Reductions in streaming algorithms, with an application to counting triangles in graphs

ABSTRACT

We introduce reductions in the streaming model as a tool in the design of streaming algorithms. We develop the concept of list-efficient streaming algorithms that are essential to the design of efficient streaming algorithms through reductions.Our results include a suite of list-efficient streaming algorithms for basic statistical primitives. Using the reduction paradigm along with these tools, we design streaming algorithms for approximately counting the number of triangles in a graph presented as a stream.A specific highlight of our work is the first algorithm for the number of distinct elements in a data stream that achieves arbitrary approximation factors. (Independently, Trevisan [Tre01] has solved this problem via a different approach; our algorithm has the advantage of being list-efficient.)

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: {AYZ97} N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997.
• 3: {Bab01} S. Babu. Work related to STREAM project, 2001. http://www-db.stanford.edu/stream/related.html.
• 4: {CW79} J. L. Carter and M. N. Wegman. Universal classes of hash functions. JCSS, 18(2):143-154, 1979.
• 5: {Dic58} L. E. Dickson. Linear Groups with an Exposition of the Galois Field Theory. Dover, 1958.
• 6: Lars Engebretsen , Piotr Indyk , Ryan O'Donnell, Derandomized dimensionality reduction with applications, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.705-712, January 06-08, 2002, San Francisco, California
• 7: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 8: 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]
• 9: Jessica H. Fong , Martin Strauss, An Approximate Lp-Difference Algorithm for Massive Data Streams, Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, p.193-204, February 01, 2000
• 10: {GKMS01} A. C. Gilbert, Y. Kotidis, S. Muthuskrishnan, and M. J. Strauss. A few good terms: Efficient streaming computation of wavelet decompositions. Manuscript, 2001.
• 11: {Gol97} O. Goldreich. A sample of samplers --- a computational perspective on sampling (survey). ECCC, TR97-020, 1997.
• 12: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 13: {HRR99} M. Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. DIMACS series in Discr. Math. & Theor. Comp. Sc., 50:107-118, 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: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 16: Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
• 17: Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
• 18: {Siv01} D. Sivakumar. Algorithmic derandomization via complexity theory. Manuscript, 2001.
• 19: Larry Stockmeyer, The complexity of approximate counting, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.118-126, December 1983 [doi>10.1145/800061.808740]
• 20: {Tre01} L. Trevisan. A note on counting distinct elements in the streaming model. Manuscript, 2001.
• 21: {Yao77} A.C-C. Yao. Probabilistic computations: toward a unified measure of complexity. Proc. 18th FOCS, pp. 222-227, 1977.