Taylor Polynomial Estimator for Estimating Frequency Moments

Taylor Polynomial Estimator for Estimating Frequency Moments by Sumit Ganguly

We present a randomized algorithm for estimating the pth moment Fp of the frequency vector of a data stream in the general update (turnstile) model to within a multiplicative factor of 1±ϵ, for p>2, with high constant confidence. For 0<ϵ≤1, the algorithm uses space O(n1−2/pϵ−2+n1−2/pϵ−4/plog(n)) words. This improves over the current bound of O(n1−2/pϵ−2−4/plog(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 ϵ=(log(n))−Ω(1) and the lower bound of Andoni et. al. \cite{anpw:icalp13} for ϵ=Ω(1).

    Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.