This is part 2/8 of my Calculating Percentiles on Streaming Data series.

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.

Insert Operation

The insert operation is defined in [GK01] as follows:

INSERT($v$)

Find the smallest $i$, such that $v_{i-1} \leq v < v_i$, and insert the tuple $ t_x = (v_x, g_x, \Delta_x) = (v, 1, \lfloor 2 \epsilon n \rfloor) $, between $t_{i-1}$ and $t_i$. Increment $s$. As a special case, if $v$ is the new minimum or the maximum observation seen, then insert $(v, 1, 0)$.

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 $\epsilon = 0.1$ to the sequence of values ${11, 20, 18, 5, 12, 6, 3, 2}$, and then apply QUANTILE($\phi = 0.5$). This means that $r = \lceil \phi n \rceil = \lceil 0.5 \times 8 \rceil = 4$ and $\epsilon n = 0.1 \times 8 = 0.8$. There is no $i$ that satisfies both $r – r_{min}(v_i) \leq \epsilon n$ and $r_{max}(v_i) – r \leq \epsilon n$, as you can see below:

I believe the fundamental problem is that the definition of INSERT($v$) fails to maintain the key invariant $\textrm{max}_i(g_i + \Delta_i) \leq 2 \epsilon n$. To correct this issue, the Greenwald-Khanna INSERT($v$) operation must be modified as follows:

INSERT($v$)*

Find the smallest $i$, such that $v_{i-1} \leq v < v_i$, and insert the tuple $t_x = (v_x, g_x, \Delta_x) = (v, 1, \lfloor 2 \epsilon n \rfloor – 1)$, between $t_{i-1}$ and $t_i$. Increment $s$. As a special case, if $v$ is the new minimum or the maximum observation seen, then insert $(v, 1, 0)$. Also, the first $1/(2 \epsilon)$ elements must be inserted with $\Delta_i = 0$.

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 $1/(2 \epsilon) $ insertions.

Band Construction

Banding in [GK01] refers to the grouping together of possible values of $\Delta$ for purposes of merging in the COMPRESS operation. The paper defines banding as the following:

BAND($\Delta$, $2 \epsilon n$)

For $\alpha$ from 1 to $\lceil \log 2 \epsilon n \rceil$, we let $p = \lfloor 2 \epsilon n \rfloor$ and we define $\mathrm{band}_\alpha$ to be the set of all $\Delta$ such that $p – 2^\alpha – (p \mod 2^\alpha) < \Delta \leq p – 2^{\alpha – 1} – (p \mod 2^{\alpha – 1})$. We define $\mathrm{band}_{0}$ to simply be $p$. As a special case, we consider the first $1/2\epsilon$ observations, with $\Delta$ = 0, to be in a band of their own. We will denote by $\mathrm{band}(t_i, n)$ the band of $\Delta_i$ at time $n$, and by $\mathrm{band}_\alpha(n)$ all tuples (or equivalently, the $\Delta$ values associated with these tuples) that have a band value of $\alpha$.

Here are some things I found when implementing banding:

• It is important to note that in the above $\log$ 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[$\Delta$] is the band for the provided $\Delta$.
• I used a very large constant to denote the band of $\Delta = 0$, as this made the tree-building operation simpler.

Compress

Compression in [GK01] is defined as follows:

COMPRESS()

for $i$ from $s – 2$ to $0$ 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 $s – 2$ to $1$ so that the first tuple is never deleted and the invariant is maintained.

References

• [GK01] M. Greenwald and S. Khanna. Space-efficient online computation of quantile summaries. In Proceedings of ACM SIGMOD, pages 58–66, 2001.