Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Rank error — where it appears

How far, as a fraction of the stream, an answered quantile sits from the rank it was asked for — a quantity unrelated to how wrong the number is. It is a fraction of the stream, so the same number is a tenth of a per cent at the median and a hundred per cent of the tail at the 99.9th percentile.

Named by 11 essays across 5 fields — each of them below, with the objects they name alongside it.

quantilepromisedone summarymerge of 8q = 0.5100.01418q = 0.920.0183q = 0.992.005overq = 0.9990.214overrank error, in items out of 20,000ε = 0.01 · high-biased · 8 shards, round2 of 4 quantiles over the single summary's promise

The promise that does not survive the tree

A high-biased quantile summary at ε = 1% answers the 99th percentile of twenty thousand values to within two ranks. Merge thirty-two of them and the answer is seventeen ranks out — inside the merged bound, eight times outside the one anybody was quoted.

wrong · Rank answered 19.90%25%50%75%100%0.36420.52,170value, logarithmicfraction of the stream at or belowrank ±2%value 19.3–21.9answered 2.9% out20,000 values · log-normal, σ = 1.2 — a latency distribution · Greenwald–Khanna, ε = 0.02rank 1.02% · value 2.9%

The error that is on the rank

A summary of 77 tuples answers eight quantiles of a stream of 20,000 values, and every answer is guaranteed to sit within 0.9% of the stream from where it was asked for. The guarantee is deterministic, it holds on every distribution, and it is not about the numbers it returns.

streaming · Rank Count-Min8,192 bitsCount-Sketch8,192 bitstug-of-war, F22,560 bitsGreenwald–Khanna0 bitsexponential histogram0 bitscash register+strict turnstile±general turnstile± may go negativesliding window+ expiresdeclareddeclared93% under—declareddeclareddeclared—declareddeclareddeclared—declared——————declared40,000 updates · deletion rate 0.5 · every count exact1,758 of 1,895 under

The model a bound was quoted in

Every accuracy figure in this field's first phase was measured under four unstated assumptions. Remove them one at a time and one structure loses its guarantee on 91% of queries, another's error stops falling when it is given more state, and a third has nothing to do at all.

bounds · Bound 0.1%1%10%100%0.50.750.90.990.999quantile asked forrank error ÷ (1 − q)Greenwald–Khanna7,080 bitshigh-biased56,064 bitst-digest5,952 bits8 streams per point · ε = 0.01, δ = 100denominator: the tail

An error measured against the answer

A quantile summary asked for the 99.9th percentile answered 9,694 where the truth was 256, and violated nothing — its promise was a rank error under one per cent of the stream and it delivered a tenth of one per cent. One per cent of the stream is a thousand per cent of the tail, and no amount of extra state changes that.

streaming · Rank 1,000248163264high-biased, α = 0.56low-biased, α = 0.56none-biased, α = 0.74tuples keptshards mergedlog-normal, σ = 1.2 — a latency distribution · 20,000 valuesα 0.56 / 0.56 / 0.74 · worst residual 6.5%

The cheap tail and the expensive merge

A summary whose tolerance tightens towards the tail keeps seven times the tuples of a plain one on a single pass, and after merging sixty-four shards it keeps three and a half times as many. The error function that buys a useful tail promise is also the one that pays most for never having the values in one place.

space · Rank answered 4,1900%25%50%75%100%11.794,190value, logarithmicfraction of the stream at or belowrank ±2%value 24.9–4,190answered 1553.5% out20,000 values · Pareto, α = 1.2 — a heavy tail · Greenwald–Khanna, ε = 0.02rank 0.10% · value 1553.5%

A promise about the rank is not a promise about the value

A quantile summary asked for the 99th percentile of a log-normal stream returns the largest value it ever saw — 2,169 against a true 318, six times too high — and its rank error is 1.00% against a promised 2%. The guarantee held. It was never about the number.

wrong · Rank 1,00010,000248163264ε = 0.02, α = 0.58ε = 0.01, α = 0.56ε = 0.005, α = 0.54tuples keptshards mergedlog-normal, σ = 1.2 — a latency distribution · 20,000 valuesα 0.58 / 0.56 / 0.54 · worst residual 2.0%

The tuples a merge does not give back

A merge of thirty-two quantile summaries keeps seven times the tuples of one summary over the same values, and sixty-four keeps ten and a half. Fitted across the sweep the count goes as the shard number to the power 0.56, which answers what it converges to — it does not.

streaming · Rank 10010³10⁴10⁵10⁶⌊1/2ε⌋ = 50151025501002005001,000tuples, and tuples examinedcompression period, in updatestuples examinedpeak tuplesresident tuplesworst rank errorε = 0.01 · 20,000 arrivalspeak 10× · work 72× · answer 1.21×

The period that is not a promise

Greenwald–Khanna's ε appears twice — once as the rank tolerance the structure promises, and once as ⌊1/2ε⌋, the number of updates between compressions. Unhook the second from the first and sweep it across a thousand-fold range. The tuples held move by 10%, the worst rank error by 21%, the peak by ten times and the housekeeping by seventy.

streaming · Rank Greenwald–Khanna7,008 bits802high-biased55,008 bits802t-digest6,144 bits675the truth, 802ε = 0.01, δ = 100 · 40,000 valuesq = 0.52

The digest that promises nothing

The t-digest is the quantile structure most widely deployed and the only one with no proven bound on its rank error at any quantile. Measured, it beats the structure that does have one — and on two clusters with a gap between them it returns 431.5, where the data holds nothing at all between 40 and 800.

wrong · Rank folded in one at a time2,616 tuples17 ranks outcombined pairwise, in a tree3,637 tuples17 ranks outfolded in, last shard first2,615 tuples17 ranks outtuples kept, and worst rank error against a promise of 10032 shards · ε = 0.01 · high-biased · round1.39× the space, 0 ranks of answer

The shape that moves the bill

Thirty-two quantile summaries combined pairwise keep 3,637 tuples and the same thirty-two folded in one at a time keep 2,616, for answers that differ by nothing at all. The counter tables measured for the same thing do the opposite — their order moves the answer and leaves the space alone.

structures · Rank counter tablesworst error, ratio to bestquantile summariestuples kept, ratio to bestchain2.18× (323)1.10× (2,807)tree1.00× (148)1.26× (3,211)smallest-first1.24× (183)1.28× (3,278)largest-first2.72× (403)1.00× (2,556)32 shards · hashed · k = 32each column against its own best shape

The shape one structure will not fold

Folding thirty-two shards largest-pair-first keeps 2,556 quantile tuples against a balanced tree's 3,211 — a fifth of the space saved. The same fold on the counter tables beside them leaves 403 counts of error against the tree's 148. A deployment holding both cannot fold once and be right twice.

structures · Merge

Named alongside it

The objects these essays reach for when they reach for this one.

GuaranteeGreenwald–KhannaQuantile summaryState bitsTrade offMergeable summaryShardHonest limitMeasurementMerge treeSpace overheadTail

All concepts