Theory of Computing
-------------------
Title     : A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words
Authors   : David Felber and Rafail Ostrovsky
Volume    : 13
Number    : 14
Pages     : 1-17
URL       : https://theoryofcomputing.org/articles/v013a014

Abstract
--------

A quantile summary is a data structure that approximates to $\epsilon$ 
error the order statistics of a much larger underlying dataset.

In this paper we develop a randomized online quantile summary for the
cash register data input model and comparison data domain model that
uses $O((1/\epsilon)\log(1/\epsilon))$ words of memory. This improves 
upon the previous best upper bound of 
$O((1/\epsilon)\log^{3/2}(1/\epsilon))$ by Agarwal et al. (PODS 2012).
Further, by a lower bound of Hung and Ting (FAW 2010) no deterministic 
summary for the comparison model can outperform our randomized summary
in terms of space complexity.  Lastly, our summary has the nice property
that $O((1/\epsilon)\log(1/\epsilon))$ words suffice to ensure that the
success probability is at least $1-\exp(-\poly{1/\epsilon})$.

A conference version of this paper appeared in the Proceedings 
of the 19th Internat. Workshop on Randomization and Computation
(RANDOM 2015).