On 26.03.2019 at 12:30 in S10, there is the following noon lecture:
A Tight Lower Bound for Quantile Summaries
University of Warwick
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 ε. That is, an ε-approximate quantile summary first processes a stream of items and then, given any quantile query 0<= ϕ <= 1, returns an item from the stream, which is a ϕ'-quantile for some ϕ' = ϕ±ε.
In the talk, we describe the comparison-based quantile summary of Greenwald and Khanna (ACM SIGMOD '01) which runs in space O(1/ε · log ε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 ε-approximate quantile summary needs to store Ω(1/ε · log εN) items, implying that the aforementioned quantile summary has essentially optimal space guarantee.
(Joint work with Graham Cormode.)
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019