Unverified

Quantiles

Consider deterministic algorithms that compute quantiles on insert-only data streams. Let $\epsilon$ denote the approximation parameter used on the source page, and let $U$ be the size of the input domain. The source does not specify the precise approximation guarantee or a range for $\epsilon$ .

Problem 1.

What is the optimal space bound, measured in words, for computing quantiles of a data stream? In particular, is a bound of

O(\epsilon^{-1})

words achievable?

Problem 2.

Can the Greenwald--Khanna algorithm, or a variation of it, admit a simpler analysis that makes generalizations easier to propose and study while retaining strict guarantees?

Download

Abstract

The problem concerns deterministic quantile summaries for insert-only data streams. Two known algorithms have incomparable space bounds: one applies to arbitrary input domains but has an involved analysis, while the other is easier to analyze and generalize but incurs a factor depending on the known domain size. The first open question asks for the optimal space bound and, in particular, whether $O(\epsilon^{-1})$ words suffice. The second asks whether the Greenwald--Khanna algorithm or a variation can receive a simpler analysis that supports generalizations with strict guarantees.

Background and progress

The problem was suggested by Graham Cormode and lists Kanpur 2006 as its source [sublinear2006quantiles, 2006]. It concerns tracking quantiles, including the median and its generalizations, of a distribution produced by a stream. For deterministic algorithms on insert-only streams, the page reports two best but incomparable space bounds: one is written as $O(\epsilon^{-1}\log \epsilon N)$ words, and the other is $O(\epsilon^{-1}\log U)$ words, where $U$ is the size of the domain from which inputs are drawn. The page does not define the symbol $N$ or state the precise approximation convention for $\epsilon$ .

The Greenwald--Khanna algorithm realizes the first type of bound, is simple to implement, and works for items from arbitrary domains. Its analysis is involved, however, and attempts to adapt the analysis to weighted items, merged summaries, or different guarantees over different ranges can yield only heuristics, potentially without strict guarantees and with known bad cases.

The $q$ -digest algorithm realizes the domain-dependent alternative. Its analysis is simpler and more amenable to variations, but the $\log U$ factor requires the input universe to be known and makes the method impractical for streams of floating-point values or strings. These complementary limitations leave both the optimal space complexity and the possibility of a simpler, generalizable analysis of the Greenwald--Khanna method unresolved. The original problem page is https://sublinear.info/index.php?title=Open_Problems:2.

Reference papers

Problem 2: Quantiles2006 ↗

Quantiles

Problem 1.

Problem 2.

Coming soon

Organizer