Optimality of Frequency Moment Estimation

Abstract

Estimating the second frequency moment of a stream up to $(1\pm \epsilon )$ multiplicative error requires at most $O(\log n/{\epsilon }^2)$ bits of space, due to a seminal result of Alon, Matias, and Szegedy. It is also known that at least $\hat{I}\text{c◯}(\log n+1/{\epsilon }^2)$ space is needed. We prove an optimal lower bound of $\hat{I}\text{c◯}\left(\log \left(n{\epsilon }^2\right)/{\epsilon }^2\right)$ for all $\epsilon =\hat{I}\text{c◯}(1/\sqrt{n})$. Note that when $\epsilon >n^{-1/2+c}$, where $c>0$, our lower bound matches the classic upper bound of AMS. For smaller values of $\epsilon$ we also introduce a revised algorithm that improves the classic AMS bound and matches our lower bound.

This version retracts a previously included sketch claiming that the lower bound should extend to non-integral frequency moments F_p for p in (1,2)