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/30483 |
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., 18493060 bytes, 833343 bytes, application/postscript, application/pdf |
Relation | Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory |
Page generated in 0.0055 seconds