Lower bounds for randomized read/write stream algorithms

ABSTRACT

Motivated by the capabilities of modern storage architectures, we consider the following generalization of the data stream model where the algorithm has sequential access to multiple streams. Unlike the data stream model, where the stream is read only, in this new model (introduced in [8,9]) the algorithms can also write onto streams. There is no limit on the size of the streams but the number of passes made on the streams is restricted. On the other hand, the amount of internal memory used by the algorithm is scarce, similar to data stream model.

We resolve the main open problem in [7] of proving lower bounds in this model for algorithms that are allowed to have 2-sided error. Previously, such lower bounds were shown only for deterministic and 1-sided error randomized algorithms [9,7]. We consider the classical set disjointness problemthat has proved to be invaluable for deriving lower bounds for many other problems involving data streams and other randomized models of computation. For this problem, we show a near-linear lower bound on the size of the internal memory used by a randomized algorithm with 2-sided error that is allowed to have o(log N/log log N) passes over the streams. This bound is almost optimal sincethere is a simple algorithm that can solve this problem using logarithmic memory if the number of passes over the streams.

Applications include near-linear lower bounds onthe internal memory for well-known problems in the literature:(1) approximately counting the number of distinct elements in the input (F₀);(2) approximating the frequency of the mod of an input sequence(F*_∞);(3) computing the join of two relations; and (4) deciding if some node of an XML document matches an XQuery (or XPath) query. Our techniques involve a novel direct-sum type of argument that yields lower bounds for many other problems. Our results asymptotically improve previously known bounds for any problem even in deterministic and 1-sided error models of computation.

REFERENCES

• 1: Gagan Aggarwal , Mayur Datar , Sridhar Rajagopalan , Matthias Ruhl, On the Streaming Model Augmented with a Sorting Primitive, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.540-549, October 17-19, 2004 [doi>10.1109/FOCS.2004.48]
• 2: [2] L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (FOCS), pages 337-347, Toronto, Ontario, Oct. 1986. IEEE.
• 3: 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]
• 4: Paul Beame , Michael Saks , Xiaodong Sun , Erik Vee, Time-space trade-off lower bounds for randomized computation of decision problems, Journal of the ACM (JACM), v.50 n.2, p.154-195, March 2003 [doi>10.1145/636865.636867]
• 5: Jian-er Chen , Chee-Keng Yap, Reversal complexity, SIAM Journal on Computing, v.20 n.4, p.622-638, Aug. 1991 [doi>10.1137/0220039]
• 6: Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
• 7: Martin Grohe , André Hernich , Nicole Schweikardt, Randomized computations on large data sets: tight lower bounds, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142387]
• 8: [8] M. Grohe, C. Koch, and N. Schweikardt. Tight lower bounds for query processing on streaming and external memory data external memory. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), LNCS3580, pages 1076-1088, 2005.
• 9: Martin Grohe , Nicole Schweikardt, Lower bounds for sorting with few random accesses to external memory, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065197]
• 10: 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
• 11: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 12: A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
• 13: Jan Matthias Ruhl , David R. Karger, Efficient algorithms for new computational models, Massachusetts Institute of Technology, 2003
• 14: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 15: David Woodruff, Optimal space lower bounds for all frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana

INDEX TERMS

General Terms:
Algorithms, Theory

Keywords:
communication complexity, data stream algorithms