高效估計的大名單

這個問題的獨特元素的數量是有點類似於通過reservoir sampling解決，但不一樣的。我認爲它也是一個相當有趣的問題。高效估計的大名單

我有一個大的數據集（通常億萬元素），我想估計此數據集的獨特元素的數量。在典型的數據集中，可能存在幾個到數百萬個獨特元素。

當然，顯而易見的解決方案是維護一個正在運行的元素的運行哈希集，並在最後對它們進行計數，這將產生一個確切的結果，但是需要我將潛在的大量狀態與我一起作爲我掃描數據集（即到目前爲止遇到的所有獨特元素）。

不幸的是在我的情況，這將需要更多的內存比提供給我（沒有什麼數據集可能比可用RAM大）。

我想知道是否會有一個統計方法，這將允許我做一個單一的通過數據集，並提出一個估計獨特的元素計數在最後，同時保持相對較少的狀態而我掃描數據集。

的輸入算法將數據集（在Java中的說法迭代器），它會返回一個估計唯一對象計數（可能是一個浮點數）。假設這些對象可以被散列（也就是說，如果你願意，你可以把它們放在一個HashSet中）。通常他們將是字符串或數字。

來源

2009-12-30 sanity

你可以用一個合理的下界Bloom Filter。您只需要傳遞數據，計算並插入絕對不在集合中的項目。

來源

2009-12-30 16:33:08

啊，好主意 - 因爲我已經非常熟悉布盧姆過濾器，所以我自己想一點也沒有想過。 – sanity 2009-12-30 16:34:21

我正在考慮布盧姆過濾器，但我認爲你必須在這裏小心。如果您發現與過濾器相匹配的內容，這意味着您可能已經看到了它，或者您可能得到了誤報。如果它不匹配過濾器，那麼你肯定還沒有看過它。問題是，你擁有的元素越多，誤報的可能性就越大，這實際上會減少你的數量。我沒有詳細說明這一點，但我擔心你可能會看到一些使用布隆過濾器解決此問題的奇怪效果。 – 2009-12-30 16:44:27

布賴恩，我在想，不是每次我看到一個我認爲是新的元素時，都會增加1.0，P增加了1.0-P，其中P是誤報的概率（可以很容易計算）。 – sanity 2009-12-30 17:08:54

如果您有您信任的散列函數，那麼你可以保持一個HashSet，就像你的精確解，但拋出其哈希值是一些小範圍以外的任何項目。例如，使用32位散列，但只保留散列的前兩位爲0的項目。然後在末尾乘以適當的因子以近似唯一元素的總數。

來源

2009-12-30 16:35:15

這個問題在文獻中已得到很好的解決;對各種方法的好評是http://www.edbt.org/Proceedings/2008-Nantes/papers/p618-Metwally.pdf。最簡單的方法（對於非常高的精度要求最緊湊）稱爲線性計數。您可以像布洛姆過濾器那樣將元素散列到位向量中的位置（除了只需要一個散列函數），但最後可以通過公式D = -total_bits * ln（unset_bits/total_bits）估計不同元素的數量。。詳情在文件中。

來源

2012-03-14 00:40:04 senderista

高效估計的大名單

回答

相關問題