在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級數據集

回答

相關問題