An error measured against the answer

The measurement this collection has already made, restated so that what follows is about a repair rather than about a complaint.

A Greenwald–Khanna summary at $\varepsilon = 0.01$ is asked for the 99.9th percentile of forty thousand heavy-tailed values. It answers 9,693.8, which is the largest value that ever arrived. The truth is 255.7.

Nothing was violated. Its promise is that the returned value’s rank is within $\varepsilon n$ of the rank asked for; the rank asked for is 39,960, the rank of 9,693.8 is 40,000, and the difference is 40 out of 40,000 — a rank error of a tenth of one per cent, well inside a promise of one per cent.

The value is off by a factor of thirty-eight.

The promise is measured against the wrong thing #

The diagnosis is arithmetic and it fits in two lines.

The promise is $\varepsilon n$ — a fraction of the whole stream. The quantile asked for is about the top $(1-q)n$ items. So the promise, expressed as a fraction of the thing the question is about, is

$$\frac{\varepsilon n}{(1-q)n} = \frac{\varepsilon}{1-q}$$

At the median that is $2\varepsilon$: the promise is twice as tight as the question is broad, which is fine. At $q = 0.99$ it is $100\varepsilon$. At $q = 0.999$ it is $1{,}000\varepsilon$, which at $\varepsilon = 0.01$ is ten times the entire tail — a permission to return any of the top ten thousandths of the data, and there are only forty of them.

The last row of the first column is exactly one hundred per cent, and it is exact for a reason: the answer is the maximum. Out in a tail there are few items per unit of value, so a tuple can absorb a wide stretch of the value range while absorbing few enough items to stay under the cap — and the value a merged tuple keeps is the right-hand one. Applied repeatedly across the top, the surviving representative of everything above a point is the largest thing seen.

More state does not help #

This is the part that makes it a defect in the shape of the promise rather than a budget problem.

Nine times the state, and the answer at $q = 0.999$ is the maximum every time. The reason is that the invariant caps every tuple’s uncertainty at $2\varepsilon n$ wherever it sits, so tightening $\varepsilon$ tightens the cap everywhere equally — and at $q = 0.999$ with $n = 40{,}000$ the tail is forty items, so the cap has to fall below forty before anything at all changes. At $\varepsilon = 0.005$ it is four hundred.

A structure whose accuracy parameter cannot reach the region being asked about is not inaccurate. It is answering a different question.

The repair is one line of the invariant #

Cormode, Korn, Muthukrishnan and Srivastava, in 2005, make the cap a function of where the tuple sits rather than a constant:

• $f(r, n) = 2\varepsilon n$ — Greenwald–Khanna. The same cap everywhere.
• $f(r, n) = 2\varepsilon (n - r)$ — high-biased. A tuple at rank $r$ may be uncertain by $\varepsilon$ times the mass above it, so the promise at $q$ is $\varepsilon(1-q)n$ and the tail is answered to within $\varepsilon$ of the tail.
• $f(r, n) = 2\varepsilon r$ — low-biased, the mirror image, for distributions whose interesting end is the small one.

Everything else — the tuple representation, the compression pass, the query — is unchanged. It is the same code with a different right-hand side, which is why the implementation here is one class with the rule as a parameter and the three settings share every line of machinery. A comparison built from two independent implementations would be a comparison of two authors as much as of two invariants.

One detail is not cosmetic: the high-biased cap goes to zero at the very top of the distribution, and a cap of zero means no tuple up there may ever merge, so the summary keeps one tuple per arrival and is not a summary. The floor here is one item — a tuple whose uncertainty is under a single item is exact, and there is nothing to be gained by demanding less.

Where the cap actually acts #

The invariant is worth watching in operation, because “make the cap a function of rank” hides where the work happens.

Every tuple carries three numbers: a value, $g$ — how many items it stands for — and $\delta$ — how much uncertainty there is about where the run it stands for begins. The compression pass walks the summary and merges a tuple into its right-hand neighbour whenever

$$g_i + g_{i+1} + \delta_{i+1} \le f(r_i, n)$$

so a large cap permits large merges and a small cap permits none. Under the uniform rule that inequality has the same right-hand side at every position, so the pass merges greedily and evenly and the summary ends up with tuples of roughly equal weight spread across the distribution — which is what the tuple plate above shows.

Under the high-biased rule the right-hand side falls to almost nothing at the top. A tuple sitting at rank $r$ near $n$ is allowed $2\varepsilon(n-r)$ of uncertainty, which for the last few hundred items is under one, so those tuples never merge with anything and the top of the distribution is stored item by item. That is not an approximation at all up there; it is a sorted list of the largest few hundred values, arrived at without anybody deciding how many to keep.

Which is a useful way to think about what the extra bits bought. The biased summary is a uniform summary of the bulk with an exact record of the extreme, and the crossover between the two regimes is wherever $2\varepsilon(n-r)$ falls below one — at $\varepsilon = 0.01$ and $n = 40{,}000$, the top fifty items.

And that is why more state cannot rescue the uniform rule. Tightening $\varepsilon$ moves a uniform summary’s resolution everywhere at once, which is the expensive way to buy resolution in one place. The biased rule buys it where it is needed and pays uniform prices everywhere else.

The floor is a choice and it is stated #

One number in the implementation is not in the published rule, and it deserves naming because a reader reproducing this would hit it in the first minute.

The high-biased cap is $2\varepsilon(n-r)$, which is zero at $r = n$. A cap of zero forbids every merge at the very top, and a summary that never merges at the top keeps one tuple per arrival there — but the top moves as the stream runs, so in practice it keeps one tuple per arrival, full stop, and is not a summary.

The floor used here is one item: no tuple’s cap is ever below one, on the grounds that a tuple whose uncertainty is under a single item is already exact and there is nothing to buy by demanding less. It is stated in the code and it is stated here because it is the difference between a structure that summarises and one that does not, and it is not in the invariant as published.

That is the same kind of gap as the half-bucket rule in the windowed histogram: a published estimate that is right in the regime the analysis is about and wrong at the boundary, where the structure is keeping things exactly and charging itself for uncertainty it does not have.

What it costs #

Eight times the state, on these streams: 55,680 bits against 7,104, 580 stored tuples against 74.

That is a real price and the shape of it is worth understanding rather than quoting. Greenwald–Khanna keeps $O(\frac{1}{\varepsilon}\log \varepsilon n)$ tuples because the cap is uniform and the summary can be uniform to match. The high-biased summary needs the tail resolved to $\varepsilon(1-q)n$ for every $q$, and summing that requirement across the distribution costs another logarithm.

But the comparison at equal $\varepsilon$ is the wrong one, because the two values of $\varepsilon$ mean different things. The honest comparison is at equal bits, and the plate above does it: at 14,144 bits Greenwald–Khanna answers the far tail with the maximum, and the biased summary at 12,800 bits answers it to within 0.8% of the tail. There is no budget in the range measured at which the uniform cap is the better use of the space, for a tail question.

For a median question it is the other way and by a wide margin, which is the sentence the plate above should not be allowed to hide. At $q = 0.5$ both are around half a per cent of the tail and one of them costs an eighth as much.

The other end, for free #

The same machinery with the cap mirrored answers the head of a distribution to a relative tolerance, which is the case where somebody cares about the fastest requests, the smallest orders, the shortest sessions.

Those are rank errors as a fraction of the stream, not of the head — the fair comparison at the low end, and the biased summary is between thirty and a hundred times tighter for a similar price. Both promises are legitimate; only one of them is about the question.

The rank error cannot see the values, and that is provable #

There is a stronger statement available about why the rank error was so misleading, and it is the one to carry away.

Greenwald–Khanna and the biased summary touch the data with <= and with nothing else. Every merge decision, every tuple boundary, every answer’s position in the sorted order is a function of the ranks alone. So relabel the values by any strictly increasing function — take the exponential of every one of them, say — and the structure that results is identical, tuple for tuple.

Measured: the rank errors are the same to the last digit.

A rank error is therefore distribution-free, and that is not a virtue. It means the number would have been the same for data with any spacing whatever, which is another way of saying it carries no information about the values — and the value error, on the same summary and the same ranks, moved by a factor of ten.

Both halves are asserted on every build, including the second, because a check that only required the rank errors to match would be passed by an implementation that had stopped answering.

Which promise a question wants #

It is worth being concrete about when each rule is the right one, because “relative error” is not automatically better and the plates above can be read as though it were.

A uniform cap is right when the quantiles are being used to describe a distribution: a box plot, a histogram’s breakpoints, a median and an interquartile range. Every part of the range matters roughly equally, resolution in the tail is worth no more than resolution in the middle, and the uniform rule delivers the most resolution per bit under exactly that valuation.

A biased cap is right when the question is about an extreme: a latency percentile in a service objective, a threshold above which an alert fires, the size of the largest orders. There, the middle of the distribution is not being asked about at all, and spending an equal share of the state on it is spending most of the state on nothing.

The distinction is not about the data and it is not about which structure is better implemented. It is about what the number is going to be used for, and it is the only thing that decides which of the two error bars is the honest one to print. A summary chosen without that decision having been made will be a uniform one, because that is the default in every library — and it will be asked for tail percentiles, because that is what quantile summaries are mostly deployed for.

Those two facts are in tension and nothing reports it. A structure meeting its stated guarantee, queried at the quantile it is usually queried at, returning a number that is wrong by a factor of thirty-eight, is what that tension produces.

A third rung: resolution only where it is asked for #

The essay presents two caps and there is a third, and it is the one a monitoring system actually wants — which makes its absence from the usual comparison worth noticing.

A biased summary promises relative accuracy at every quantile in the tail, and that is more than most callers need. A dashboard asks for a fixed set — the median, the 90th, the 99th, sometimes the 99.9th — and nothing else, ever. Resolution at $q = 0.9993$ is being paid for and never used.

The same invariant supports the narrower requirement. Give each target quantile its own tolerance and let the cap at rank $r$ be the smallest requirement any target imposes there:

$$f(r, n) = \min_{q \in T} \bigl(\text{what target } q \text{ needs at } r\bigr)$$

The cap is then small near each target and large everywhere between them, so the summary is dense at four places and sparse in the gaps. Its state is governed by the number of targets rather than by a logarithm of the stream, and on a set of four it is a fraction of what the fully biased summary costs.

Which reverses the essay’s cost argument for the case it is usually applied to. The eightfold price of relative accuracy is the price of relative accuracy everywhere; the price of relative accuracy at four stated quantiles is much less, and four stated quantiles is what the query pattern is.

The catch is that the target set has to be known when the summary is built, and a dashboard that later adds a percentile is asking a question the structure was not built to answer — it will still answer, at whatever resolution the cap happened to leave there, with no indication that this query is not one of the four. That is a real hazard and it is the same one every structure in this field has: the promise is fixed at construction and the query arrives later, and nothing in the answer says which of the two it was designed for.

The failure announces itself, and nothing listens #

The most striking row in this essay is the one where the answer is exactly the maximum, and it comes with a free diagnostic that no implementation reports.

If the value returned for a quantile equals the largest value the summary has seen, then the query landed in the tuple at the very top — the one whose rank interval runs to $n$ — and that tuple is the summary saying it has no resolution up there. The answer is not merely inaccurate; it is the structure’s way of saying no resolution up here.

Detecting it costs a comparison. Every summary in this family stores the maximum exactly, because the largest value is always a tuple boundary, so the check is: does the answer equal the stored maximum, and was $q$ less than one? If both, the query is past the structure’s resolution and the number should be reported as a lower bound rather than as an estimate.

Nothing does this, and the reason is the shape of the interface rather than any difficulty: a summary that returns one number has nowhere to put the caveat, and a caller that receives one number has nothing to branch on.

It is the same repair this collection keeps arriving at from different structures — report the bracket rather than the point — in the cheapest form it takes anywhere. Here it is not even a bracket: it is one boolean, computable from state the structure already holds, that separates the answer is 9,693.8 from the answer is at least 9,693.8 and this summary cannot say more.

What is not measured here #

Merging. Biased summaries merge, and the merge is where quantile summaries are usually deployed — one per shard, combined at query time. The merged structure’s guarantee is weaker than either input’s and this collection has not measured by how much.

The deterministic space bound. The tuple counts above are measurements of one implementation on particular streams. The published bound for the biased variant is $O(\frac{1}{\varepsilon}\log^2 \varepsilon n)$ against Greenwald–Khanna’s $O(\frac{1}{\varepsilon}\log \varepsilon n)$, and one extra logarithm is consistent with the eightfold gap seen here without being demonstrated by it.

And the compression pass here is the greedy one. Greenwald–Khanna’s banded variant reaches a better space bound while maintaining the same invariant and therefore the same guarantee. Both structures above use the plain greedy pass, so the comparison between them is fair and the absolute tuple counts are larger than the best known.