T-Digest: Streaming Quantile Estimation

The core idea: centroids instead of raw values

A t-digest never stores individual data points once they have been absorbed into the sketch; instead it maintains a sorted collection of centroids, where each centroid tracks just two numbers, a running mean of the values assigned to it and a count of how many values that represents. When a new data point arrives, the algorithm finds a nearby centroid it is allowed to merge into, given a size constraint described below, updates that centroid's mean as a weighted average and increments its count, or creates a brand-new singleton centroid if no suitable merge candidate exists. Periodically, or continuously depending on the implementation, centroids are recompacted by sorting them and greedily merging adjacent ones as long as the merge keeps every centroid within its size limit. The result is a data structure whose memory footprint depends only on the configured number of centroids, commonly in the range of a few hundred, regardless of whether the digest has absorbed a thousand points or a trillion, because old individual values are never retained, only the summarized centroids that approximate where the mass of the distribution lies.

The scale function: why tails get more resolution

The defining innovation of t-digest is its non-uniform sizing rule for how large a centroid is allowed to grow based on where it sits in the overall rank of the distribution. Each centroid has an associated quantile position q, roughly the fraction of the total data lying below it, and the algorithm's scale function maps q to an allowed size limit that is small when q is near 0 or 1, meaning near the minimum or maximum of the data, and large when q is near 0.5, the median. A commonly used scale function is based on the arcsine transformation, k(q) proportional to (2/pi) times arcsin(2q - 1), which stretches out near the tails and compresses in the middle, so equal increments of the internal scale k correspond to much finer quantile resolution near the extremes than near the center. Practically this means a t-digest might allocate dozens of tiny centroids to represent the top and bottom 1 percent of the data with high fidelity, while the middle 98 percent gets summarized by comparatively few, much larger centroids, a tradeoff that matches exactly what most real-world monitoring and analytics use cases care about, since nobody worries whether the median latency was 40 or 41 milliseconds but everybody cares whether the 99.9th percentile crossed an SLA threshold.

Merging, batch construction, and the compression parameter

T-digest exposes a single tunable knob, usually called the compression parameter, that controls the overall budget and hence the tradeoff between accuracy and memory. A higher compression value permits more centroids and finer resolution at every quantile at the cost of more memory and slightly more computation per merge, while a lower value keeps the sketch tiny but accepts coarser accuracy, particularly in the tails where fewer allowed centroids means larger clusters average over a wider range of values. In practice, digests are built incrementally as data streams in one point at a time, but they can also be built more efficiently in batches by sorting a chunk of buffered points and merging them all at once against the existing centroid list, which amortizes the cost of maintaining sorted order and tends to produce a slightly more accurate final digest than naive one-at-a-time insertion. A particularly useful property is that two independently built t-digests, say from two different servers each summarizing their own slice of traffic, can be merged together into a single combined digest that approximates the union of both underlying datasets, making t-digest naturally suited to distributed and parallel aggregation pipelines.

Estimating quantiles from the centroid list

To answer a quantile query such as, what value corresponds to the 95th percentile, the algorithm walks the sorted list of centroids accumulating their counts until it reaches the target rank, then interpolates within or between the relevant centroids to produce a smooth estimate rather than a blocky, discontinuous one. Because each centroid represents a cluster of values approximated by a single mean, this interpolation is necessarily approximate, and the error at any given quantile depends on how coarse the centroids near that quantile happen to be, which circles back to why the scale function keeps tail centroids fine-grained. Importantly, t-digest is also invertible in the other direction, supporting cumulative distribution function style queries that ask what fraction of the data falls below a given value, using the same centroid list and a symmetric interpolation scheme. Both directions of query run in time proportional to the number of centroids, essentially instantaneous compared to sorting a full dataset, which is what makes t-digest practical for interactive dashboards that need percentile answers on demand from data streams accumulating in real time.

Where t-digest shows up in real systems

T-digest has become a standard tool wherever systems need approximate percentiles over high-volume streaming data without the cost of retaining every observation. It is built into monitoring and observability platforms for computing request latency percentiles across distributed services, into big data query engines and columnar analytics systems for approximate aggregate functions over massive datasets, and into time-series databases that need to compute rolling percentile metrics efficiently. Compared to alternative streaming quantile sketches such as the GK (Greenwald-Khanna) algorithm or simple fixed-bucket histograms, t-digest is popular because its accuracy-memory tradeoff is tunable with a single intuitive parameter, its mergeability makes distributed aggregation straightforward, and its bias toward tail accuracy lines up naturally with what operators actually care about when watching production systems. The tradeoff to keep in mind is that t-digest gives approximate, not exact, answers, with error bounds that are provably small in the tails but can be comparatively larger near the median, so applications requiring exact percentiles on modestly sized datasets that fit comfortably in memory may still prefer exact sorting-based methods.

Frequently asked questions

Try it live

Everything above runs in your browser — open T-Digest: Streaming Quantile Estimation and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.