Streaming Quantile Approximation with T-Digest

Worked Solution

How to Think About It: The core tension in streaming quantiles is that you cannot store every data point, so you must compress. Uniform compression -- equal-sized bins across the range -- treats the 50th percentile the same as the 99.9th. But in practice, the tails are where the action is: VaR, CVaR, tail risk, extreme event detection. The T-Digest insight is dead simple: let clusters near the edges be tiny (high resolution) and clusters in the middle be large (low resolution). This is just a non-uniform allocation of your compression budget toward where it matters most.

Key Insight: Use a scale function $k(q) = (\delta / 2\pi) \arcsin(2q - 1)$ (or equivalently tied to the CDF of an arcsine-like distribution) that maps quantile position $q$ to a "scale space." The maximum weight a cluster at quantile $q$ can absorb is proportional to $k'(q)$, which is small near $q = 0$ and $q = 1$ and large near $q = 0.5$. This single function drives the entire design.

The Method:

*Data Structure:*

Maintain a sorted array (or balanced BST) of clusters $\{(\mu_i, w_i)\}_{i=1}^{C}$, where $\mu_i$ is the weighted mean of points absorbed into cluster $i$ and $w_i$ is the count. Define the cumulative weight up to cluster $i$ as $W_i = \sum_{j \leq i} w_j$ and total weight $N = W_C$. The quantile position of cluster $i$ is approximately $q_i = (W_{i-1} + w_i/2) / N$.

The size-limit function is:

$$k(q) = \frac{\delta}{2\pi} \arcsin(2q - 1)$$

where $\delta$ is a compression parameter (typically $\delta \approx 100{-}300$). A cluster at quantile $q_i$ with current weight $w_i$ can absorb a new point only if the resulting cluster would satisfy:

$$w_i + 1 \leq \delta \cdot k'(q_i) = \frac{\delta}{\pi \sqrt{q_i(1 - q_i)}}$$

Note that $k'(q) \to 0$ as $q \to 0$ or $q \to 1$, so tail clusters stay small. Near $q = 0.5$, clusters can grow large.

*Insert Procedure:*

1. Binary search the sorted cluster array to find the cluster $c_j$ whose mean $\mu_j$ is closest to the new point $x$. Time: $O(\log C)$.
2. Check the size limit: if $w_j + 1 \leq \delta \cdot k'(q_j)$, merge $x$ into $c_j$ by updating $\mu_j \leftarrow (\mu_j w_j + x) / (w_j + 1)$ and $w_j \leftarrow w_j + 1$.
3. If the size limit is violated, create a new singleton cluster $(x, 1)$ and insert it into the sorted array.
4. If the number of clusters exceeds a threshold (e.g., $10 \cdot \delta / 2\pi$), trigger a compression pass: scan clusters in sorted order, merging adjacent pairs whenever the combined weight stays within the size limit for the resulting quantile position.

*Merge Procedure (combining two T-Digests $A$ and $B$):*

1. Concatenate all clusters from $A$ and $B$ into a single list and sort by centroid mean. This takes $O(C \log C)$.
2. Walk through the sorted list, greedily merging consecutive clusters as long as the combined weight satisfies the size-limit function evaluated at the new cumulative quantile position.
3. Alternate the scan direction (left-to-right, then right-to-left) across multiple merges to avoid systematic bias toward one tail.

*Quantile Query:*

To estimate the value at quantile $q$, compute the target cumulative weight $t = q \cdot N$. Binary search for the two adjacent clusters $c_i, c_{i+1}$ that straddle $t$, then linearly interpolate between $\mu_i$ and $\mu_{i+1}$.

Rank Error Bound:

The rank error at quantile $q$ is bounded by the maximum weight of the cluster containing $q$, divided by $N$. Since the maximum cluster weight at position $q$ is at most $\delta \cdot k'(q) = \delta / (\pi \sqrt{q(1-q)})$, the rank error is:

$$\epsilon(q) \leq \frac{\delta}{\pi N \sqrt{q(1-q)}}$$

But since we have at most $C$ clusters and total weight $N$, the average cluster weight is $N/C$. In the tails where $q \approx 1/N$ (a single observation), the cluster weight is $O(1)$, giving rank error $O(1/N)$ -- essentially exact. In the middle where $q \approx 0.5$, the cluster weight can be up to $O(N/C)$, giving rank error $O(1/C)$. More precisely:

$$\epsilon(q) = O\!\left(\frac{1}{C \cdot \min(q, 1-q)}\right) \quad \text{for } q \text{ bounded away from 0 and 1}$$

The total number of clusters is $C = O(\delta)$, so increasing $\delta$ (and thus $C$) tightens the bound everywhere.

Why This Beats Uniform Binning:

Uniform binning (equal-count or equal-width) allocates the same resolution everywhere. With $C$ uniform bins, the rank error is $O(1/C)$ at every quantile -- including the tails. The T-Digest achieves $O(1/C)$ in the middle but much better in the tails:

• At $q = 0.01$ (the 1st percentile), a uniform scheme has error $O(1/C)$, while T-Digest has error $O(1/(100C))$ -- two orders of magnitude better for the same budget $C$.
• At the extremes ($q = 1/N$), T-Digest stores individual observations, giving exact answers.
• The cost is slightly worse resolution near the median, but nobody needs six decimal places at the 50th percentile -- they need it at the 99th.

This is exactly the trade-off you want in risk management: your VaR and CVaR estimates (which live in the tails) get dramatically better accuracy without increasing memory.

Answer: Maintain $C = O(\delta)$ sorted cluster centroids with a size-limit function $k'(q) = \delta / (\pi \sqrt{q(1-q)})$ that forces small clusters in the tails and allows large clusters in the middle. Insert via binary search in $O(\log C)$; merge by sorted concatenation and greedy compression. Rank error is $O(1/(C \cdot \min(q, 1-q)))$, which beats uniform binning's flat $O(1/C)$ by a factor proportional to how extreme the quantile is.