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 &#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.)

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

Webmaster: kamweb.mff.cuni.cz         Archive page