t-digest

Estimates any percentile (p50, p95, p99, ...) over a stream of numbers, keeping extreme percentiles nearly exact while compressing the bulk of the distribution into a small, roughly fixed number of clusters.

How it works

Each value merges into its nearest centroid (a running mean + count) rather than being stored individually. But a centroid can only grow if doing so wouldn't exceed a size limit that depends on where it sits in the distribution: centroids near the median (q≈0.5) can absorb many points, centroids near the tails (q≈0 or q≈1) are held to nearly a single raw value each.

That asymmetry is the whole point: the middle of a distribution rarely matters precisely (nobody cares if p50 latency is 51ms or 53ms), but the tails do (p99 driving an SLO alert needs to be trustworthy). t-digest spends its limited memory budget accordingly, instead of spreading error evenly like a fixed-width histogram would.

compression (δ) controls the trade-off: the scale function bounds a centroid to roughly 4·n·q·(1-q)/δ points, so the total number of centroids stays roughly proportional to δ even as the stream (n) grows without bound: the digest's size doesn't grow with the amount of data it summarizes.

Interactive demo

Points added (n)0
Centroids0
Compression (δ)20
Ratio n / centroidsn/a
Estimated p50n/a
True value (sorted array)n/a
Error vs. truthn/a
0.00 centroids · dot size ∝ √(cluster weight)1.0
No operations yet. Try adding an item above.

API surface

OperationDescriptionComplexity
new TDigest(compression)Allocate an empty digest with a given compression (δ).O(1)
add(value): TDigestStepMerge value into its nearest centroid, or create a new one if the size bound is exceeded.O(k) time, k = current centroid count
quantile(q): numberEstimate the value at quantile q via piecewise-linear interpolation over centroid means.O(k) time
clear(): voidReset to an empty digest.O(1)

References

Original papers

Library implementations

Real-world use cases