Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2509.07599 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909778851135488 |
|---|---|
| author | Green-Maimon, Naomi Zamir, Or |
| author_facet | Green-Maimon, Naomi Zamir, Or |
| contents | Estimating the second frequency moment $F_2$ of a data stream up to a $(1 \pm \varepsilon)$ factor is a central problem in the streaming literature. For errors $\varepsilon > Ω(1/\sqrt{n})$, the tight bound $Θ\left(\log(\varepsilon^2 n)/\varepsilon^2\right)$ was recently established by Braverman and Zamir. In this work, we complete the picture by resolving the remaining regime of small error, $\varepsilon < 1/\sqrt{n}$, showing that the optimal space complexity is $Θ\left( \min\left(n, \frac{1}{\varepsilon^2} \right) \cdot \left(1 + \left| \log(\varepsilon^2 n) \right| \right) \right)$ bits for all $\varepsilon \geq 1/n^2$, assuming a sufficiently large universe. This closes the gap between the best known $Ω(n)$ lower bound and the straightforward $O(n \log n)$ upper bound in that range, and shows that essentially storing the entire stream is necessary for high-precision estimation.
To derive this bound, we fully characterize the two-party communication complexity of estimating the size of a set intersection up to an arbitrary additive error $\varepsilon n$. In particular, we prove a tight $Ω(n \log n)$ lower bound for one-way communication protocols when $\varepsilon < n^{-1/2-Ω(1)}$, in contrast to classical $O(n)$-bit protocols that use two-way communication. Motivated by this separation, we present a two-pass streaming algorithm that computes the exact histogram of a stream with high probability using only $O(n \log \log n)$ bits of space, in contrast to the $Θ(n \log n)$ bits required in one pass even to approximate $F_2$ with small error. This yields the first asymptotic separation between one-pass and $O(1)$-passes space complexity for small frequency moment estimation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07599 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes Green-Maimon, Naomi Zamir, Or Data Structures and Algorithms Estimating the second frequency moment $F_2$ of a data stream up to a $(1 \pm \varepsilon)$ factor is a central problem in the streaming literature. For errors $\varepsilon > Ω(1/\sqrt{n})$, the tight bound $Θ\left(\log(\varepsilon^2 n)/\varepsilon^2\right)$ was recently established by Braverman and Zamir. In this work, we complete the picture by resolving the remaining regime of small error, $\varepsilon < 1/\sqrt{n}$, showing that the optimal space complexity is $Θ\left( \min\left(n, \frac{1}{\varepsilon^2} \right) \cdot \left(1 + \left| \log(\varepsilon^2 n) \right| \right) \right)$ bits for all $\varepsilon \geq 1/n^2$, assuming a sufficiently large universe. This closes the gap between the best known $Ω(n)$ lower bound and the straightforward $O(n \log n)$ upper bound in that range, and shows that essentially storing the entire stream is necessary for high-precision estimation. To derive this bound, we fully characterize the two-party communication complexity of estimating the size of a set intersection up to an arbitrary additive error $\varepsilon n$. In particular, we prove a tight $Ω(n \log n)$ lower bound for one-way communication protocols when $\varepsilon < n^{-1/2-Ω(1)}$, in contrast to classical $O(n)$-bit protocols that use two-way communication. Motivated by this separation, we present a two-pass streaming algorithm that computes the exact histogram of a stream with high probability using only $O(n \log \log n)$ bits of space, in contrast to the $Θ(n \log n)$ bits required in one pass even to approximate $F_2$ with small error. This yields the first asymptotic separation between one-pass and $O(1)$-passes space complexity for small frequency moment estimation. |
| title | Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.07599 |