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.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/6741 |
| Date | 02 July 2004 |
| Creators | Indyk, Piotr, Woodruff, David |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | en_US |
| Detected Language | English |
| Format | 18 p., 3705201 bytes, 761567 bytes, application/postscript, application/pdf |
| Relation | AIM-2004-014 |
Page generated in 0.0017 seconds