Asymmetric scale functions for t-digests
Joseph Ross · Journal of Statistical Computation and Simulation · 2021
The t-digest is a data structure that can be queried for approximate quantiles, with greater accuracy near the minimum and maximum of the distribution. We develop a t-digest variant with accuracy asymmetric about the median, thereby making possible alternative trade-offs between computational resources and accuracy which may be of particular interest for distributions with significant skew. After establishing some theoretical properties of scale functions for t-digests, we show that a tangent line construction on the familiar scale functions preserves the crucial properties that allow t-digests to operate online and be mergeable. We conclude with an empirical study demonstrating the asymmetric variant preserves accuracy on one side of the distribution with a much smaller memory footprint.