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

arXiv: https://arxiv.org/abs/2504.21175 · HTML: https://mlsanity.com/paper/2504.21175/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2025.

## Built on by (most cited first, 1 of 1)

- [Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits](https://mlsanity.com/paper/2606.08977/) (2026)

## Abstract (arXiv)

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.