Gk

Calculating Percentiles on Streaming Data Part 8: Parameterizing Algorithms on Measurement Type

Calculating Percentiles on Streaming Data Part 8: Parameterizing Algorithms on Measurement Type
This is part 8 of my series on calculating percentiles on streaming data. As mentioned in part 6 of this series, I have published a C++ and JavaScript library which implements a number of streaming percentile algorithms on GitHub at https://github.com/sengelha/streaming-percentiles. Versions 1.x and 2.x of the C++ library required all measurements to use the type double, and usage of the algorithms looked something like this: #include <stmpct/gk.hpp> double epsilon = 0.

Calculating Percentiles on Streaming Data Part 7: Cormode-Korn-Muthukrishnan-Srivastava

Calculating Percentiles on Streaming Data Part 7: Cormode-Korn-Muthukrishnan-Srivastava
This is part 7 of my series on calculating percentiles on streaming data. In 2005, Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava published a paper called Effective Computation of Biased Quantiles over Data Streams [CKMS05]. This paper took the Greenwald-Khanna algorithm [GK01] and made the following notable changes: Generalized the algorithm to work with arbitrary targeted quantiles, where a targeted quantile is a combination of a quantile $\phi$ and a maximum allowable error $\epsilon$.