Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916714337271808 |
|---|---|
| author | Feng, Shiyuan Swartworth, William Woodruff, David P. |
| author_facet | Feng, Shiyuan Swartworth, William Woodruff, David P. |
| contents | We consider the heavy-hitters and $F_p$ moment estimation problems in the sliding window model. For $F_p$ moment estimation with $1<p\leq 2$, we show that it is possible to give a $(1\pm ε)$ multiplicative approximation to the $F_p$ moment with $2/3$ probability on any given window of size $n$ using $\tilde{O}(\frac{1}{ε^p}\log^2 n + \frac{1}{ε^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}ε.$ 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}{ε^2}\log^2 n)$ space which is tight. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_21175 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model Feng, Shiyuan Swartworth, William Woodruff, David P. Data Structures and Algorithms We consider the heavy-hitters and $F_p$ moment estimation problems in the sliding window model. For $F_p$ moment estimation with $1<p\leq 2$, we show that it is possible to give a $(1\pm ε)$ multiplicative approximation to the $F_p$ moment with $2/3$ probability on any given window of size $n$ using $\tilde{O}(\frac{1}{ε^p}\log^2 n + \frac{1}{ε^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}ε.$ 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}{ε^2}\log^2 n)$ space which is tight. |
| title | Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2504.21175 |