Tight lower bounds for selection in randomly ordered streams

ABSTRACT

We show that any algorithm computing the median of a stream presented in random order, using polylog(n) space, requires an optimal Ω (log log n) passes, resolving an open question from the seminal paper on streaming by Munro and Paterson, from FOCS 1978.

REFERENCES

• 1: Micah Adler , Erik D. Demaine , Nicholas J. A. Harvey , Mihai Pǎtraşcu, Lower bounds for asymmetric communication channels and distributed source coding, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.251-260, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109586]
• 2: Amit Chakrabarti, Lower Bounds for Multi-Player Pointer Jumping, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.33-45, June 13-March 16, 2007 [doi>10.1109/CCC.2007.14]
• 3: Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Space- and time-efficient deterministic algorithms for biased quantiles over data streams, 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.1142389]
• 4: Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005 [doi>10.1016/j.jalgor.2003.12.001]
• 5: Amit Chakrabarti , Oded Regev, An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.473-482, October 17-19, 2004 [doi>10.1109/FOCS.2004.12]
• 6: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 7: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, United States
• 8: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, How to summarize the universe: dynamic maintenance of quantiles, Proceedings of the 28th international conference on Very Large Data Bases, p.454-465, August 20-23, 2002, Hong Kong, China
• 9: Sudipto Guha , Andrew McGregor, Approximate quantiles and the order of the stream, 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.1142390]
• 10: {GM07} Sudipto Guha and Andrew McGregor. Lower bounds for quantile estimation in random-order and multi-pass streaming. In Proc. 34th International Colloquium on Automata, Languages and Programming, pages 704--715, 2007.
• 11: Anupam Gupta , Francis X. Zane, Counting inversions in lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.103-111, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225093]
• 13: {MP80} J. Ian Munro and Mike Paterson. Selection and sorting with limited storage. TCS, 12:315--323, 1980. Preliminary version in Proc. 19th Annual IEEE Symposium on Foundations of Computer Science, pages 253--258, 1978.
• 14: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.426-435, June 01-04, 1998, Seattle, Washington, United States
• 15: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.251-262, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 16: Mihai Pătraşcu , Mikkel Thorup, Time-space trade-offs for predecessor search, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132551]
• 17: Mihai Pǎtraşcu , Mikkel Thorup, Randomization does not help searching predecessors, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.555-564, January 07-09, 2007, New Orleans, Louisiana
• 18: Nisheeth Shrivastava , Chiranjeeb Buragohain , Divyakant Agrawal , Subhash Suri, Medians and beyond: new aggregation techniques for sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031524]
• 19: {Sen03} Pranab Sen. Lower bounds for predecessor searching in the cell probe model. In Proc. 18th Annual IEEE Conference on Computational Complexity, pages 73--83, 2003.
• 20: {VW07} Emanuele Viola and Avi Wigderson. One-way multiparty communication lower bound for pointer jumping with applications. In Proc. 48th Annual IEEE Symposium on Foundations of Computer Science, 2007. to appear.
• 21: {Yao77} Andrew C. Yao. Probabilistic computations: Towards a unified measure of complexity. In Proc. 18th Annual IEEE Symposium on Foundations of Computer Science, pages 222--227, 1977.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Theory