Quantile Summaries: Greenwald-Khanna Bounds and the KLL Compactor

A quantile query returns the value at a given rank: the median is the value at rank $n/2$, the 99th percentile the value at rank $0.99n$. Unlike a count or a sum, a quantile depends on the ordering of the values, and ordering is exactly what a stream destroys as it delivers elements one at a time. A summary must therefore retain enough about the distribution to place an unseen value between two stored ones, and the question is how little that can be.

Two families of answers exist. Greenwald-Khanna is deterministic and gives a rank-error guarantee per item. The KLL compactor is randomised, uses less space for the same guarantee, and its constants make it the construction to prefer when memory is the binding constraint. Both are exact in a specific sense: they return a value that is actually present in the stream, at a rank close to the one requested.

Ranks, not values

The error model is the first thing to fix, because quantile summaries are usually specified with a rank error rather than a value error.

A summary is $\varepsilon$-approximate if for every query rank $r$, it returns a value $v$ whose true rank $R(v)$ satisfies $|R(v) - r| \leq \varepsilon n$. The returned value is one of the stream’s elements — the summary does not interpolate — so the guarantee is about position, not about distance. An $\varepsilon$ of 0.01 means the returned value is within one percent of the stream’s ranks of the requested one; for a million elements that is ten thousand ranks of slack.

The distinction matters because value-space error is unbounded for heavy-tailed data. A stream of a million values where 999,000 are near zero and 1,000 are near a billion has a median that is essentially zero and a 99.9th percentile near a billion. An algorithm that guarantees a small absolute value error is either impossible or trivially satisfied by returning zero for everything; the rank formulation is scale-free and is the one that composes.

Greenwald-Khanna achieves $O((1/\varepsilon)\log(\varepsilon n))$ space, and its guarantee holds for every rank at once with no failure probability. The later randomised work shows that the logarithm can be removed once determinism is given up, which is what makes the deterministic bound a statement about determinism rather than about the problem.

The tuple invariant

The summary stores a sorted sequence of tuples $(v_i, g_i, \Delta_i)$. The value $v_i$ is an element observed in the stream; $g_i$ is the number of elements between $v_{i-1}$ and $v_i$ that are not stored; $\Delta_i$ is an upper bound on the uncertainty in $v_i$‘s rank.

Define $r_{\min}(i) = \sum_{j \leq i} g_j$ and $r_{\max}(i) = r_{\min}(i) + \Delta_i$. These bracket the true rank of $v_i$: $r_{\min}(i) \leq R(v_i) \leq r_{\max}(i)$. The invariant the algorithm maintains is

$$ g_i + \Delta_i ;\leq; \lfloor 2\varepsilon n \rfloor $$

for every stored tuple, where $n$ is the number of elements seen so far. A tuple with a large $\Delta$ is one whose rank is poorly known, and the invariant caps the total uncertainty at $2\varepsilon n$.

Insertion preserves the invariant. A new value $v$ is placed between $v_{i-1}$ and $v_i$ with $g = 1$ and $\Delta = \lfloor 2\varepsilon n \rfloor - 1$; since $v$ has just been observed, its rank is known exactly to within the elements already elided, and the choice of $\Delta$ is the tightest value the invariant allows.

Compression restores the invariant when it is violated by growth. A merge operation takes two adjacent tuples $(v_i, g_i, \Delta_i)$ and $(v_{i+1}, g_{i+1}, \Delta_{i+1})$ and replaces them with a single tuple at $v_{i+1}$ whose $g$ is $g_i + g_{i+1}$ and whose $\Delta$ is $\Delta_{i+1}$. The merged tuple’s uncertainty absorbs the elided tuple’s count, so the invariant $g + \Delta \leq 2\varepsilon n$ is what decides whether a merge is permitted. The algorithm repeatedly merges the pair with the smallest $g_i + g_{i+1} + \Delta_{i+1}$ until no violation remains, which is the band-merging strategy: tuples are grouped into bands by the magnitude of $\Delta$, and merges happen preferentially within a band.

Querying a rank $r$ walks the tuples accumulating $r_{\min}$ until it passes $r$, and returns the previous value. The returned value’s true rank is within $\varepsilon n$ of $r$ because the accumulated uncertainty of any tuple it passes is bounded by the invariant.

Why the space is logarithmic in the stream

The space bound follows from counting tuples per band. A band is a range of $\Delta$ values: band $b$ holds tuples with $\Delta$ in $[2^{b-1}, 2^b)$. Within a band, the invariant $g + \Delta \leq 2\varepsilon n$ and the requirement that no two tuples in the same band be mergeable together force the $g$ values to grow geometrically, so a band holds at most $O(\log(\varepsilon n))$ tuples. There are $O(\log(\varepsilon n))$ bands, and the first band — tuples with small $\Delta$ — is capped by the $1/\varepsilon$ term because a small $\Delta$ implies a small $g$, and total $g$ sums to $n$.

The product of the two counts is the space bound, and the $\log$ factors are the reason the structure is practical: for $\varepsilon = 0.001$ and a stream of a billion, the space is on the order of tens of thousands of tuples rather than millions.

import bisect

class GK:
    def __init__(self, epsilon):
        self.eps = epsilon
        self.n = 0
        self.v, self.g, self.d = [], [], []

    def insert(self, x):
        self.n += 1
        i = bisect.bisect_left(self.v, x)
        if i > 0 and i < len(self.v):
            delta = max(0, int(2 * self.eps * self.n) - 1)
        else:
            delta = 0            # min or max: rank is exact
        self.v.insert(i, x)
        self.g.insert(i, 1)
        self.d.insert(i, delta)
        self._compress()

    def _compress(self):
        limit = int(2 * self.eps * self.n)
        i = len(self.v) - 1
        while i >= 1:
            # merge tuple i-1 into i when the invariant allows
            if self.g[i - 1] + self.g[i] + self.d[i] <= limit:
                self.g[i] += self.g[i - 1]
                del self.v[i - 1], self.g[i - 1], self.d[i - 1]
            i -= 1

The listing merges from the top down, which is simpler than band merging but not equivalent to it. The guarantee survives, because any pair whose combined $g + \Delta$ fits under the limit may be merged; the choice of pair affects only the space constant. The paper specifies band-based selection precisely because it keeps the constant small, so a naive left-to-right or right-to-left pass leaves more tuples than the analysis promises.

Randomised compaction and the KLL bound

The KLL summary replaces the deterministic tuple machinery with a hierarchy of buffers. Level $h$ holds up to $k_h$ items, and when a level overflows, its items are sorted, and either the even-indexed or the odd-indexed half is promoted to level $h+1$ while the other half is discarded — the choice is made at random for each compaction. The item count at each level therefore drops by a factor of two per promotion, and a query interpolates the rank of an item from its level: an item that has been promoted $h$ times stands for $2^h$ stream elements.

The error analysis is a sum over levels. Each compaction introduces rank uncertainty proportional to the number of items promoted, and the total uncertainty is the sum of these over the levels an item passes through. With geometric capacities $k_h = k/c^{H-h}$, the total error is $O(1/k)$ with high probability, and the space is $O(1/\varepsilon)$ items — no $\log$ factor at all, which is the improvement over Greenwald-Khanna.

The randomised step is what removes the logarithm. In the deterministic scheme the tuple structure must record where each elided element went, which is the source of the $\log(\varepsilon n)$ factor. KLL discards that information and relies on the random choice of which half to keep to make the rank error behave like a sum of independent random variables. A union bound over levels then gives a high-probability guarantee, at the cost of a failure probability that Greenwald-Khanna does not have.

The practical consequence is a smaller constant. KLL’s space is $O(1/\varepsilon)$ items with no logarithmic factor in $n$, so the summary size is fixed once $\varepsilon$ is chosen, and its compaction is a sort of a small buffer followed by a separable stride copy, which maps well onto sequential memory. The cost is that the guarantee is probabilistic and the summary is not deterministic — two runs over the same stream produce different summaries, both correct with high probability.

Merging, and the error that accumulates

Both summaries are mergeable, and both lose accuracy on merge.

Merging two Greenwald-Khanna summaries requires combining the tuple sequences and then compressing, with the invariant evaluated against the combined $n$. The merged summary’s error is bounded by the sum of the two input errors plus the error introduced by the compression pass. The Agarwal et al. analysis gives a bound of $\varepsilon_1 + \varepsilon_2 + \varepsilon_{\text{merge}}$, and the practical rule is that merging $p$ summaries in a tree of depth $\log p$ yields error $O(\varepsilon \log p)$.

KLL merges more gracefully: the level structure of two summaries can be combined by merging corresponding levels and compacting, and the error bound grows with the number of merges in a way that is tighter than the deterministic version, because the random choices in each input are independent and their errors add in variance rather than in the worst case.

The asymmetry has a design consequence. A single-node summary can use Greenwald-Khanna for its determinism; a distributed aggregation over many nodes should use KLL, or should allocate $\varepsilon$ per node divided by the expected merge depth, so that the accumulated error stays within the global target.

Failure modes that the bound does not mention

Five things break in practice.

Duplicate values. Both algorithms handle ties by insertion order, so a stream of a million copies of one value produces a summary whose tuples all hold that value; the query walk then returns it for every rank, which is the right answer. The hazard is an implementation that deduplicates values before insertion to save space: a hash is not order-preserving, so rank queries over the deduplicated set answer a question about a different input.

The error is relative to $n$, which changes. A summary built with $\varepsilon = 0.01$ over a stream that later grows by a factor of a hundred has an effective error of one percent of the current $n$ only if the summary is rebuilt; a summary that was compressed under the old $n$ carries tuples with $\Delta$ values appropriate to the old scale. Streaming implementations that never stop growing must re-evaluate the invariant against the current $n$, which the algorithm does, but the space then grows as $\log n$ — the bound is not a constant.

Quantiles of a window are not quantiles of the stream. Subtracting two quantile summaries does not produce the quantile summary of the difference. The tuple structure records rank information tied to a specific prefix of the stream, and removing a prefix requires re-deriving it, which is not a merge operation. Windowed quantiles need a different structure, such as the bucket-based approach in sliding windows applied to a fixed set of rank boundaries, or a periodic rebuild.

Value-space queries do not compose. Asking for the fraction of elements below a threshold $t$ is a rank query at the rank of $t$, and it is answerable; asking for the value at a given rank is answerable; asking for the count of elements in an interval $[a, b]$ requires two rank queries, and the difference of two $\varepsilon$-approximate ranks has error $2\varepsilon n$, not $\varepsilon n$. The errors add, and a summary sized for $\varepsilon$ precision on single quantiles gives $2\varepsilon$ on interval counts.

The guarantee is simultaneous, and that is unusual. A Greenwald-Khanna summary is $\varepsilon$-approximate for every rank at once, because the bound is a statement about the tuple invariant rather than about a single walk. KLL’s failure probability is stated per queried rank, so a caller who wants $q$ fixed ranks answered reliably has to divide the failure budget across them. That asymmetry is what makes the deterministic summary usable for plotting an entire distribution from one pass.

The lower bound and what it rules out

The Karnin–Lang–Liberty result shows that any summary achieving rank error $\varepsilon n$ with constant probability needs $\Omega(1/\varepsilon)$ space, and that KLL attains it. Greenwald-Khanna’s $\log(\varepsilon n)$ factor is therefore not a defect of that algorithm but the price of determinism: a deterministic summary cannot use the random half-selection that removes the logarithm.

That closes the problem in an unusually clean way. Space $O(1/\varepsilon)$ is necessary and sufficient, up to constants and the $\log$ for determinism, and no further asymptotic improvement is available. What remains is the engineering: constants, merge behaviour, and the choice between a summary that is always right within its bound and one that is right with high probability. Compared with the sketches that answer aggregate questions — HyperLogLog for presence, Tug-of-War for concentration — quantile summaries are expensive per unit of information, because ordering carries more information than any aggregate.