Optimal Quantile Approximation in Streams

Abstract

This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An $\epsilon$ approximate quantile sketch receives a stream of items $x_1,\dots ,x_n$ and allows one to approximate the rank of any query up to additive error $\epsilon n$ with probability at least $1-\delta$. The rank of a query $x$ is the number of stream items such that $x_i\le x$. The minimal sketch size required for this task is trivially at least $1/\epsilon$. Felber and Ostrovsky obtain a $O((1/\epsilon )\log (1/\epsilon ))$ space sketch for a fixed $\delta$. To date, no better upper or lower bounds were known even for randomly permuted streams or for approximating a specific quantile, e.g.,\ the median. This paper obtains an $O((1/\epsilon )\log \log (1/\delta ))$ space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This subtle modification allows for an analysis which is both tight and extremely simple. Similar techniques should be useful for improving other sketching objectives and geometric coreset constructions.