如何在Python中有效地計算超大型數據集的基數？

我一直在使用一些非常大型的數據集，通常是數十億個元素，這些數據都保存在一個memcached雲中並定期轉儲到文件中，對於我的其中一項任務，我試圖計數這套的基數。如何在Python中有效地計算超大型數據集的基數？

對於某些情況下，每個項目包含一個IP和一些其他屬性標識一個人，並在base64中編碼，項目大小爲20個字節。通過刪除一些字段來減少項目的大小是不可能的。

這裏的東西，模仿我的數據集作爲一個內存版本（感謝this post字符串代）：

import base64, os 

dataset_size = 10000000000 # that's 10 billion, be careful if you run it ! 
big_dataset = [base64.b64encode(os.urandom(10)) for i in range(dataset_size)]

我的第一個方法是使用這樣一個HashSet：

uniques = set(big_dataset) 
print "Cardinality: %d" % len(uniques)

雖然這在理論上可以在小數據集上正常工作，但您可以猜到這是一個呃逆：

我無法對數據的唯一性做任何假設。我可以擁有50％的獨特數據集，或者我也可以擁有100％的數據集。這是以固定的時間間隔動態生成的，並且取決於許多因素（例如，一天中的時間）而變化。
數據集大小在100億。以64爲基數編碼的每個項目是20個字節，時間100億是平均數百兆字節。不幸的是，我沒有機會獲得那麼多的RAM！

我已經完成了我的作業，發現至多一些研究論文，或者一些不起眼的圖書館，但是其目標的一部分是瞭解什麼方法可行，爲什麼。

所以我打電話給你Python用戶，你知道任何算法，可以幫助我有效地估計基數嗎？就複雜性而言，我的意思是我並不在乎運行時間的複雜性，但我更關注空間複雜性。我不介意犧牲一點準確性，如果它能夠極大地提高性能（所以我不一定需要知道確切的唯一身份數，即使這是理想的，但可能不是一個可行的方法）。我會說高達5％是可以接受的。我正在爲這個項目尋找專門針對Python的東西。

感謝您提供任何幫助！如有人指出，我可以使用Hadoop/MR，但是對於這個特定的項目，我們不想採用MR方式，並且希望能夠在單臺機器上有效地探索算法，因爲這可能會適用於其他幾個不同的項目。

來源

2012-04-15 Charles Menguy

只是一個建議，但這聽起來像是一些可能對Map-Reduce框架有好處的東西 - 將數據中的元素映射到字典中的計數或某物。爲此，您可以使用由Yelp創建的Python Map-Reduce框架[MRJob]（https://github.com/Yelp/mrjob）。使用MRJob在Amazon EC2上運行它也可能是一個好主意。我以前曾經用它來處理大型文字的頻率計數。我想這完全取決於你如何解析單個數據元素。 – ely 2012-04-15 18:05:58

感謝您的建議，是的，我已經考慮過MR（實際上我在其他項目中使用過它），但對於這個特定問題，MR/Hadoop不是一種選擇，我們希望研究算法作爲概念證明的一部分，在一臺機器上做這件事。 – 2012-04-15 18:08:22

如果100％的準確性不重要，也許一個布隆過濾器會給你5％的錯誤將適合內存？如果沒有，並且需要一臺計算機，則可以簡單地使用一些簡單的nosql數據庫和唯一的密鑰，這些密鑰存儲在磁盤上並刪除重複項。它會很慢，但它可以適用於你擁有的任何數量的內存。您仍然可以並行實際插入工作。 – 2012-04-15 18:52:56

我會推薦使用哈希草圖，即（超級）日誌日誌草圖或超級日誌草圖。

您可以檢查並可能使用，提高了簡單的Python實現，我提出： https://github.com/goncalvesnelson/Log-Log-Sketch

來源

2012-04-15 20:03:04 goncalvesnelson

真棒，它與前一篇文章中提到的Bloom Filter相比如何？你知道使用LogLog/HyperLog的優點和缺點嗎？ – 2012-04-15 22:18:06

這些技術的主要問題是它們對小基數的不準確性（<2000）。在下面的圖表[Bloom Filters vs散列草圖]（http://cl.ly/1u0v0V402W3Y2l0F1A1n）中可以看到，對於幾乎達到2000個元素的小基數，它們的誤差大於5％，但對於更大的基數，它們的錯誤是低於你想要的5％。儘管與Bloom Filters沒有相同的精度，但看看[this]（http://cl.ly/3M2T1h3s1T2e1G0N1u1K），您可以檢查這兩種技術在空間方面效率更高。 – goncalvesnelson 2012-04-15 23:35:38

@goncalvesnelson是可用於生成這兩個圖的任何源代碼？ – 2016-01-08 23:01:46

我會建議你嘗試與布隆過濾器。即使有這麼多的數據，只要適度的系統要求，您可以實現極低的錯誤率。假設您將使用（粗略）最優的k = ln（2）*（布盧姆過濾器的大小，位數）/（10億），您可以計算您的布隆過濾器的大小，比特爲 - （（10億）* ln率））/ LN（2）^ 2。

例如，如果內存小於2gig，您可以獲得0.1％的錯誤率。一個非常快速和極其簡單的實現是所有這一切都是http://mike.axiak.net/python-bloom-filter/docs/html/

來源

2012-04-15 20:12:47 yahe

這聽起來很酷！我會試一試，但聽起來很有希望！ – 2012-04-15 22:17:04

如何在Python中有效地計算超大型數據集的基數？

回答

相關問題