2026-08-16T16:19:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23452 2025-10-02T12:55:33Z ddc:004 open_access

Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model Feng, Shiyuan Swartworth, William Woodruff, David sketching streaming heavy hitters sliding window moment estimation We consider the heavy-hitters and F_p moment estimation problems in the sliding window model. For F_p moment estimation with 1 < p ≤ 2, we show that it is possible to give a (1± ε) multiplicative approximation to the F_p moment with 2/3 probability on any given window of size n using Õ(1/(ε^p)log² n + 1/(ε²)log n) bits of space. We complement this result with a lower bound showing that our algorithm gives tight bounds up to factors of log log n and log1/(ε). As a consequence of our F₂ moment estimation algorithm, we show that the heavy-hitters problem can be solved on an arbitrary window using O(1/(ε²)log² n) space which is tight. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shiyuan Feng and William Swartworth and David Woodruff 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.75 urn:nbn:de:0030-drops-234524 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.75 eng https://creativecommons.org/licenses/by/4.0/legalcode