A Tight Lower Bound for Quantile Summaries

Pavel Veselý

University of Warwick

Abstract

Quantiles, such as the median (or 0.5-quantile), provide concise and useful information about the distribution of a sequence of items 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 &#949;. That is, an &#949;-approximate quantile summary first processes a stream of items and then, given any quantile query 0<= &#981; <= 1, returns an item from the stream, which is a &#981;'-quantile for some &#981;' = &#981;&plusmn;&#949;.

In the talk, we describe the comparison-based quantile summary of Greenwald and Khanna (ACM SIGMOD '01) which runs in space O(1/&#949; &middot; log &#949;N), where N is the number of items in the stream and comparison-based means that the only allowed operations with items are the equality test and a comparison of two items. We then prove that any deterministic comparison-based &#949;-approximate quantile summary needs to store &#937;(1/&#949; &middot; log &#949;N) items, implying that the aforementioned quantile summary has essentially optimal space guarantee.

(Joint work with Graham Cormode.)