Optimal space lower bounds for all frequency moments

ABSTRACT

We prove that any one-pass streaming algorithm which (ε, δ)-approximates the kth frequency moment Fk, for any real k ≠ 1 and any ε = Ω(1/√m), must use Ω(1/ε²) bits of space, where m is the size of the universe. This is optimal in terms of ε, resolves the open questions of Bar-Yossef et al in [3, 4], and extends the Ω(1/ε²) lower bound for F0 in [11] to much smaller ε by applying novel techniques. Along the way we lower bound the one-way communication complexity of approximating the Hamming distance and the number of bipartite graphs with minimum/maximum degree constraints.

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: N. Alon and J. Spencer. The Probabilistic Method, Wiley Interscience, New York, 1992, 86--87.
• 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: Z. Bar Yossef. The complexity of massive data set computations. Ph.D. Thesis, U.C. Berkeley, 2002.
• 5: 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
• 6: 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
• 7: G. Cormode, M. Datar, P. Indyk, and M. Muthukrishnan. Comparing Data Streams Using Hamming Norms. 28th International Conference on Very Large Databases (VLDB), 2002.
• 8: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Practical Skew Handling in Parallel Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.27-40, August 23-27, 1992
• 9: P. Flajolet and G. N. Martin. Probabilistic Counting Algorithms for Data Base Applications. Journal of Computer and System Sciences, 18(2) 143--154, 1979.
• 10: I. J. Good. Surprise Indexes and P-values. Journal of Statistical Computation and Simulation 32, p 90--92, 1989.
• 11: 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
• 12: Ilan Kremer , Noam Nisan , Dana Ron, On randomized one-round communication complexity, Computational Complexity, v.8 n.1, p.21-49, June 1999 [doi>10.1007/s000370050018]
• 13: Brendan D. Mckay , Ian M. Wanless , Nicholas C. Wormald, Asymptotic Enumeration of Graphs with a Given Upper Bound on the Maximum Degree, Combinatorics, Probability and Computing, v.11 n.4, p.373-392, July 2002 [doi>10.1017/S0963548302005229]
• 14: V. N. Vapnik and A. Y. Chervonenkis. On the uniform converges of relative frequences of events to their probabilities. Theory of Probability and its Applications, XVI(2):264--280, 1971.
• 15: A. C-C. Yao. Lower bounds by probabilistic arguments. In Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, p. 420--428, 1983.