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_4: A fundamental problem in data management and analysis is to generate descriptions of the distribution of data. It is most common to give such descriptions in terms of the cumulative distribution, which is characterized by the quantiles of the data. The design and engineering of efficient methods to find these quantiles has attracted much study, especially in the case where the data are given incrementally, and we must compute the quantiles in an online, streaming fashion. While such algorithms have proved to be extremely useful in practice, there has been limited formal comparison of the competing methods, and no comprehensive study of their performance. In this paper, we remedy this deficit by providing a taxonomy of different methods and describe efficient implementations. In doing so, we propose new variants that have not been studied before, yet which outperform existing methods. To illustrate this, we provide detailed experimental comparisons demonstrating the trade-offs between space, time, and accuracy for quantile computation.
  @cite_11: A quantile query over a set (S ) of size (n ), takes as input a quantile ( ), (0 < 1 ), and returns a value (v S ), whose rank in the sorted (S ) is ( n ). Computing the median, the 99-percentile, or the quartiles of a set are examples of quantile queries. Many database optimization problems involve approximate quantile computations over large data sets. Query optimizers use quantile estimates to estimate the size of intermediate results and choose an efficient plan among a set of competing plans. Load balancing in parallel databases can be done by using quantile estimates. Above all, quantile estimates can give a meaningful summary of a large data set using a very small memory footprint. In this chapter, we present a broad range of algorithmic ideas for computing quantile summaries of data streams using small space. We highlight connections among these ideas, and how techniques developed for one setting sometimes naturally lend themselves to a seemingly different setting.
summary: Luo al @cite_4 compared quantile summaries experimentally and also provided a simple randomized algorithm with a good practical performance. This paper studies not only streaming algorithms for insertion-only streams (i.e., the cash register model), but also for turnstile streams, in which items may depart. Note that any algorithm for turnstile streams inherently relies on the bounded size of the universe. We refer the interested reader to the survey of Greenwald and Khanna @cite_11 for a description of both deterministic and randomized algorithms, together with algorithms for turnstile streams, the sliding window model, and distributed algorithms.