计算分布式数据的四分位数

我有一个小型数据库集群（4盒），每台机器都有一个整体数据集的碎片。

我需要为特定数据点计算四分位数，但是我需要这样做，而无需一次访问整个数据集。

这甚至可能吗？

编辑我宁愿确切的答案，但一个合理的近似值也可能工作。

可能值得说明您是否需要确切的答案，或者会对合理的近似值感到满意。（+1） – NPE 2013-04-05 15:26:49

在这种情况下，您无法计算确切的四分位数，但QDigest算法可以解决您的问题。你可以得到近似值，这是相当不错的。你可以检查一次，Java的实现可以在这里找到：https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/quantile/QDigest.java。

有了这个，您可以在每个群集上创建QDigest数据结构。它的超级压缩数据结构，将保留数据集的四分位数摘要。而且，您可以执行这些数据结构的联合，从而解决您的问题。

因此，在每个集群上创建一个QDigest实例，并合并结果，只需为每个集群执行这些实例的联合，即可为您提供相当好的四分位数的近似值。

你可以按照QDigest的文件了解细节。

2014-01-13 11:42:36 bistaumanga

我想这可能是不可能的，因为你说数据库很小。如果它是一个大型数据集，并且每个集群都包含1/4代表性样本，那么我想您可以将特定数据点与一个集群中保存的数据进行比较。

数据集中每个分片的统计量之间是否存在很大差异？

2013-04-05 15:34:54 James

集群很小，但数据库的大小有点大（取决于您的大的定义...也许总共100Gb）。四分位数只需要计算超过200k点，每台服务器上有50k点。这些点随机分布在碎片上。 – 2013-04-05 15:38:35

那么这样的样本量和随机分布的碎片我不认为你会看到一个很大的差异，如果你计算四分位数在一台服务器或全部4.你的答案不会是确切的，但我希望一个合理的近似。 – James 2013-04-05 15:44:33

回答