按年被提到
20192019 · 1 次2026
系统、数据库与网络›表格、数据草图与数据集·arXiv:1902.04023 · stat.CO

Computing Extremely Accurate Quantiles Using t-Digests

用 t-digest 计算极精确的分位数
Ted Dunning, Otmar Ertl · 2019

在线分位数草图 t-digest,尾部相对精度高、体积小、可无损合并

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2019-02-15 · 最近 2021-09-14
3不同的人
3活跃月份
3讨论串
61被引(OpenAlex)

论文提出计算基于秩的统计量近似值的在线算法,用很小的草图(sketch)就能达到高精度,尤其在分布尾部。其特点是分位数 q 的精度是相对于 max(q, 1-q) 的,而不是像多数方法那样的绝对精度;算法对偏斜分布或有序数据集保持稳健,并且分别计算的摘要可以无损合并。作者提供了 Java 开源实现,另有 Go 和 Python 的独立实现。

HN 为什么提它

评论者用它说明较新的数据结构 t-digest 即使在 99.999% 这样的极端尾部分位数上仍保持很高精度,也有人讨论其评估所用的平均绝对误差。

方法难度 3 / 5约 40 分钟经得起时间
读之前最好知道
1分位数与百分位数
2流式算法与数据草图(sketch)
3聚类与质心(centroid)
4误差度量:绝对误差与相对误差

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用jmacd333 · 2020-03

“Dunning uses Mean Absolute Error in his latest T-digest paper:”

指出 Dunning 在最新 t-digest 论文中用平均绝对误差
Lies, Damned Lies, and Averages: Perc50, Perc95 Explained for Programmers原评论 ↗
引用cyral · 2021-09

“There are some newer data structures that take this to the next level such as T-Digest[1], which remains extremely accurate even when determining percentiles at the very tail end (like 99.999%)”

推荐 t-digest,在 99.999% 等极端尾部分位数仍很精确
How percentile approximation works and why it's more useful than averages原评论 ↗
被提交为 story · 1 次