Taylor Polynomial Estimator for Estimating Frequency Moments

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