THE FOLD / LOOT / THE INVENTORY / THE T-DIGEST
THE T-DIGEST
a sketch that decided in advance what would matter
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
To report a 99th percentile you appear to need every sample. A t-digest keeps a few hundred weighted centroids instead — and deliberately keeps them uneven: fine at the tails, coarse in the middle, because that is where the questions are.
LIT verified live. 100,000 samples reduced to 51 centroids — a 1,961× reduction. Worst error across the seven quantiles tested is 0.0789, at q=0.99. The unevenness is the point and it is measured, not asserted: the first centroid carries 98 samples while the middle one carries 3,139, so the tail is resolved about 32× more finely than the median.
LIT verified live. 100,000 samples reduced to 51 centroids — a 1,961× reduction. Worst error across the seven quantiles tested is 0.0789, at q=0.99. The unevenness is the point and it is measured, not asserted: the first centroid carries 98 samples while the middle one carries 3,139, so the tail is resolved about 32× more finely than the median.
2 HOW IT WAS WEAVED · AI + HUMAN
Ted Dunning introduced the t-digest in 2013; the scale function
AVAN (AI) measured the asymmetry rather than describing it. The arcsine is steep at 0 and 1 and flat at 0.5, so a fixed budget of one k-unit per centroid buys many samples in the middle and few at the edges. That is not an accuracy tuning parameter bolted on afterwards — the error profile is a direct consequence of the shape of a single function.
k1(q) = (d/2π)·asin(2q−1) is his, and it is the whole trick.AVAN (AI) measured the asymmetry rather than describing it. The arcsine is steep at 0 and 1 and flat at 0.5, so a fixed budget of one k-unit per centroid buys many samples in the middle and few at the edges. That is not an accuracy tuning parameter bolted on afterwards — the error profile is a direct consequence of the shape of a single function.
3 ONE DIMENSION
Centroid weight against position. The dip at the edges is the design.
4 TWO DIMENSIONS · INTERACTIVE
Estimate against truth, quantile by quantile.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a distribution folded onto a few points.
AVAN’s addition (the inverse-companion): the forward reading is that the t-digest is accurate where it matters. The inverse is that it decided where that was before it saw your data. The arcsine is fixed; it commits to caring about tails at the moment of construction, and a distribution whose interesting structure sits at q=0.5 gets resolved 32× more coarsely for no reason but the shape of a curve chosen in advance. Read backwards, every sketch is a prior about which questions will be asked, and its accuracy is a statement about the asker, not the data.
LIT 100,000 samples reduced to 51 centroids, a 1,961x reduction, with a worst error of 0.0789 across seven quantiles, at q=0.99; the unevenness is measured not asserted - the first centroid carries 98 samples and the middle one 3,139, so the tail is resolved about 32 times more finely than the median
FIG Ted Dunning introduced the t-digest in 2013; the scale function k1(q) = (d/2pi) asin(2q-1) is his and it is the whole trick. AVAN measured the asymmetry rather than describing it: the arcsine is steep at 0 and 1 and flat at 0.5, so a fixed budget of one k-unit per centroid buys many samples in the middle and few at the edges. The error profile is a direct consequence of the shape of a single function, not an accuracy knob added afterwards.
FIG Ted Dunning introduced the t-digest in 2013; the scale function k1(q) = (d/2pi) asin(2q-1) is his and it is the whole trick. AVAN measured the asymmetry rather than describing it: the arcsine is steep at 0 and 1 and flat at 0.5, so a fixed budget of one k-unit per centroid buys many samples in the middle and few at the edges. The error profile is a direct consequence of the shape of a single function, not an accuracy knob added afterwards.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE INVENTORY · David Lee Wise (ROOT0), with AVAN