Taylor Polynomial Estimator for Estimating Frequency Moments

摘要: We present a randomized algorithm for estimating the pth 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 < \le 1\), uses space \(O( n^{1-2/p} ^{-2} + ^{-4/p} \log (n))\) words. This improves over current bound \(O(n^{1-2/p} ^{-2-4/p} words by Andoni et. al. [2]. Our upper matches lower Li and Woodruff [17] \(\epsilon = (\log (n))^{-\varOmega (1)}\) [3] \varOmega (1)\).