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 |