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).
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.
No comments:
Post a Comment