Abstract. When trying to process a data stream in small space, how important is the order in which the data arrive? Are there problems that are unsolvable when the ordering is worst case, but that can be solved (with high probability) when the order is chosen uniformly at random? If we consider the stream as if ordered by an adversary, what happens if we restrict the power of the adversary? We study these questions in the context of quantile estimation, one of the most well studied problems in the data-stream model. Our results include an O(polylog n)-space, O(log log n)-pass algorithm for exact selection in a randomly ordered stream of n elements. This resolves an open question of Munro and Paterson [Theoret. Comput. Sci., 23 (1980), pp. 315-323]. We then demonstrate an exponential separation between the random-order and adversarial-order models: using O(polylog n) space, exact selection requires Ω(log n/ log log n) passes in the adversarial-order model. This lower bound, in contrast to previous results, applies to fully general randomized algorithms and is established via a new bound on the communication complexity of a natural pointer-chasing style problem. We also prove the first fully general lower bounds in the random-order model: finding an element with rank n/2 ± n δ in the single-pass random-order model with probability at least 9/10 requires Ω( n 1−3δ / log n) space. Key words. communication complexity, stochastically generated streams, stream computation AMS subject classifications. 68Q05, 68Q17, 68Q25, 68W20, 68W25 1. Introduction. One of the principal theoretical motivations for studying the data-stream model is to understand the role played by the order in which a problem is revealed. While an algorithm in the RAM model can process the input data in an arbitrary order, the key constraint of the data-stream model is that the algorithm must process (in small space) the input data in the order in which it arrives. Parameterizing the number of passes that an algorithm may have over the data establishes a spectrum between the RAM model and the one-pass data-stream model. How does the computational power of the model vary along this spectrum? To what extent does it matter how the stream is ordered? These issues date back to one of the earliest papers on the data-stream model in which Munro and Paterson considered the problems of sorting and selection in limited space [21] . They showed thatÕ(n 1/p ) space was sufficient to find the exact median of a sequence of n numbers given p passes over the data. However, if the data were randomly ordered,Õ(n 1/(2p) ) space sufficed. Based on this result and other observations, it seemed plausible that any p-pass algorithm in the random-order model could be simulated by a 2p-pass algorithm in the adversarial-order model. This was posed as an open problem by Kannan [17], and further support for this conjecture came via work initiated by Feigenbaum et al. [6] that considered the relationship
For random-order streams, Guha and McGregor REF studied algorithms for exact and approximate selection of quantiles.
STREAM ORDER AND ORDER STATISTICS: QUANTILE ESTIMATION IN RANDOM-ORDER STREAMS ∗
SIAM J. Comput.
SIAM J. Comput.
Mathematics Computer Science