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

We consider the heavy-hitters and Fp moment estimation problems in the sliding window model. For Fp moment estimation with 1<p≤ 2, we show that it is possible to give a (1± ε) multiplicative approximation to the Fp moment with 2/3 probability on any given window of size n using tildeO(frac1εplog2 n + frac1ε2log n) bits of space. We complement this result with a lower bound showing that our algorithm gives tight bounds up to factors of loglog n and logfrac1ε. As a consequence of our F2 moment estimation algorithm, we show that the heavy-hitters problem can be solved on an arbitrary window using O(frac1ε2log2 n) space which is tight.