# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 26.3.2019 at 12:30 in S10, there is the following noon lecture:

# 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 ε. 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 Archive page