Open Problems:2 - Revision history

Krzysztof Onak at 01:37, 7 March 2013

2013-03-07T01:37:32Z

Krzysztof Onak at 04:54, 16 November 2012

2012-11-16T04:54:44Z

Krzysztof Onak at 02:07, 16 November 2012

2012-11-16T02:07:10Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:50Z

1 revision

Krzysztof Onak at 19:41, 19 September 2012

2012-09-19T19:41:15Z

New page

{{DISPLAYTITLE:Problem 2: Quantiles}}
{{Infobox
|label1 = Proposed by
|data1 = Graham Cormode
|label2 = Source
|data2 = [[Workshops:Kanpur_2006|Kanpur 2006]]
|label3 = Short link
|data3 = http://sublinear.info/2
}}
The problem of tracking the quantiles (median and generalizations thereof)
of a distribution produced by a stream has attracted significant study
over the last decade {{cite|MankuRL-98|MankuRL-99|GreenwaldK-01|GilbertKMS-02|CormodeM-05|ShrivastavaBAS-04|GuhaM-06}}.
For deterministic algorithms on insert only streams, two algorithms obtain
the best (and incomparable) space bounds: $O(\epsilon^{-1} \log \epsilon N)$
words {{cite|GreenwaldK-01}} and $O(\epsilon^{-1}\log U )$
words {{cite|ShrivastavaBAS-04}}, where $U$ is the size of
the domain from which the input is drawn.

The Greenwald-Khanna algorithm {{cite|GreenwaldK-01}} is simple to implement, and works on
streams of items drawn from arbitrary domains.
However, the analysis is rather involved; moreover, attempts to modify the
analysis for different situations (say, weighted input items, merging
summaries together, giving different guarantees to different ranges etc.)
lead to heuristics at best, which may no longer have strict guarantees and
known bad cases.
The $q$-digest algorithm {{cite|ShrivastavaBAS-04}} is much
simpler to analyze and more amenable to variations, meaning that several
generalizations and alternatives have been
proposed {{cite|HershbergerSST-04|CormodeKMS-06}}.
However, it carries with it a factor of $\log U$, meaning that the universe
has to be known, making it impractical for tracking quantiles over streams
of floating point values, or strings.

This leads to some interlinked open questions:
#What is the optimal space bound for an algorithm to compute quantiles of a data stream? Is $O(\epsilon^{-1})$ words achievable?
#Can the Greenwald-Khanna algorithm, or a variation thereof, submit to a simpler analysis which will allow generalizations of the algorithm to be more easily proposed and studied?

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur06
 |who=Graham Cormode

@@ Line 1: / Line 1: @@
 {{Header
- |number=2
+|title=Quantiles
- |title=Quantiles
+|source=kanpur06
- |source=kanpur06
+|who=Graham Cormode
 }}
 The problem of tracking the quantiles (median and generalizations thereof)

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)