t-Digest

t-Digest is a compact, mergeable streaming data structure and adaptive clustering algorithm in computation and algorithms designed to estimate empirical quantiles, percentiles, and cumulative distribution functions (CDFs) over continuous one-dimensional numerical streams in bounded O(δ) memory. Developed by Ted Dunning beginning in 2013 and formalized by Ted Dunning and Otmar Ertl in 2019, the t-digest partitions an ordered sequence of N observations into m ≤ ⌈δ⌉ weighted centroids (c_i = (μ_i, w_i)) whose maximum allowable weight w_i is governed by a steep non-linear scale function k(q, δ) that shrinks to 1 sample at the distribution tails (q → 0 and q → 1) while permitting wider clusters near the median (q = 0.5).

Within computational complexity theory and distributed telemetry engineering, computing precise quantiles such as the 99.9th or 99.99th latency percentile across N observations requires Ω(N) memory according to the Munro–Paterson (1980) streaming lower bound. Classical uniform-error quantile summaries such as the Greenwald–Khanna (GK, 2001) algorithm and the Karnin–Lang–Liberty (KLL, 2016) sketch bound uniform rank error |q̂ − q| ≤ ε uniformly across all q ∈ [0, 1], which requires O(1/ε) centroids and becomes prohibitive when ε = 10⁻⁴ or 10⁻⁵ at the far tails (p99.99). By trading uniform error for relative tail error proportional to q(1 − q), the t-digest estimates p99, p99.9, and p99.999 with parts-per-million precision using only 100 to 300 centroids (~1.6–4.8 KB of RAM) and merges associatively across parallel workers alongside HyperLogLog and Count–Min sketch aggregators.

Weighted Centroids and Empirical Quantile Intervals

Given a multiset of N real-valued observations X = {x₁, x₂, ..., x_N}, a t-digest summarizes X as an ordered sequence of m centroids C = ((μ₁, w₁), (μ₂, w₂), ..., (μ_m, w_m)) sorted by ascending mean μ₁ ≤ μ₂ ≤ ... ≤ μ_m, where μ_i ∈ ℝ is the sample mean of the i-th cluster and w_i ≥ 1 is the total weight (sample count) of observations merged into that cluster, satisfying ∑_i=1..m w_i = N.

For each centroid c_i, define its left cumulative weight W_left(i) = ∑_j<i w_j and its right cumulative weight W_right(i) = W_left(i) + w_i. These cumulative sums map each centroid c_i to a sub-interval [q_left(i), q_right(i)] ⊆ [0, 1] of the quantile domain:

When two centroids (μ_a, w_a) and (μ_b, w_b) are combined, their merged centroid (μ_ab, w_ab) follows precise one-pass weighted mean combination:

The k-Size Invariant and the Four Canonical Scale Functions k(q, δ)

To control the size of each centroid as a function of its quantile position q ∈ [0, 1], the t-digest introduces a monotonically increasing scale function k : [0, 1] → [k_min, k_max] parameterized by a compression factor δ (typically δ ∈ [100, 1000]). The t-digest size invariant requires that the k-scale span Δk(c_i) of every centroid containing more than one sample (w_i > 1) never exceed 1:

Because the total span of k(q, δ) from q = 0 to q = 1 is k(1, δ) − k(0, δ) ≤ δ, a fully merged t-digest (in which no two adjacent centroids can be combined without violating Δk ≤ 1) contains at most ⌈δ⌉ centroids (and at least ⌊δ/2⌋ centroids when N ≫ δ), bounding the memory footprint at O(δ) independent of stream length N.

By the Mean Value Theorem, Δk(c_i) ≈ (w_i / N) · (∂k/∂q), so the maximum allowable weight w_i of a centroid at quantile q is inversely proportional to the derivative ∂k/∂q:

1. k₀ (Piecewise Linear / Uniform): k₀(q, δ) = (δ / 2) q. Gives uniform centroid weights w_i ≤ 2N/δ across all q (constant uniform rank error, identical to an equi-depth histogram).
2. k₁ (Arcsine Scale Function — Default):

Here ∂k₁/∂q = δ / (2π √(q(1 − q))), so maximum centroid weight scales as w_i ≤ (2π N / δ) √(q(1 − q)), shrinking smoothly to w_i = 1 at q = 0 and q = 1.

1. k₂ (Logarithmic Odds Scale Function):

Here ∂k₂/∂q ∝ 1 / (q(1 − q)), so maximum centroid weight scales linearly with tail distance w_i ∝ N q(1 − q) / δ, keeping relative quantile error |q̂ − q| / min(q, 1 − q) nearly constant across all orders of magnitude near 0 and 1.

1. k₃ (Split-Logarithmic Scale Function): Uses ln(2q) for q ≤ 0.5 and −ln(2(1 − q)) for q > 0.5, providing the same w_i ∝ q(1 − q) tail scaling as k₂ without symmetric cross-talk at q = 0.5.

Batch Sort-Merge Compression Algorithm (MergingDigest)

Although Dunning's original 2013 paper described both a tree-based online clustering variant (ClusteringDigest, which inserts each new sample into the nearest centroid in a balanced red–black tree) and a batch-merging variant (MergingDigest), production systems almost universally use MergingDigest because it operates in flat contiguous arrays with zero heap allocations:

1. Buffer Accumulation: Incoming stream samples (x, w = 1) or incoming centroids from other worker nodes are appended to a small temporary buffer array of capacity B ≈ 2δ to 5δ.
2. Sort and Greedy Compaction Pass: Whenever the buffer fills (or a query is issued), the existing m centroids and the buffered items are combined and sorted by ascending mean μ in O(δ log δ) time. A single linear pass then merges consecutive items (μ_j, w_j) into the current running centroid (μ_curr, w_curr) as long as adding w_j keeps k(q_right, δ) − k(q_left, δ) ≤ 1; as soon as adding w_j would exceed the k-step limit of 1, (μ_curr, w_curr) is emitted and (μ_j, w_j) starts the next centroid.
3. Alternating Forward/Backward Merge Passes: Performing every compaction pass rigorously from left (q = 0) to right (q = 1) would introduce a subtle asymmetric drift on non-stationary or sorted streams. MergingDigest eliminates this bias by alternating the merge scan direction—scanning in ascending order (q : 0 → 1) on odd merges and descending order (q : 1 → 0) on even merges.

Quantile and CDF Linear Interpolation

To evaluate quantile(q) for a target rank Q = q · N, the t-digest locates the pair of adjacent centroids c_i and c_i+1 whose cumulative midpoint ranks M_i = W_left(i) + w_i/2 and M_i+1 = W_left(i + 1) + w_i+1/2 bracket Q (M_i ≤ Q ≤ M_i+1), and linearly interpolates between their means μ_i and μ_i+1 (forcing singleton centroids w = 1 at the boundary to return their precise sample value). Because w₁ = w_m = 1 under k₁, k₂, and k₃, the minimum (q = 0) and maximum (q = 1) are always preserved without error.

Why does a t-digest keep singleton centroids (w = 1) at the minimum and maximum of the stream?

Under the arcsine (k₁) and logarithmic (k₂, k₃) scale functions, the slope ∂k/∂q diverges as q → 0⁺ and q → 1⁻. Consequently, the k-size limit Δk ≤ 1 forces the first centroid at q_left = 0 and the last centroid at q_right = 1 to have maximum weight w = 1, ensuring that quantile(0.0) and quantile(1.0) always return the precise minimum and maximum observed in the stream, and that p99.99 is interpolated across tiny near-singleton clusters.

Is the t-digest vulnerable to adversarial input sequences?

Like other heuristic value-clustering sketches, the t-digest is not an oblivious comparison-only sketch: carefully constructed adversarial input sequences (such as exponentially growing interleaved sawtooth patterns studied by Cormode et al., 2021) can induce larger rank error in the interior of the distribution if merge buffers are small. However, on real-world latency, financial, and scientific telemetry distributions (log-normal, Pareto, Weibull, Gaussian, or uniform), alternating-direction MergingDigest with δ = 200 achieves 10× to 100× lower tail error per kilobyte than worst-case uniform-rank sketches.

1. Dunning, T., & Ertl, O. (2019). "Computing exceptionally accurate quantiles using t-digests." arXiv Preprint / Software Impacts Foundation, arXiv:1902.04023. https://doi.org/10.48550/arXiv.1902.04023
2. Munro, J. I., & Paterson, M. S. (1980). "Selection and sorting with limited storage." Theoretical Computer Science, 12(3), 315–323. https://doi.org/10.1016/0304-3975(80)90061-490061-4)
3. Greenwald, M., & Khanna, S. (2001). "Space-efficient online computation of quantile summaries." Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data (SIGMOD '01), 58–66. https://doi.org/10.1145/375663.375670
4. Karnin, Z., Lang, K., & Liberty, E. (2016). "Optimal quantile approximation in streams." Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), 71–78. https://doi.org/10.1109/FOCS.2016.17
5. Masson, C., Rim, J. E., & Lee, H. K. (2019). "DDSketch: A fast and fully-mergeable quantile sketch with relative-error ensures." Proceedings of the VLDB Endowment, 12(12), 2195–2205. https://doi.org/10.14778/3352063.3352135