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

A rank promise of ±2% at q = 0.99 on log-normal, σ = 1.2 — a latency distribution

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
A rank promise of ±2% at q = 0.99 on log-normal, σ = 1.2 — a latency distributionThe curve is the empirical distribution of 20,000 values: the horizontal axis is the value, logarithmic and the vertical axis is the fraction of the stream at or below it. A promise about the RANK is the shaded horizontal band, whose height is fixed at ±2% wherever it is drawn. What it permits in the ANSWER is the vertical band it cuts from the curve, and that runs from 187 to 2,170 — a range of 623% of the true value at this quantile. The summary answered 2,170 against a true 318: a rank error of 1.00%, inside the promise, and a value error of 581.7%, about which the promise says nothing. The two errors are the same number exactly when the distribution is flat, and the gap between them is the slope of this curve.answered 2,1700%25%50%75%100%0.36420.52,170value, logarithmicfraction of the stream at or belowrank ±2%value 187–2,170answered 581.7% out20,000 values · log-normal, σ = 1.2 — a latency distribution · Greenwald–Khanna, ε = 0.02rank 1.00% · value 581.7%

A rank promise of ±2% at q = 0.99 on log-normal, σ = 1.2 — a latency distribution

The curve is the empirical distribution of 20,000 values: the horizontal axis is the value, logarithmic and the vertical axis is the fraction of the stream at or below it. A promise about the RANK is the shaded horizontal band, whose height is fixed at ±2% wherever it is drawn. What it permits in the ANSWER is the vertical band it cuts from the curve, and that runs from 187 to 2,170 — a range of 623% of the true value at this quantile. The summary answered 2,170 against a true 318: a rank error of 1.00%, inside the promise, and a value error of 581.7%, about which the promise says nothing. The two errors are the same number exactly when the distribution is flat, and the gap between them is the slope of this curve.

Drawn at 700 × 420, wide on the page. Everything above is what rank-against-value returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

7 essays call rank-against-value. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

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% One pass, and no room

The error that is on the 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 What a bound is

The model a bound was quoted in

 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 One pass, and no room

An error measured against the answer

 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% What is taught wrongly

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

 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% One pass, and no room

The tuples a merge does not give back

 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× One pass, and no room

The period that is not a promise

 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 What is taught wrongly

The sampler that cannot alias

The library, page 3 of 5 — where rank-against-value sits