Optimal Approximations of the Frequency Moments
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...
Main Authors: | Indyk, Piotr, Woodruff, David |
---|---|
Language: | en_US |
Published: |
2004
|
Subjects: | |
Online Access: | http://hdl.handle.net/1721.1/6741 |
Similar Items
-
Optimal Approximations of the Frequency Moments
by: Indyk, Piotr, et al.
Published: (2005) -
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees
by: Badoiu, Mihai, et al.
Published: (2004) -
A Constant-Factor Approximation Algorithm for Embedding Unweighted Graphs into Trees
by: Badoiu, Mihai, et al.
Published: (2005) -
New LSH-based Algorithm for Approximate Nearest Neighbor
by: Andoni, Alexandr, et al.
Published: (2005) -
Generalized Low-Rank Approximations
by: Srebro, Nathan, et al.
Published: (2004)