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

DDSketch: A fast and fully-mergeable quantile sketch with relative-error guarantees

DDSketch:快速且完全可合并、带相对误差保证的分位数草图
Charles Masson, Jee E. Rim, Homin K. Lee · 2019

首个完全可合并、有相对误差形式保证的分位数草图,Datadog 已大规模使用

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2019-08-29 · 最近 2022-05-14
3不同的人
3活跃月份
3讨论串
88被引(OpenAlex)

均值、方差等汇总统计很容易在大型分布式数据流上维护,但次序统计量(样本分位数)只能近似汇总。已有分位数草图文献侧重在小内存下限制秩误差,但秩误差保证并不能排除任意大的相对误差,数据严重偏斜时这在实践中常发生;而分布式大规模系统又要求草图可合并,合并后的多个草图要与同一数据的单个草图同样准确。论文提出首个具备形式化保证、完全可合并且带相对误差保证的分位数草图算法,极快且准确,目前已被 Datadog 大规模使用。

HN 为什么提它

评论者把它与同类的 UDDSketch 一起提及,称赞这类草图能给出相对误差保证,并引用它声称每个百分位都有固定的相对误差比例。

方法难度 3 / 5约 50 分钟经得起时间
读之前最好知道
1分位数与次序统计量
2数据流与草图(sketch)算法
3相对误差与秩误差
4对数分桶(logarithmic bucketing)
5分布式系统中的可合并摘要

HN 书评

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

“we also used uddsketch[1] which provides relative error guarantees, which is pretty nifty.”

提到自己还用了带相对误差保证的 UDDSketch
How percentile approximation works and why it's more useful than averages原评论 ↗
引用sujayakar · 2022-05

“The linked paper [3] claims a fixed percentage of relative error per percentile.”

引它说明声称每个分位数有固定比例的相对误差
Monarch: Google’s Planet-Scale In-Memory Time Series Database原评论 ↗
被提交为 story · 1 次