Optimal Quantile Approximation in Streams
Authors:
- Zohar KarninZKZohar Karnin
- Kevin LangKLKevin Lang
- Edo LibertyELEdo Liberty
- 15 December 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 71-78
Abstract
This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An ε approximate quantile sketch receives a stream of items x1,·,xn and allows one to approximate the rank of any query item up to additive error ε n with probability at least 1-δ.The rank of a query x is the number of stream items such that xi ≤ x. The minimal sketch size required for this task is trivially at least 1/ε.Felber and Ostrovsky obtain a O((1/ε)log(1/ε)) space sketch for a fixed δ.Without restrictions on the nature of the stream or the ratio between ε and n, no better upper or lower bounds were known to date. This paper obtains an O((1/ε)log log (1/δ)) space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching for which an Ω((1/ε)log(1/ε)) lower bound is known. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This modification allows for an analysis which is both tight and extremely simple. The same technique was reported, in private communications, to be useful for improving other sketching objectives and geometric coreset constructions.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Quantiles and Equi-depth Histograms over Streams2016
- Frugal Streaming for Estimating Quantiles2013
- Space-Efficient Data Structures, Streams, and AlgorithmsLecture Notes in Computer Science, 2013
- Mergeable summaries2012
- An $\Omega(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ Space Lower Bound for Finding ε-Approximate Quantiles in a Data StreamLecture Notes in Computer Science, 2010
- Stream Order and Order Statistics: Quantile Estimation in Random-Order StreamsSIAM Journal on Computing, 2009
- Medians and beyond2004
- Space-efficient online computation of quantile summaries2001
- Random sampling techniques for space efficient online computation of order statistics of large datasetsACM SIGMOD Record, 1999
- Selection and sorting with limited storageTheoretical Computer Science, 1980