Selected References on Quantile Sketches

• Zohar Karnin, Kevin Lang, Edo Liberty. Optimal Quantile Approximation in Streams. IEEE FOCS 2016.
• J.I. Munro and M.S. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, 12(3):315 – 323, 1980.
• Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. Random sampling techniques for space efficient online computation of order statistics of large datasets. SIGMOD 1999.
• Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries. In Proceedings of the 2001 ACM SIGMOD 2001
• Pankaj K. Agarwal, Graham Cormode, Zengfeng Huang, Jeff Phillips, Zhewei Wei, and Ke Yi. Mergeable summaries. In Proceedings of the 31st Symposium on Principles of Database Systems, PODS ’12
• Lu Wang, Ge Luo, Ke Yi, and Graham Cormode. Quantiles over data streams: An experimental study. In Proceedings of the 2013 SIGMOD
• In J. Gehrke M. Garofalakis and R. Rastogi, editors, In Data Stream Management: Processing High-Speed Data Streams. Springer, 2016.
• David Felber and Rafail Ostrovsky. A randomized online quantile summary in O((1/ε) log(1/ε))
• Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, Pavel Veselý. Relative Error Streaming Quantiles. https://arxiv.org/abs/2004.01668.
• Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, Pavel Veselý. Relative Error Streaming Quantiles. In PODS ‘21 Proceedings, 2021.