引用djk447 · 2021-09
“we also used uddsketch[1] which provides relative error guarantees, which is pretty nifty.”
提到自己还用了带相对误差保证的 UDDSketch
首个完全可合并、有相对误差形式保证的分位数草图,Datadog 已大规模使用
均值、方差等汇总统计很容易在大型分布式数据流上维护,但次序统计量(样本分位数)只能近似汇总。已有分位数草图文献侧重在小内存下限制秩误差,但秩误差保证并不能排除任意大的相对误差,数据严重偏斜时这在实践中常发生;而分布式大规模系统又要求草图可合并,合并后的多个草图要与同一数据的单个草图同样准确。论文提出首个具备形式化保证、完全可合并且带相对误差保证的分位数草图算法,极快且准确,目前已被 Datadog 大规模使用。
评论者把它与同类的 UDDSketch 一起提及,称赞这类草图能给出相对误差保证,并引用它声称每个百分位都有固定的相对误差比例。
“we also used uddsketch[1] which provides relative error guarantees, which is pretty nifty.”
“The linked paper [3] claims a fixed percentage of relative error per percentile.”