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

Greenwald–Khanna — where it appears

A quantile summary of value-count-uncertainty triples whose merging invariant delivers a deterministic bound on the rank error of every answer. Its bound is deterministic and uniform across the distribution, which makes it worthless at a tail percentile where the tolerance covers the whole tail.

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

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 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 ε = 0.0515 → 29 (1.93×)ε = 0.0238 → 73 (1.92×)ε = 0.0177 → 136 (1.77×)ε = 0.005152 → 270 (1.78×)ε = 0.002397 → 674 (1.70×)reportedoccupied at the peak20,000 arrivals · lognormalpeak = resident + period, to 14%

The tuples a summary does not report

A Greenwald–Khanna summary at ε = 0.01 answers `tuples` with seventy-seven. Watched through the run it holds a hundred and thirty-six. The gap is the compression period, it is 1.70 to 1.93 times across every tolerance measured, and it is the number a deployment has to allocate.

space · Space 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 1 — no differencethe whole array reviewed1.03×only this batch reviewed1.22×a block window, which does alias1.48×20,000 arrivals · period 50 · cyclethe instrument reads 1.48 where an alias is known to be

The sampler that cannot alias

A block window's boundary fires on an arrival count, and a stream whose burst repeats every sixty-four arrivals is reported as perfectly even by a block of five hundred and twelve. A quantile summary compresses on an update count, which is the same arrangement. Swept against three periodic value processes and their shuffles, it does not alias — and the reason is one line of arithmetic rather than a lucky sweep.

wrong · Window

Named alongside it

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

Quantile summaryRank errorGuaranteeState bitsTrade offMeasurementSpace overheadMerge treeMergeable summaryShardCompression scheduleHonest limit

All concepts