Greenwald-Khanna

An implementation of the Greenwald-Khanna algorithm.

References:

1. Michael B. Greenwald, Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, USA.
   • Link: ftp://ftp.cis.upenn.edu/pub/mbgreen/papers/sigmod01.pdf.gz
2. Michael B. Greenwald, Sanjeev Khanna, Quantiles and Equidepth Histograms over Streams, Chapter 2 of Part II of "Data Stream Management: Processing High-Speed Data Streams", ed. M. Garofalakis, J. Gehrke, and R. Rastogi, (Springer, ISBN 978-3-540-28607-3).
   • Link: https://www.cis.upenn.edu/~mbgreen/papers/stream-chapter.pdf
3. Michael B. Greenwald, Sanjeev Khanna, Power-conserving computation of order-statistics over sensor networks, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France. (This reference was used for the merge algorithm).
   • Link: https://www.cis.upenn.edu/~mbgreen/papers/pods04.pdf
4. Shun Yan Cheung's class notes from Emory University:
   • http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/08-Quantile/Greenwald.html
   • http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/08-Quantile/Greenwald2.html
   • http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/11-Window/Greenwald-window.html