An improved data stream algorithm for frequency moments

ABSTRACT

We present a simple, one-pass, Õ(√n)-space data stream algorithm for approximating the third frequency moment. This is the first improvement to the Õ(n^2/3)-space data stream algorithm of Alon, Matias, and Szegedy [AMS99]. the current known lower bound for this problem is Ω(n^1/3) [BJKS02a].Our algorithm can also be generalized to an Õ(n^1-1/(k-1))-space data stream algorithm for approximating the k-th frequency moment. Besides improving the Õ(n^1--1/k)-space upper bound [AMS99], our algorithm beats the Ω(n^1--1/k)-sampling lower bound [BKS01] for this problem.Our method suggests a unified perspective of space-efficient data stream algorithms for all frequency moments.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 2: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 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: 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
• 5: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, Information Theory Methods in Communication Complexity, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.93, May 21-24, 2002
• 6: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Sampling algorithms: lower bounds and applications, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.266-275, July 2001, Hersonissos, Greece [doi>10.1145/380752.380810]
• 7: Ziv Bar-Yosseff , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 8: {CKS03} A. Chakrabarti, S. Khot, and X. Sun. Nearoptimal lower bounds on the multiparty communication complexity of set-disjointness. In Proc. of the 18th Annual IEEE Conference on Computational Complexity (CCC), 2003.
• 9: {CW79} L. Carter and M. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143--154, 1979.
• 10: 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]
• 11: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 12: Phillip B. Gibbons , Srikanta Tirthapura, Estimating simple functions on the union of data streams, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.281-291, July 2001, Crete Island, Greece [doi>10.1145/378580.378687]
• 13: Monika R. Henzinger , Prabhakar Raghavan , Sridhar Rajagopalan, Computing on data streams, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 14: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 15: Piotr Indyk , David Woodruff, Tight Lower Bounds for the Distinct Elements Problem, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.283, October 11-14, 2003
• 16: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 17: 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]
• 18: {WC81} M. Wegman and L. Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3):265--279, 1981.