**
A Randomized Online Quantile Summary in Ο(1/epsilon ^{∗}log (1/epsilon)Words
**

*
David Felber,
Rafail Ostrovsky
*

**
Abstract:
**

A quantile summary is data structure that approximates to epsilon-relative 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
Ο((1/epsilon)log(1/epsilon)) words of memory. This improves upon the previous best upper bound of Ο((1/epsilon)^{∧}( 3/2) by Agarwal et al. (PODS 2012).
Further, by a lower bound of Hung and Ting ( FWA 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 Ο((1/epsilon)log(1/epsilon)) words suffice to ensure that the success probability is 1−exp (−poly(1/epsilon)).

**comment:**
APPROX−2015 PP: 775−785

Fetch PDF file of the paper

Back to Publications List |