Rafail Ostrovsky - Publications

A Randomized Online Quantile Summary in Ο(1/epsilonlog (1/epsilon)Words

David Felber, Rafail Ostrovsky


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