database - 计算 TB 数据集中分位数的高效算法

Question

我正在尝试为一个巨大的数据集(TB 级数据)计算分位数(可以通过一些精度保证或误差界限来近似)。我怎样才能有效地计算分位数。要求是

1) Can be computed efficiently (one-pass) or in a distributed way (merging)
2) High accuracy (or at least can be controlled)
3) Can be re-computed or reproduced in multiple language (java and python)
4) Incrementally updated (not a requirement but good to have)

我正在寻找的几种方法是:

1) The naive solution : reservoir sampling (not sure how to do it in
distributed map reduce way specially how to merge different reservoir samples for same data or two different distributions, are there any
good implementations ? )

2) t-digest

3) Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. Approximate medians and other quantiles in one pass and with
limited memory. (Reason being i think some map reduce frameworks like dataflow and BigQuery already implement variation of this AFAIK)

有使用这些算法和技术经验的人能否为我提供一些建议，说明每种 .何时使用哪种方法，如果要求是有效的计算和更好的准确性，那么一种方法可以说比其他方法更好。

我没有特别使用基于摘要的方法，并且想更好地理解为什么以及什么时候我更喜欢像 t-digest 这样的方法而不是像水库采样这样简单的方法来计算近似分位数。

Answer 1

更新:似乎出现了一种新的非常好的算法，称为 KLL。参见 paper .它有一个实现 in Python和 in Go .

t-digest有多种语言的实现并满足您的所有要求。参见 the paper与其他一些算法进行比较，例如到 Q-文摘。您可以在 Q-Digest paper 中查找更多比较.

一般来说，这两种算法都远优于用于估计分位数的基于采样的算法，因为在给定相同存储量的情况下提供更高的准确性。您可以在优秀书籍 Data Streams: Algorithms and Applications 中寻找更多近似算法的讨论。 (它不讨论 t-digest，因为它是在本书出版后创建的)。

可能还有其他我不熟悉的更好的算法。

目前没有用于 t-digest 库的 Beam 包装器，但使用自定义 CombineFn 开发一个应该不难。参见，例如，a current pending PR使用 CombineFn 添加对不同近似算法的支持。