The t-digest

Your web server just handled its ten-millionth request. You want to know the median response time and the 99th percentile — the p99, the number that reveals whether the slowest one percent of your users are suffering. The naive approach: save every measurement, sort them, and read off the right positions. That works fine for a thousand requests. For a billion it means gigabytes of storage, minutes of sorting, and a result that is already stale by the time you have it.

What you really need is a streaming algorithm: something that processes each value once and keeps only a tiny summary — a sketch — from which you can read off any percentile at any moment.

The t-digest, invented by Ted Dunning and Otmar Ertl and published in 2019, is one of the most elegant solutions to this problem. It stores not raw values but a small list of weighted centroids — (mean, count) pairs that summarize clusters of nearby values. Its key insight is that the sketch needs to be most accurate at the extremes: an estimate of the median can afford a little slack, but an estimate of the p99.9 must be tight, because that is where rare, painful outliers live.

To enforce that guarantee, the t-digest uses a scaling function that limits how many data points any single centroid near the tails may absorb. Centroids near the median can grow large and coarse; centroids at the very edges stay small and precise.

The demo below runs a simplified t-digest. Each time you click Add 20 values, twenty random latency measurements (in milliseconds) are drawn from a realistic bi-modal distribution — most responses are fast, a small tail is slow. The digest absorbs each value and merges centroids that have grown too large.

<!-- {{c_layout_comment}} -->
<div class="layout">
  <div class="left-panel">
    <p class="hint">{{hint_para}}</p>
    <div class="stats" id="stats">
      <div class="stat-row">
        <span class="stat-label">{{label_count}}</span>
        <span class="stat-val" id="val-count">0</span>
      </div>
      <div class="stat-row">
        <span class="stat-label">{{label_est_median}}</span>
        <span class="stat-val" id="val-est">—</span>
      </div>
      <div class="stat-row">
        <span class="stat-label">{{label_true_median}}</span>
        <span class="stat-val" id="val-true">—</span>
      </div>
      <div class="stat-row">
        <span class="stat-label">{{label_error}}</span>
        <span class="stat-val" id="val-error">—</span>
      </div>
      <div class="stat-row">
        <span class="stat-label">{{label_centroids}}</span>
        <span class="stat-val" id="val-centroids">0</span>
      </div>
    </div>
    <div class="btns">
      <button id="btn-add" type="button">{{btn_add}}</button>
      <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
    </div>
    <div class="status" id="status"></div>
  </div>
  <div class="right-panel">
    <!-- {{c_centroid_list_comment}} -->
    <div class="centroid-header">{{label_centroid_list}}</div>
    <div id="centroid-list" class="centroid-list"></div>
  </div>
</div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.layout { display: flex; gap: 12px; align-items: flex-start; }
.left-panel { flex: 0 0 220px; }
.right-panel { flex: 1; min-width: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; }
.stats { background: #f0f4f8; border-radius: 8px; padding: 8px 10px; margin-bottom: 8px; }
.stat-row { display: flex; justify-content: space-between; align-items: center; padding: 3px 0; border-bottom: 1px solid #dde3ea; }
.stat-row:last-child { border-bottom: none; }
.stat-label { color: #556; font-size: .8rem; }
.stat-val { font-weight: 700; font-size: .9rem; color: #1d3557; font-variant-numeric: tabular-nums; }
.btns { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: 6px; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .8rem; font-weight: 600; min-height: 1.2em; color: #0a7d33; }
.centroid-header { font-size: .75rem; font-weight: 700; color: #556; text-transform: uppercase; letter-spacing: .04em; margin-bottom: 4px; }
.centroid-list { display: flex; flex-direction: column; gap: 2px; max-height: 320px; overflow-y: auto; }
.centroid-row { display: flex; align-items: center; gap: 4px; }
.c-bar-wrap { flex: 1; background: #e8eef3; border-radius: 3px; height: 12px; overflow: hidden; }
.c-bar { height: 100%; background: #457b9d; border-radius: 3px; transition: width .2s; }
.c-bar.tail { background: #e63946; }
.c-label { font-size: .7rem; color: #556; min-width: 64px; text-align: right; font-variant-numeric: tabular-nums; }

// Code not found

Notice how the estimated median stays close to the true median even though the sketch never stores the raw values. The centroid list on the right shows the structure of the sketch: a few small centroids at the extremes hold individual or near-individual points (high resolution), while the fat centroids in the middle absorb many values at once (low resolution). That deliberate imbalance is the whole trick.

How does the t-digest decide when a centroid has absorbed enough data?

Every centroid is assigned a rank — its approximate fractional position in the sorted stream, a number between 0 and 1. The algorithm uses a scaling function $k(q, \delta)$ (where $q$ is the rank and $\delta$ is a compression parameter) to map ranks to a "size budget." A centroid may only absorb a new point if doing so would not push it beyond a budget of 1 unit on the $k$-scale.

The original t-digest used $k(q) = \frac{\delta}{2\pi} \arcsin(2q - 1)$, which squeezes the budget near $q = 0$ and $q = 1$ (the tails) and widens it near $q = 0.5$ (the median). A later paper by Dunning and Ertl (2019) introduced simpler piecewise functions that are easier to compute and easier to reason about.

The result is a sketch of at most $O(\delta)$ centroids with the following accuracy guarantee: for a quantile at rank $q$, the absolute error in the estimated rank is bounded by $\frac{1}{\delta}$ near the median and by $\frac{q(1-q)}{\delta}$ near the tails — which shrinks to near zero at the very edges.

Merging digests is straightforward: concatenate the two centroid lists, sort by mean, and re-compress. This makes t-digests parallelism-friendly: each worker node builds its own digest independently, and the coordinator merges them in $O(\delta \log \delta)$ time — no raw data needs to travel the network.

Space usage is $O(\delta)$ — typically a few hundred centroids — regardless of how many values the stream has seen. Time per value is $O(\log \delta)$ for the binary search to find the right centroid, amortized $O(1)$ with a sorted buffer and batch merges.

The t-digest belongs to the broader family of sketching algorithms that trade a small, controlled error for dramatic reductions in space. Related ideas appear in counting distinct elements and other streaming problems — but quantile estimation is uniquely demanding because it requires order information, not just membership or count.

Percentile estimation is not an academic curiosity — it sits at the heart of how modern systems measure themselves:

• Observability and SLOs: Prometheus, Grafana, and Datadog all offer histogram-based approximations, but the t-digest (or HDR Histogram) is the preferred tool when you need accurate tail percentiles from unbounded streams. Service-level objectives like "p99 < 200 ms" are meaningless without accurate p99 estimates.
• Database engines: Apache Spark uses a variant of quantile sketching for its approxQuantile function. Elasticsearch ships a t-digest implementation for its percentile aggregations. ClickHouse offers quantileTDigest as a built-in aggregate.
• A/B testing platforms: experiment analysis platforms need to compare latency distributions between control and treatment groups across hundreds of millions of events; t-digests let them do it in a single pass.
• Network monitoring: routers and switches that track packet-delay distributions use compact quantile sketches; a full sorted list of every packet delay is out of the question.
• Machine learning pipelines: preprocessing steps that bin continuous features or normalize distributions use online quantile estimates; reprocessing the entire dataset on every update is too slow.

Whenever you see a p95, p99, or p99.9 figure in a production dashboard, there is a very good chance a t-digest — or something inspired by it — is doing the work behind the scenes.

The t-digest is a beautiful inversion of what "accuracy" usually means. Most data structures try to be uniformly correct. The t-digest deliberately trades precision in the easy middle — where the median lives and a small error barely hurts — for ultra-precise estimates at the extremes, where a single misclassified value can mean the difference between a passing SLO and a page-three incident report.

That asymmetric bargain, enforced by a simple scaling function, turns a list of a few hundred centroids into an accurate window onto a stream of billions. It is a reminder that knowing where you need to be right is often as valuable as the algorithm itself.

If this kind of space-efficient approximate computing intrigues you, the same family of ideas powers HyperLogLog for counting distinct elements — a different problem, but the same spirit of keeping a sketch so small it fits in a few kilobytes, and making the error provably small where it counts.