在TB级数据集

我试图计算位数计算位数高效的算法（可近似具有一定精确度保证或错误边界）一个巨大的数据集（万亿字节的数据）。我如何有效地计算分位数。要求是在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-消化。

来源

2017-10-19 user179156

你的数据集是如何格式化的？ –

@AndrewMo：你能澄清你的意思，以及它的重要性。您可以假设为几百列（对于每个需要计算分位数的列）以及分布式文件系统上的avro文件。每一列都是不同的，并有自己的分布 – user179156

为什么不把它推到BigQuery中，并用SQL命中？BigQuery会在早餐时吃TB：https：//cloud.google.com/bigquery/docs/reference/standard-sql/functions-and-operators#approx_quantiles –

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

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

通常，这两种算法都远远优于基于采样的算法用于估计分位数，在给定相同的存储量给予更好的准确性方面。你可以在优秀的书Data Streams: Algorithms and Applications（它不讨论t-摘要，因为它是在书出版后创建的）中寻找关于更多近似算法的讨论。

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

目前还没有束包装为T-消化库，但它不应该是很难开发使用自定义CombineFn之一。例如，请参阅a current pending PR，使用CombineFn添加对不同近似算法的支持。

来源

2017-10-19 20:24:35 jkff

在TB级数据集

回答

相关问题