text: Quantiles, such as the median or percentiles, provide concise and useful information about the distribution of a collection of items, drawn from a linearly ordered universe. We study data structures, called quantile summaries, which keep track of all quantiles, up to an error of at most @math . That is, an @math -approximate quantile summary first processes a stream of items and then, given any quantile query @math , returns an item from the stream, which is a @math -quantile for some @math . We focus on comparison-based quantile summaries that can only compare two items and are otherwise completely oblivious of the universe. The best such deterministic quantile summary to date, by Greenwald and Khanna (ACM SIGMOD '01), stores at most @math items, where @math is the number of items in the stream. We prove that this space bound is optimal by providing a matching lower bound. Our result thus rules out the possibility of constructing a deterministic comparison-based quantile summary in space @math , for any function @math that does not depend on @math . A consequence of our results is also to show a lower bound for randomized algorithms.
  @cite_9: We resolve the problem of small-space approximate selection in random-order streams. Specifically, we present an algorithm that reads the n elements of a set in random order and returns an element whose rank differs from the true median by at most n1 3+o(1) while storing a constant number of elements and counters at any one time. This is optimal: it was previously shown that achieving better accuracy required poly(n) memory. However, it was conjectured that the lower bound was not tight and that a previous algorithm achieving an n1 2+o(1) approximation was optimal. We therefore consider the new result a surprising resolution to a natural and basic question.
  @cite_13: 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 con- sider 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 logn)-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 logn) passes in the adversarial-order model. This lower bound, in contrast to previous results, applies to fully general randomized algorithms and is estab- lished 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δ logn) space.
summary: Other results arise when relaxing the requirement for correctness under adversarial order to assuming that the input arrives in a random order. For random-order streams, Guha and McGregor @cite_13 studied algorithms for exact and approximate selection of quantiles. Among other things, they gave an algorithm for finding the exact @math -quantile in space @math using @math passes over a random-order stream, while with @math memory we need to do @math passes on the worst-case stream. The Shifting Sands algorithm @cite_9 reduce the magnitude of the error from @math to @math . Since our lower bound relies on carefully constructing an adversarial input sequence, it does not apply to this random order model.