API Snapshots: Java Core, C++ Core, Python, Memory, Pig, Hive,

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.