pdf icon
Volume 13 (2017) Article 14 pp. 1-17
APPROX-RANDOM 2015 Special Issue
A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words
Received: November 18, 2015
Revised: May 16, 2017
Published: November 14, 2017
Download article from ToC site:
[PDF (328K)] [PS (2038K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: algorithms, data structures, data stream, approximation, approximation algorithms, online algorithms, randomized, summary, quantiles, RANDOM
Categories: algorithms, data structures, data stream, approximation algorithms, online algorithms, randomized, summary, quantiles, short, RANDOM, APPROX-RANDOM 2015 special issue
ACM Classification: F.2.2, E.1, F.1.2
AMS Classification: 68W20, 68W25, 68W27, 68P05

Abstract: [Plain Text Version]

$ \newcommand{\ep}{\varepsilon} \newcommand{\poly}{\text{poly}} $

A quantile summary is a data structure that approximates to $\ep$ 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/\ep)\log(1/\ep))$ words of memory. This improves upon the previous best upper bound of $O((1/\ep)\log^{3/2}(1/\ep))$ 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/\ep)\log(1/\ep))$ words suffice to ensure that the success probability is at least $1-\exp(-\poly(1/\ep))$.

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