Optimal Approximations of the Frequency Moments
Piotr Indyk, David P. Woodruff · DSpace@MIT (Massachusetts Institute of Technology) · 2004
We give a one-pass, O~(m^{1-2/k})-space algorithm for estimating the k-th frequency moment of a data stream for any real k>2. Together with known lower bounds, this resolves the main problem left open by Alon, Matias, Szegedy, STOC'96. Our algorithm enables deletions as well as insertions of stream elements.