Search tools and guides ⌘K
IV · Probabilistic structures

t-digest

Quantiles, fairly accurate, fully streaming.

2013 · Ted Dunning · MapR
The story

Computing exact percentiles requires sorting all the data. Approximate methods (GK summary, Q-digest) work but degrade at the tails — exactly where p99 and p99.9 live. Dunning's t-digest cleverly allocates more resolution to the tails by clustering points with non-uniform weights.

How it works

Maintain a list of "centroids" (mean, weight) compressed by a scale function that gives more resolution near 0 and 1 quantiles. Inserts merge into nearest centroid or create a new one. Quantile queries interpolate between centroids.

Where it lives

Elasticsearch percentiles. Cassandra latency aggregates. Apache Druid. Every time-series database that ships pre-aggregated p99s — including Prometheus's histogram_quantile.

The key insight

t-digests are mergeable. Each shard or pod can compute its own; the central server merges them for the cluster-wide p99. Without merge, you cannot do approximate percentiles across distributed systems.

More in Probabilistic structures
Bloom filter A set, in a thousandth of the space. HyperLogLog Count distinct, in 12 KB. Count-Min sketch Approximate frequencies, in tiny memory. MinHash Set similarity, in a few hashes.
Across the cabinet
V Gap buffer A buffer with a hole at the cursor. VI Adjacency list Each node, its neighbours. VI Disjoint Set / Union-Find Track connected components, in a forest. VI Merkle tree Hash of hashes; tamper-evident. VI LSM-tree Append-only, merged in the background. VI DAG · directed acyclic graph Order without cycles. VII KD-tree Binary search, in higher dimensions. VII R-tree A tree of bounding boxes.
← All data structures