This is part 2 of my series on calculating percentiles on streaming data.
The most famous algorithm for calculating percentiles on streaming data appears to be Greenwald-Khanna [GK01]. I spent a few days implementing the Greenwald-Khanna algorithm from the paper and I discovered a few things I wanted to share.
The insert operation is defined in [GK01] as follows:
- Find the smallest , such that , and insert the tuple , between and . Increment . As a special case, if is the new minimum or the maximum observation seen, then insert .
However, when I implemented this operation, I noticed via testing that there were certain queries I could not fulfill. For example, consider applying Greenwald-Khanna with to the sequence of values , and then apply QUANTILE(). This means that and . There is no that satisfies both and , as you can see below:
I believe the fundamental problem is that the definition of INSERT() fails to maintain the key invariant . To correct this issue, the Greenwald-Khanna INSERT() operation must be modified as follows:
- Find the smallest , such that , and insert the tuple , between and . Increment . As a special case, if is the new minimum or the maximum observation seen, then insert . Also, the first elements must be inserted with .
I found the above modification from Prof. Chandra Chekuri’s lecture notes for his class CS 598CSC: Algorithms for Big Data. I believe this modification will maintain the above invariant after insertions.
Banding in [GK01] refers to the grouping together of possible values of for purposes of merging in the COMPRESS operation. The paper defines banding as the following:
- BAND(, )
- For from 1 to , we let and we define to be the set of all such that . We define to simply be . As a special case, we consider the first observations, with = 0, to be in a band of their own. We will denote by the band of at time , and by all tuples (or equivalently, the values associated with these tuples) that have a band value of .
Here are some things I found when implementing banding:
- It is important to note that in the above refers to the base 2 logarithm of a number.
- I found it useful to construct an array, bands, at the beginning of the COMPRESS operation, such that bands is the band for the provided .
- I used a very large constant to denote the band of , as this made the tree-building operation simpler.
Compression in [GK01] is defined as follows:
- for from to do …
However, with this definition, it is possible for the first (0th) tuple to be deleted, which would then violate the following invariant of the summary data structure: “We ensure that, at all times, the maximum and the minimum values are part of the summary.”
Therefore, I modified COMPRESS() to go from to so that the first tuple is never deleted and the invariant is maintained.
- [GK01] M. Greenwald and S. Khanna. Space-efficient online computation of quantile summaries. In Proceedings of ACM SIGMOD, pages 58–66, 2001.