Fetching the paper…

Reading the bibliography…

2016

Optimal Quantile Approximation in Streams

Karnin, Zohar, Lang, Kevin, Liberty, Edo

Original
PDF
Post on X

Understand

This paper resolves one of the longest standing basic problems in the streaming computational model.

Namely, optimal construction of quantile sketches.
An $\varepsilon$ approximate quantile sketch receives a stream of items $x_1,\ldots,x_n$ and allows one to approximate the rank of any query up to additive error $\varepsilon 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$.

Optimal Quantile Approximation in Streams · Around

Built on

Selection and sorting with limited storage
J.I. Munro and M.S. Paterson · 1980
Earlier work this paper cites.
Random sampling techniques for space efficient online computation of order statistics of large datasets
Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay · 1999
Earlier work this paper cites.
Space-efficient online computation of quantile summaries
Michael Greenwald and Sanjeev Khanna · 2001
Earlier work this paper cites.
Medians and beyond: New aggregation techniques for sensor networks
Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri · 2004
Earlier work this paper cites.

Similar

A ( 1 / ε ) log ⁡ ( 1 / ε ) (1/\varepsilon)\log(1/\varepsilon) space lower bound for finding ε \varepsilon -approximate quantiles in a data stream
Regant YS Hung and Hingfung F Ting · 2010
Cited alongside, same era.
Mergeable summaries
Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff Phillips, Zhewei Wei, and Ke Yi · 2012
Cited alongside, same era.
Quantiles over data streams: An experimental study
Lu Wang, Ge Luo, Ke Yi, and Graham Cormode · 2013
Cited alongside, same era.

Then

Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro, on the Occasion of His 66th Birthday
Andrej Brodnik, Alejandro Lopez-Ortiz, Venkatesh Raman, and Alfredo Viola · 2013
Later among the works it cites.
A randomized online quantile summary in O ⁡ ( ( 1 / ε ) log ⁡ ( 1 / ε ) ) {O}((1/\varepsilon)\log(1/\varepsilon)) words
David Felber and Rafail Ostrovsky · 2015
Later among the works it cites.
Quantiles and equidepth histograms over streams
Michael B. Greenwald and Sanjeev Khanna · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…