A Randomized Online Quantile Summary in $O((1/\varepsilon) \log(1/\varepsilon))$ Words

by David Felber and Rafail Ostrovsky

Theory of Computing, Volume 13(14), pp. 1-17, 2017

Bibliography with links to cited articles

[1]   Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff M. Phillips, Zhewei Wei, and Ke Yi: Mergeable summaries. ACM Trans. Database Syst., 38(4):26:1–26:28, 2013. Preliminary version in PODS’12. [doi:10.1145/2500128]

[2]   Graham Cormode: List of Open Problems in Sublinear Algorithms: Problem 2. https://sublinear.info/2.

[3]   David Felber and Rafail Ostrovsky: A randomized online quantile summary in O(1∕ε log(1∕ε)) words. In Proc. 19th Internat. Workshop on Randomization and Computation (RANDOM’15), pp. 775–785. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015. [doi:10.4230/LIPIcs.APPROX-RANDOM.2015.775]

[4]   Michael Greenwald and Sanjeev Khanna: Space-efficient online computation of quantile summaries. In 2001 ACM SIGMOD Internat. Conf. on Managment of Data, pp. 58–66. ACM Press, 2001. [doi:10.1145/375663.375670]

[5]   Regant Y. S. Hung and Hingfung F. Ting: An Ω(1∕ϵ log 1∕ϵ) space lower bound for finding ϵ-approximate quantiles in a data stream. In Proceedings of the 4th International Conference on Frontiers in Algorithmics (FAW’10), pp. 89–100. Springer, 2010. [doi:10.1007/978-3-642-14553-7_11]

[6]   Zohar Karnin, Kevin Lang, and Edo Liberty: Optimal quantile approximation in streams. In Proc. 57th FOCS, pp. 71–78. IEEE Comp. Soc. Press, 2016. [doi:10.1109/FOCS.2016.17, arXiv:1603.05346]

[7]   Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay: Approximate medians and other quantiles in one pass and with limited memory. In 1998 ACM SIGMOD Internat. Conf. on Managment of Data, pp. 426–435. ACM Press, 1998. [doi:10.1145/276304.276342]

[8]   Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay: Random sampling techniques for space efficient online computation of order statistics of large datasets. In 1999 ACM SIGMOD Internat. Conf. on Managment of Data, pp. 251–262. ACM Press, 1999. [doi:10.1145/304182.304204]

[9]   J. Ian Munro and Mike Paterson: Selection and sorting with limited storage. Theoret. Comput. Sci., 12(3):315–323, 1980. Preliminary version in FOCS’78. [doi:10.1016/0304-3975(80)90061-4]

[10]   Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri: Medians and beyond: New aggregation techniques for sensor networks. In Proc. 2nd Internat. Conf. Embedded Networked Sensor Systems (SenSys’04), pp. 239–249. ACM Press, 2004. [doi:10.1145/1031495.1031524, arXiv:cs/0408039]

[11]   Vladimir N. Vapnik and Alexey Ya. Chervonenkis: On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. [doi:10.1137/1116025]

[12]   Lu Wang, Ge Luo, Ke Yi, and Graham Cormode: Quantiles over data streams: experimental comparisons, new analyses, and further improvements. The VLDB Journal, 25(4):449–472, 2016. Preliminary version in SIGMOD’13. [doi:10.1007/s00778-016-0424-7]