Taylor Polynomial Estimator for Estimating Frequency Moments

Abstract

We present a randomized algorithm for estimating the $p$th moment $F_p$ of the frequency vector of a data stream in the general update (turnstile) model to within a multiplicative factor of $1\pm \epsilon$, for $p>2$, with high constant confidence. For $0<\epsilon \le 1$, the algorithm uses space $O(n^{1-2/p}{\epsilon }^{-2}+n^{1-2/p}{\epsilon }^{-4/p}\log (n))$ words. This improves over the current bound of $O(n^{1-2/p}{\epsilon }^{-2-4/p}\log (n))$ words by Andoni et. al. in \cite{ako:arxiv10}. Our space upper bound matches the lower bound of Li and Woodruff \cite{liwood:random13} for $\epsilon =(\log (n){)}^{-\Omega (1)}$ and the lower bound of Andoni et. al. \cite{anpw:icalp13} for $\epsilon =\Omega (1)$.

Supercedes arXiv:1104.4552. Extended Abstract of this paper to appear in Proceedings of ICALP 2015