Optimality of Frequency Moment Estimation
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918113803501568 |
|---|---|
| author | Braverman, Mark Zamir, Or |
| author_facet | Braverman, Mark Zamir, Or |
| contents | Estimating the second frequency moment of a stream up to $(1\pm\varepsilon)$ multiplicative error requires at most $O(\log n / \varepsilon^2)$ bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least $Ω(\log n + 1/\varepsilon^{2})$ space is needed. We prove an optimal lower bound of $Ω\left(\log \left(n \varepsilon^2 \right) / \varepsilon^2\right)$ for all $\varepsilon = Ω(1/\sqrt{n})$. Note that when $\varepsilon>n^{-1/2 + c}$, where $c>0$, our lower bound matches the classic upper bound of AMS. For smaller values of $\varepsilon$ we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02148 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimality of Frequency Moment Estimation Braverman, Mark Zamir, Or Data Structures and Algorithms Computational Complexity Information Theory Estimating the second frequency moment of a stream up to $(1\pm\varepsilon)$ multiplicative error requires at most $O(\log n / \varepsilon^2)$ bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least $Ω(\log n + 1/\varepsilon^{2})$ space is needed. We prove an optimal lower bound of $Ω\left(\log \left(n \varepsilon^2 \right) / \varepsilon^2\right)$ for all $\varepsilon = Ω(1/\sqrt{n})$. Note that when $\varepsilon>n^{-1/2 + c}$, where $c>0$, our lower bound matches the classic upper bound of AMS. For smaller values of $\varepsilon$ we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound. |
| title | Optimality of Frequency Moment Estimation |
| topic | Data Structures and Algorithms Computational Complexity Information Theory |
| url | https://arxiv.org/abs/2411.02148 |