t-digest & Streaming Quantiles

A stream of values forms centroids — small at the tails, large in the middle — then a quantile query interpolates.

Add: O(log C) amortized Query: O(C) Memory: O(compression) Tail-accurate p99 / p999

Controls

slow fast
0.99
0
values (n)
0
centroids (C)
–
min
–
max
–
estimate
–
exact
–
rel. error

Centroids along the distribution

centroid (width = value range, height = count)
just merged / added
new centroid (tail)
query interpolation

What just happened

Pick a distribution and press Stream or Add 1 value. Watch centroids stay small near the tails and grow large in the middle. Then Query quantile to interpolate p99.

Complexity & accuracy

OperationTimeSpaceNotes
Add value (buffered)O(log C)—amortized; C = compression
Quantile queryO(C)—sweep + interpolate
Merge two digestsO(C log C)O(C)concatenate, sort, re-cluster
Total memory—O(compression)independent of n
Exact (sort)O(n log n)O(n)impossible on a stream

Rank error ≈ (π/δ)·√(q(1−q)) — smallest at the tails (p99/p999), largest at the median. Accuracy is empirical; GK is deterministic, KLL is randomized.

Operation log