The digest that promises nothing

Every structure in this collection has been given a claim and a test its claim could fail. The t-digest has no claim.

That is not a criticism and it is not an omission by its author. Ted Dunning’s papers are explicit about it: the argument for the structure is that its centroid sizes are bounded by a stated scale function, and that this is observed to produce small relative error at the tails. There is no theorem. There is a rule about sizes and a body of empirical evidence, and the structure is, by a wide margin, the most deployed quantile summary there is.

So the only thing to do with it here is measure it.

The scale function is the whole structure #

A t-digest holds centroids: pairs of a mean and a count. A new batch of values is sorted and merged into the existing centroids left to right, and a centroid is allowed to keep absorbing while its span in a transformed coordinate stays under one:

$$k(q) = \frac{\delta}{2\pi} \arcsin(2q - 1)$$

The arcsine is the mechanism and it is worth understanding directly. Its derivative is $\frac{\delta}{2\pi\sqrt{q(1-q)}}$ — small near $q = \tfrac12$, unbounded at either end. So a centroid in the middle may absorb a wide stretch of the distribution before its $k$-span reaches one, and a centroid at $q = 0.999$ may absorb almost nothing.

That is where the tail accuracy comes from, and it comes without anybody stating an $\varepsilon$. There is one parameter, $\delta$, and it sets the total number of centroids to roughly $\delta$ — sixty-two at $\delta = 100$ in the measurements here, which at a mean and a count each is 5,952 bits.

Measured, it is good #

Rank error as a fraction of the tail it is about, averaged over eight independent streams of forty thousand heavy-tailed values:

It is better than the structure with the proven bound, at fewer bits, at every quantile. And it is far worse than the structure whose bound is stated relative to the tail, at a ninth of that structure’s state.

That is the honest ranking and it does not fit a story in which guarantees are what matter. A guarantee is a floor under the behaviour, not a description of it, and Greenwald–Khanna’s floor is low enough at a tail percentile that a structure with no floor at all can walk under it.

What it has instead of a promise, and where that runs out #

The scale function does imply something, and it is worth deriving because what it implies is not what the structure is usually described as delivering.

Setting $\Delta k = 1$ gives $\Delta q = 2\pi\sqrt{q(1-q)}/\delta$, so the rank error at quantile $q$ is proportional to $\sqrt{q(1-q)}$. Divide by the tail mass $1-q$ to get the error relative to the question and it is proportional to

$$\frac{\sqrt{q(1-q)}}{1-q} = \sqrt{\frac{q}{1-q}}$$

which grows without bound as $q \to 1$. The accuracy improves towards the tail and the accuracy relative to the tail gets worse, and both statements are true of the same numbers. The structure is relative-ish, and it is not relative.

Measured against that prediction, over twenty streams:

Two things. The structure is between three and sixteen times better than its own scale function’s bound, because a query interpolates between adjacent centroid means rather than returning one, and interpolation recovers most of a centroid’s width. That is a real advantage of the query rule and it is not in the sizing argument at all.

And the growth is there. From $q = 0.9$ to $q = 0.999$ the tail-relative error rises by a factor of fifty at $\delta = 100$ and seventy at $\delta = 400$. The direction matches the derivation; the magnitude is steeper than $\sqrt{q/(1-q)}$, which predicts about ten. So the shape is right and the constant is not, and this collection can state the ordering — the far tail is relatively worse than the near tail, at every $\delta$ — without claiming the exponent.

Which is the sentence “the t-digest gives relative error at the tails” gets wrong. It gives decreasing absolute error at the tails. Relative to what is being asked about, it gives increasing error, and the structure that gives genuinely flat relative error is the one from the previous essay, at nine times the state.

It is not comparison-based, and that has consequences #

Here is the property that separates the digest from every other quantile summary in this collection, and it is not obvious from the description.

Greenwald–Khanna and the biased summary touch the data with <= and nothing else. As the previous essay establishes, their rank errors are therefore identical under any strictly increasing relabelling of the values — the same permutation of ranks produces the same structure and the same answers by rank.

A t-digest takes means. That is not a comparison. Relabel the values monotonically and the centroid means land somewhere else, the merge decisions change, and the rank errors move:

The digest’s rank error at the median went up eightfold under a relabelling that no comparison-based structure can even detect. Both halves of that are asserted on every build, because a check that only demanded the first pair match would be satisfied by a structure that had stopped working.

The consequence is not that the digest is worse. It is that the digest’s accuracy is a property of the data as well as of the parameter, so a measurement of it on one distribution is evidence about that distribution and not a bound. Every number in this essay is a measurement on stated streams, and there is no argument available here that would extend any of them to a stream nobody has tried. For the comparison-based structures there is.

The answer that never occurred #

The sharpest consequence of taking means is on the plate at the top of this page.

Build a stream of two clusters — half the values uniform on $[0, 40]$, half uniform on $[800, 840]$, nothing in between — and ask for quantiles near the middle.

Two of the three summaries are wrong at $q = 0.5$, and they are wrong in different ways. The biased summary returns 39.7 — the wrong side of the gap, but a value that arrived. Its high-biased cap at the median permits a rank error of $\varepsilon n / 2$, which is two hundred items, and two hundred items at the median of this distribution is the whole crossing. That is a correct structure meeting its promise on a distribution where the promise is not enough, which is the previous essay’s subject with the ends swapped.

The digest returns 431.5, and no value between 40 and 800 ever arrived. It is not on the wrong side of the gap; it is in the gap.

The mechanism is the query rule rather than the sizing. Not one centroid has a mean inside the empty region — the merge never crosses it, because the sorted batch has no values there — but a query interpolates between the mean of the last low centroid and the mean of the first high one, and the straight line between them passes straight through the void.

Every value a comparison-based summary returns is a value that arrived. That is not stated as a property of those structures anywhere, because it is too obvious to say: they store observations and return one. A structure that stores averages does not have it, and the interpolation that made it three to sixteen times better than its own bound at the tail is what takes it away.

Why it is deployed and the others are not #

It is worth stating the practical case plainly, because an essay in this field that only listed a structure’s defects would be misleading about why it exists.

One parameter, and it is a size. $\delta$ sets the centroid count directly, so a memory budget translates into a parameter without arithmetic. An $\varepsilon$ does not: the tuple count of a Greenwald–Khanna summary at a given $\varepsilon$ depends on the stream length and is discovered rather than chosen.

Bounded state, unconditionally. The digest holds about $\delta$ centroids however long the stream runs. Both comparison-based summaries here grow logarithmically in $n$, which is small and is not nothing when the alternative is a fixed array.

Cheap updates. Values go into a buffer and the structure is rebuilt once per buffer, so the per-arrival cost is an array append and the merge cost is amortised across hundreds of arrivals. Greenwald–Khanna does an insertion into a sorted list on every arrival and a compression pass every $1/2\varepsilon$ of them.

And it is good where most questions are. At the 90th percentile it is a third of Greenwald–Khanna’s error at four-fifths of the bits, and a ninth of the state of the structure that beats it.

None of that is a guarantee, and all of it is what an engineer choosing a library actually weighs. The gap this essay is about is not that the structure is bad; it is that the sentence “relative error at the tails” is doing work in that decision that the structure does not support, and the two places where it fails — the far tail, and a gap in the data — are not where anybody looks.

What sorted input did not do #

One thing worth reporting because it failed to reproduce.

A merging digest is often said to be vulnerable to input arriving in sorted order, on the grounds that each batch then merges into one end of the structure rather than across it. Measured, on the same heavy-tailed stream:

Nothing happens. The structure sorts each buffer before merging and rebuilds the centroid list from scratch on every flush, so an already-sorted buffer is not a special case for it. If there is an input that defeats this structure — and the literature on relative-error streaming quantiles gives reason to think adversarial ones exist — a plain sort is not it, and reporting the failed attempt is more useful than not having tried.

What a claim without a test is worth here #

This collection’s standing rule is that a claim gets a test it could fail, and an assertion that has never rejected anything proves nothing. The t-digest is the one structure here that arrives with nothing to test.

So what is asserted about it is what can be: not a bound, but a comparison that must come out in a stated direction. The digest’s tail-relative error at $q = 0.999$ must exceed its own at $q = 0.9$ by more than a factor of three, averaged over twelve independent streams, and the biased summary’s must not. That is a statement the plates rest on, it is measured rather than derived, and it fails if either the digest stops degrading or the biased summary starts.

And the structure is asked for its promise and must not have one. A query for promiseAt — the method every other summary in this family answers — is required to be absent, so that a plate drawing the digest cannot print a guarantee line beside its measurements. That is a small piece of machinery and it exists because the natural thing to do when drawing three structures on one plate is to give them all the same furniture.

A structure with no bound is not a structure with a bound of infinity. It is a structure whose behaviour has to be established by measurement on named inputs, every time, with no extension to inputs nobody has tried — which is exactly the position this collection is in with respect to it, and exactly what the sections above are.

A mean is not an observation #

The gap failure is attributed above to the query rule, and interpolation is indeed what produced 431.5. The property that was lost is older than the query, and saying so makes the repair clearer.

A centroid holds a mean of several values, and a mean of a set need not belong to it. Even without any interpolation, a digest answering with a centroid’s mean is answering with a number that may never have arrived — three values of 10, 10 and 40 give a centroid at 20, and 20 is not in the data. On a continuous distribution nobody notices, because a number close to values that arrived is indistinguishable from one that did. On data with structure — integers, prices in whole pennies, latencies rounded to the millisecond, two clusters — it is exactly noticeable.

So the guarantee that comparison-based summaries have and this one lacks is not the answer is close; it is the answer is a member of the input. That is a stronger property than it sounds and it is worth naming because it decides whether a summary’s output can be used as a key, matched against a record, or presented as an example.

The repair, for anybody who needs it, is to change what a centroid stores. Keeping a representative — one of the values it absorbed, chosen and kept — rather than a mean restores the property outright, and the query then returns an observed value at the cost of the interpolation that made the structure three to sixteen times better than its own scale bound. That is a genuine trade rather than a free fix, and which side of it is right depends on whether the answer is going to be read as a number or used as a value.

And the two failures compose. A centroid mean is not an observation; an interpolation between two centroid means is not even close to one. The 431.5 in the table above is the second on top of the first, and only the second is usually discussed.

What has to be re-measured, and how cheaply #

The consequence of having no bound is not that the structure might be wrong. It is that nothing about its accuracy transfers between deployments, and that is an ongoing cost rather than a one-off caveat.

Every number in this essay is a measurement on a named stream. The relabelling table shows why they cannot be extended: a monotone change of the values, which no comparison-based summary can even detect, moved the digest’s median rank error by a factor of eight. So a digest that was measured as accurate on last quarter’s latencies has been measured on last quarter’s latencies, and a change in the shape of the traffic — a new tier of customers, a caching layer, a unit change from milliseconds to microseconds — is a change to the thing that was measured.

That sounds like an argument against the structure and it is not, because the re-measurement is cheap and nobody does it.

Keep a uniform reservoir sample of a few thousand values alongside the digest. It costs a few tens of kilobytes, its own quantiles are exact on the sample, and the sample’s sampling error at a mid-quantile is well under a per cent at that size. Comparing the digest’s answers against the sample’s, periodically, gives a running measurement of the digest’s error on the traffic actually arriving — which is the number the structure cannot supply about itself and the number a bound would have supplied for free.

A structure with a guarantee needs no monitoring and a structure without one does, and the monitoring is a sampler that costs a fraction of the structure being monitored. That is the honest form of what “no guarantee” costs: not a risk to be accepted, but a small permanent overhead that the accuracy comparisons in this essay never charge to it.

What is not measured here #

The scale functions that are not $k_1$. Implementations offer several — one that bounds the centroid count strictly, one that is uniform, one designed for merging — and each changes the shape of the error curve. Only the arcsine is measured here, and the numbers above are about it rather than about the structure’s name.

Merging digests. The structure’s main practical claim is that digests combine well, which is why it is in monitoring systems at all. Nothing here measures a merge.

Weighted and clustered inputs beyond these two. The clustered case above is one gap in one place. A distribution with many gaps, or with heavy discrete atoms, would put the interpolation under more strain and neither is measured. What can be said from what is here is that the failure needs a gap rather than a tail: on every continuous distribution tried, the digest’s answers were values close to values that arrived.

And the guarantee that does exist. Later work — Cormode, Karnin, Liberty, Thaler and Veselý, 2021 — gives a genuinely relative-error streaming quantile structure with a proven bound and a space cost close to the digest’s. It is a different structure, it is not built here, and quoting its numbers would be quoting.