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.
The Greenwald-Khanna algorithm @cite_6 is generally regarded as the best deterministic quantile summary. The space bound of @math follows from a somewhat involved proof, and it has been questioned whether this approach could be simplified or improved. Our work answers this second question in the negative. For a known universe @math of bounded size, Shrivastava al @cite_5 designed a quantile summary using @math words. Note that their algorithm is not comparison-based and so the result is incomparable to the upper bound of @math .
@cite_5 @cite_6
2161118867 2112452856
A quantile summary is a data structure that approximates to "-relative error the order statistics of a much larger underlying dataset. In this paper we develop a randomized online quantile summary for the cash register data input model and comparison data domain model that uses O( 1 " log 1 " ) words of memory. This improves upon the previous best upper bound of O( 1 log 3=2 1 ) by Agarwal et. al. (PODS 2012). Further, by a lower bound of Hung and Ting (FAW 2010) no deterministic summary for the comparison model can outperform our randomized summary in terms of space complexity. Lastly, our summary has the nice property that O( 1 log 1 ) words suce An -approximate quantile summary of a sequence of N elements is a data structure that can answer quantile queries about the sequence to within a precision of N. We present a new online algorithm for computing-approximate quantile summaries of very large data sequences. The algorithm has a worst-case space requirement of O(1 log(N)). This improves upon the previous best result of O(1 log2(N)). Moreover, in contrast to earlier deterministic algorithms, our algorithm does not require a priori knowledge of the length of the input sequence. Finally, the actual space bounds obtained on experimental data are significantly better than the worst case guarantees of our algorithm as well as the observed space requirements of earlier algorithms.