Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model

Abstract

We consider the heavy-hitters and $F_p$ moment estimation problems in the sliding window model. For $F_p$ moment estimation with $1<p\le 2$, we show that it is possible to give a $(1\pm \epsilon )$ multiplicative approximation to the $F_p$ moment with $2/3$ probability on any given window of size $n$ using $\tilde{O}(\frac{1}{{\epsilon }^p}{\log }^{2}n+\frac{1}{{\epsilon }^2}\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 $\log \frac{1}{\epsilon }.$ As a consequence of our $F_2$ moment estimation algorithm, we show that the heavy-hitters problem can be solved on an arbitrary window using $O(\frac{1}{{\epsilon }^2}{\log }^{2}n)$ space which is tight.