我试图计算位数计算位数高效的算法(可近似具有一定精确度保证或错误边界)一个巨大的数据集(万亿字节的数据)。我如何有效地计算分位数。要求是在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)天真的解决方案:水库取样(不知道怎么做,在
分布地图缩小的方式专门如何合并不同水库相同数据 样品或两个不同的分布,是否有任何
好的实现?)2)叔消化
3)古米特·辛格曼梏,斯里达尔拉贾戈帕兰,和Bruce G.林赛。 近似中位数和其他分位数在一次通过并且与
有限的记忆。 (原因是我觉得有些地图缩小框架,如 数据流和大量查询已经实现了这个AFAIK的变化)
可有人谁拥有了与这些算法的工作以前的经验和技术提供给我什么是告诫一些指点,每个人的利弊。何时使用哪种方法,如果要求有效计算和准确度更好,则可以说是一种比其他方法更好的方法。
我还没有特别用于消化为基础的方法,并想更好地了解为什么以及何时会我更喜欢像过一些简单的像水库取样来计算近似分位数T-消化。
你的数据集是如何格式化的? –
@AndrewMo:你能澄清你的意思,以及它的重要性。您可以假设为几百列(对于每个需要计算分位数的列)以及分布式文件系统上的avro文件。每一列都是不同的,并有自己的分布 – user179156
为什么不把它推到BigQuery中,并用SQL命中?BigQuery会在早餐时吃TB:https://cloud.google.com/bigquery/docs/reference/standard-sql/functions-and-operators#approx_quantiles –