Optimal approximations of the frequency moments of data streams

ABSTRACT

We give a 1-pass Õ(m^1-2⁄k)-space algorithm for computing the k-th frequency moment of a data stream for any real k > 2. Together with the lower bounds of [1, 2, 4], this resolves the main problem left open by Alon et al in 1996 [1]. Our algorithm also works for streams with deletions and thus gives an Õ(m ^1-2⁄p) space algorithm for the Lp difference problem for any p > 2. This essentially matches the known Ω(m^1-2⁄p-o(1)) lower bound of [12, 2]. Finally the update time of our algorithms is Õ(1).

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, An Information Statistics Approach to Data Stream and Communication Complexity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.209-218, November 16-19, 2002
• 3: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, Counting Distinct Elements in a Data Stream, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.1-10, September 13-15, 2002
• 4: A. Chakrabarti, S. Khot, and X. Sun. Near-optimal lower bounds on the multiparty communication complexity of set-disjointness. In Proceedings of the 18th IEEE Conference on Computational Complexity (CCC), pages 107--117, 2003.
• 5: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004 [doi>10.1016/S0304-3975(03)00400-6]
• 6: Don Coppersmith , Ravi Kumar, An improved data stream algorithm for frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 7: Joan Feigenbaum , Sampath Kannan , Martin J. Strauss , Mahesh Viswanathan, An Approximate L¹-Difference Algorithm for Massive Data Streams, SIAM Journal on Computing, v.32 n.1, p.131-151, 2003 [doi>10.1137/S0097539799361701]
• 8: S. Ganguly. Estimating Frequency Moments of Data Streams using Random Linear Combinations. In RANDOM, 2004.
• 9: S. Ganguly. A Hybrid Technique for Estimating Frequency Moments over Data Streams. Unpublished Manuscript, 2004.
• 10: P. Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. In Journal of the ACM, to appear.
• 11: Preliminary version in Proceedings of the 41st Symposium on Foundations of Computer Science (FOCS), pages 187-197, 2000.
• 12: Piotr Indyk, A small approximately min-wise independent family of hash functions, Journal of Algorithms, v.38 n.1, p.84-90, Jan. 2001 [doi>10.1006/jagm.2000.1131]
• 13: Michael Saks , Xiaodong Sun, Space lower bounds for distance approximation in the data stream model, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509963]
• 14: Mikkel Thorup , Yin Zhang, Tabulation based 4-universal hashing with applications to second moment estimation, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms

Keywords:
frequency moments, streaming algorithms