sketchadv

confirmedshipRustSystems & data structuresJuly 14, 2026

the question

At matched-or-greater space on adversarial continuous streams, does t-digest's quantile rank error stay within the eps*N bound that Greenwald-Khanna guarantees?

what came out

GK holds eps*N (2000 at N=200k) on every stream. t-digest, given equal-or-greater space, stays near-exact and about 2.3x faster on random data but violates the bound on adversarial streams: max rank error 2313 on skew_middle and 6277 on bimodal_gap, with the whole BCa CI above eps*N.

method & receipts

Result: confirmed
Pre-registered — the prediction was written down and committed before the run.
Reproducible — one script re-runs the whole thing from scratch.
Tested — a correctness/benchmark suite ships alongside the code.

→ read the code and re-run it

github.com/v-code01/sketchadv