The error that is on the rank

The median of a stream cannot be computed in small space, and the reason is worth stating before anything is built on top of it.

To know the median exactly, a one-pass algorithm must be able to distinguish streams whose medians differ, and there are far too many of those to encode in a summary. The standard result is that an exact $q$-quantile over $n$ items needs $\Omega(n)$ space in one pass — the whole stream, essentially — which is the same memory-state argument that floors exact distinct counting.

So the question becomes what to give up. And there are two entirely different things to give up, which is what makes quantiles different from everything else in this field.

Two things a quantile summary could promise #

A value guarantee. The number returned is within $\varepsilon$ of the true $q$-quantile. Within $\varepsilon$ of what, though — the value is a latency in milliseconds or a price in pounds, and a summary that has not seen the whole stream does not know its scale. Any such promise is relative to a range the structure would have to learn, and a stream whose values arrive in increasing order can move that range arbitrarily at the last moment.

A rank guarantee. The number returned is a value whose true rank is within $\varepsilon n$ of $qn$. This is a promise about position in the sorted order, it needs no knowledge of the values’ scale, and it is achievable in a few tuples.

Every quantile summary in use makes the second promise. This essay is about how, and the next one is about the gap between the two, which is larger than almost anybody expects.

The structure #

Greenwald and Khanna’s summary is a sorted list of triples $(v_i, g_i, \Delta_i)$.

• $v_i$ is a value that actually occurred in the stream.
• $g_i$ is how many items this tuple absorbed — the number of stream elements whose rank falls in the gap between the previous stored value and this one.
• $\Delta_i$ is the uncertainty this tuple inherited when it was created.

From those, the rank of $v_i$ is known to lie in $[r_i, r_i + \Delta_i]$ where $r_i = \sum_{j \le i} g_j$. The invariant maintained at all times is

$$g_i + \Delta_i \le 2\varepsilon n$$

and it is the whole of the guarantee. A query for $q$ walks the list and returns the first stored value whose rank interval sits inside $[qn - \varepsilon n, qn + \varepsilon n]$; the invariant is exactly what makes such a tuple always exist.

Insertion puts a new triple with $g = 1$ and $\Delta = \lfloor 2\varepsilon n \rfloor - 1$ at its sorted position — a new item’s rank is unknown to within the current tolerance, and that is what the $\Delta$ records. Every $1/(2\varepsilon)$ insertions a compress pass merges each tuple into its right-hand neighbour wherever doing so keeps the invariant, which is where the structure gets its size back.

The whole structure, on two hundred items #

Nine tuples summarising two hundred uniform values at $\varepsilon = 0.1$, after forty compress passes:

Everything the summary knows is in that table. The invariant caps $g + \Delta$ at $2\varepsilon n = 40$ and the largest entry is the 694 row at 38. The first and last rows have $\Delta = 0$ because the minimum and the maximum have exactly known ranks — a new minimum’s rank is 1 whatever else arrives.

Asking for the median walks down the rank column looking for an interval inside $[100 - 20,\; 100 + 20]$, finds the 507 row at $[108, 108]$, and returns 507 against a true median of 469: a rank error of 4.5%, inside the promised 10%, from a structure holding nine numbers.

Two features of that table are worth naming. The 834 row has $g = 1$ and $\Delta = 34$: a value that arrived recently, absorbed nothing, and inherited a large uncertainty because the summary was already coarse when it appeared. And the 694 row is the reverse — it has absorbed fifteen items and carries 23 of inherited slack, which together sit just under the cap. The two numbers are doing different jobs and merging them into one would destroy the guarantee, which is exactly what the rejected implementation in the gate does.

The guarantee is deterministic, and that changes what a test means #

Everything else in this field is randomised. A Count-Min sketch fails with probability $e^{-d}$; a HyperLogLog is within $1.04/\sqrt{m}$ typically; the tug-of-war estimator has a variance. For all of those, a single bad answer is a sample from a distribution and proves nothing.

Greenwald–Khanna has no randomness in it at all. There is no seed, no hash, and no failure probability: a single query anywhere outside $\varepsilon n$ is a defect in the implementation, not an unlucky draw.

That makes the check sharper than any other in this phase. The gate runs four distributions at three tolerances each and requires every one of the resulting queries to be inside its promise, and a version of the compress pass that drops the inherited $\Delta$ from its merge condition is required to fail it — which it does, answering a query 95% of the stream away from where it was asked.

The worst error is inside the promise in every row and close to it in several, which is the right shape: a structure whose measured error was ten times inside its promise would be one holding more state than it needed to.

The size, measured against the bound #

The published bound on the summary’s size is $O\!\left(\frac{1}{\varepsilon}\log(\varepsilon n)\right)$ tuples, for the banded version of the compress pass. This implementation uses the plain greedy pass, which maintains the same invariant and therefore the same guarantee, and whose size is nobody’s theorem. So it is measured.

Over an eightyfold range of stream lengths the summary does not grow. The bound permits growth by a factor of nearly three across that range and none appears; the size sits at about $0.77/\varepsilon$ throughout.

Two honest remarks about that. It is a measurement on four streams and not a theorem — the logarithmic term is a worst-case statement and an adversarial arrival order is exactly what would produce it. And it is the same shape this site has recorded twice before: a bound correct and loose, and a formula whose assumption is false and whose prediction holds. The right conclusion is that the constant is what a practitioner should size against and the logarithm is what they should not be surprised by.

For scale: keeping all 20,000 values at 32 bits each is 640,000 bits, and the summary at $\varepsilon = 0.01$ is 7,392. Eighty-seven times smaller, for answers guaranteed to sit within 1% of the stream from where they were asked for.

Against a uniform sample of the same size #

The obvious competitor is not another deterministic structure but a sample: keep $k$ items by reservoir sampling, sort them at query time, and report the sample’s own $q$-quantile. It is simpler, it is one value per slot rather than a value and two counters, and its rank error is a random variable of order $1/\sqrt{k}$.

Matched on bits — the sample given three slots for every tuple the summary holds, because a tuple is three times the size — on 20,000 log-normal values:

The deterministic summary wins at every size, and the margin widens as the state grows — which is the $1/\varepsilon$ against $1/\sqrt{k}$ exchange rate showing up as an increasing ratio. At the largest size measured it is nearly four times more accurate on the same bits.

That is the ordering on the promise both structures are making. It is not the ordering on everything, and the reversal is the subject of the next essay.

What compress is spending #

The compress pass is where the size comes from and it is worth being precise about what it gives away.

Merging tuple $i$ into tuple $i+1$ means forgetting that a value near $v_i$ ever occurred and adding its $g$ to its neighbour’s. The neighbour’s rank interval widens by that much. The pass performs the merge whenever $g_i + g_{i+1} + \Delta_{i+1} \le 2\varepsilon n$ — that is, whenever the widened interval still fits under the cap — and refuses otherwise.

So the cap is a budget spent on forgetting, and the two things that make it grow are the two things in the invariant. It is proportional to $n$, so a longer stream can afford coarser tuples; and it is proportional to $\varepsilon$, so a laxer promise buys them directly. That is why the summary’s size does not grow with $n$ in the measurement above: as the stream lengthens the budget lengthens with it, and the compress pass has more room to merge at exactly the rate new items arrive.

The version in the paper is more careful. It groups tuples into bands by when they were created and merges only within a band, which prevents a young tuple from absorbing an old one whose slack is about to become useful, and it is what the $\log(\varepsilon n)$ in the bound is about. This implementation does not do that, which is why its size is measured rather than quoted — and on these streams the simpler pass costs nothing measurable.

Where the gap is widest #

Every plate so far has been drawn at the middle of the distribution or three-quarters of the way up it, and that is the polite part of the curve. The quantile anybody actually asks a summary about is the ninety-ninth, and the ninety-ninth percentile is where the curve is steepest in rank and flattest in value — which is exactly the geometry that turns a narrow horizontal band into a wide vertical one.

Nothing has gone wrong. The summary is inside its guarantee at every point on that plate, and the guarantee is the one the structure was chosen for. What has happened is that the quantity the promise is denominated in and the quantity the reader cares about have come apart by a factor of six hundred, and no amount of tightening $\varepsilon$ closes a gap that is a property of the distribution rather than of the summary.

The pair is the argument in one image. A rank promise is a promise about a position in a sorted list, and converting it into a promise about a number requires the slope of the distribution at that position — which the summary does not have and the reader does not usually ask for. A latency dashboard quoting p99 ± 2% is quoting the first and being read as the second.

One more asymmetry belongs with the merge arithmetic, because it decides which direction a fleet should be assembled in. Merging is associative in its error as well as in its result — the tolerances add however the tree is shaped — so nothing is recovered by balancing it, and a chain of a hundred pairwise merges ends in the same place as a balanced tree of the same hundred summaries. That is unlike almost every other combination in this collection, where the shape of the tree is the whole subject, and the reason is that there is no cost being amortised here: the merge is exact bookkeeping over a budget that was spent when the tuples were made.

Why it is not a linear sketch #

Everything else in this phase is a sum of updates, and this is not.

A quantile summary’s state is a set of representative values with counts, and merging two of them is a real operation with a real cost in accuracy: the merged summary’s $\varepsilon$ is the sum of the two inputs’ tolerances, not the smaller of them. There is no subtraction at all — a deletion has no meaning for a structure whose tuples are order statistics, and the model this summary declares itself valid in is the cash register alone.

That is not a defect of this construction. It is a consequence of the question: Count-Min’s cells are sums and sums subtract, while a rank is a fact about an ordering and orderings do not.

Every quantile at once, with no union bound #

The table above answers eight quantiles from one summary of 77 tuples, and the guarantee covers all eight. That is worth stopping on, because for every randomised structure in this field it would be false as stated.

A Count-Min sketch promises that a query is within its error with probability $1 - \delta$. Ask it a thousand questions and the probability that all thousand are good is not $1 - \delta$; it is nearer $1 - 1000\delta$, and recovering the original confidence means shrinking $\delta$ by a factor of a thousand, which costs $\log 1000$ more rows. That is the guarantee that is per query, and the correction is a real cost paid in state by anybody whose dashboard asks a lot of questions.

Greenwald–Khanna’s invariant is a property the structure holds at all times, not an event that might fail. Every stored tuple satisfies $g + \Delta \le 2\varepsilon n$ simultaneously, so every query that walks the list finds a tuple inside its band, so all $q$ from 0 to 1 are answered within $\varepsilon n$ at once and there is nothing to correct for. A summary that answers eight quantiles is the same size as one that answers one, and the same size as one asked ten thousand.

The consequence is a reversal of the ordering in the comparison table above, and it is not a small one. Matched on bits and on a single query the deterministic summary was about four times more accurate than a sample. Matched on bits and on a workload — every percentile from the 50th to the 99.9th, which is exactly what a latency dashboard asks for — the randomised competitor has to widen its promise or grow, and the deterministic one does neither. The structure is at its best precisely where it is used.

It also changes what the gate can assert, which is why the checks here are sharper than elsewhere in this field. A test of a randomised structure can only ever measure a rate and compare it against a distribution. A test of this one can take every quantile it feels like asking, on every distribution it can generate, and require all of them to be inside the band — one violation anywhere is a defect. That is the difference between a check that estimates and a check that refutes, and it is available here only because the promise is not statistical.

Merging costs more than the promise suggests #

The last section noted that the summary is not a linear sketch and that merging two of them adds their tolerances. That sentence has a consequence large enough to decide architectures, so it is worth following through.

Merging summaries with tolerances $\varepsilon_1$ and $\varepsilon_2$ gives one valid at $\varepsilon_1 + \varepsilon_2$. Combine $m$ machines’ summaries pairwise up a tree and the tolerances add at every level, so $m$ summaries each built at $\varepsilon$ produce a final answer guaranteed only at $m\varepsilon$. To land at a stated $\varepsilon$ across the fleet, every node must build at $\varepsilon/m$.

The size of a summary goes as $1/\varepsilon$, so each node’s summary grows linearly in the number of nodes, and the total state across the fleet grows as $m^2/\varepsilon$. A hundred machines each holding a hundred times more than they would alone is ten thousand times the state of one, which is the point at which a merge-based deployment stops being a summary at all.

Nothing about that is a flaw in the invariant; it is what an additive error does under composition. It is also the reason the structures that get deployed across fleets are not this one. Summaries whose merge error grows like $\sqrt{\log m}$ rather than like $m$ exist, are the reason the mergeable-summary literature exists, and are not implemented in this collection — so the comparison above stops at the arithmetic and does not put a number on the alternative, on the same principle as the quoted bound in the section above it.

The practical reading is a rule about where to put the boundary. A summary is cheap when one process sees the whole stream and expensive the moment the stream is split, and the cheapest repair is usually not a better merge but a different topology: route by key so that each key’s stream is whole somewhere, and the summaries never have to be combined at all. That is the same answer the windowed count arrives at from a different obstruction, and two structures reaching one deployment rule by unrelated routes is worth more than either of them reaching it alone.

What it does not do #

Three limits worth stating, all of them the kind of thing a reader will otherwise discover later.

It answers about the stream it saw and not about a window of it. Quantiles over the last hour need the machinery two essays on and this structure has none of it.

It cannot be told the quantile in advance and get smaller. The summary is built to answer any $q$ to within $\varepsilon$, and knowing that only $q = 0.99$ will ever be asked does not shrink it, because the compress pass has no way to spend its tolerance unevenly. Structures that do exist — biased quantile summaries, which give relative rather than absolute rank error — are a different construction and are not implemented here.

The tolerance is on the rank and the answer is a value. Which is the whole of the next essay and the reason this one stops here.