機率很低的概率集

Question

我正在尋找一個集合數據結構，該集合數據結構對於一個項目是該集合的一部分的可能性很低而進行了優化。

用例是Gnip/Twitter合規性流水，每秒我們獲得約1,000個事件（這是所有Twitter的刪除）。我們有一個表格，比方說1000萬個存儲推文（每年增加這個數量），如果一個項目出現在流水帳中，我必須刪除它。我猜測每10萬秒會有一場比賽（將空氣中的數字拉出）。

我曾想過一個布隆過濾器，可能是幾個鏈接，但考慮到有一個非常低的命中機率，我總是需要通過整個鏈，事情最終會達到線性。

有沒有一個很好的次線性數據結構呢？

Answer 1

我沒有看到問題。在我看來，如果檢查布隆過濾器告訴你存儲了推文，則可以在數據存儲中查找推文。如果它在那裏，你刪除它。如果不存在，則不要刪除它。

你有1000萬個存儲推文，你預計它每年增長約1000萬。因此，建立一個容量爲十億的布隆過濾器，誤報概率爲0.1％。根據Bloomfilter calculator，這將花費你1.67千兆字節。

瞭解，「誤報」數字假定過濾器包含10億個密鑰。當你的過濾器非常稀疏時，誤報的可能性要低得多。

如果您每秒獲得一千條推文，布隆過濾器的誤報率爲0.1％，那麼在最壞的情況下，您會得到每秒一個誤報的平均值。因此，每秒一次的代碼將不得不擊中數據庫以確定推文是否存在。

但是，要達到這一點還需要很多年。只有1000萬現有記錄和每年1000萬的增長率，這個過濾器甚至會在10％滿的前10年。您可能會將過濾器大小降至5億（860 MB），並且由於誤報而仍然沒有受到重大打擊。

Answer 2

Bloom Filter應該沒問題，假設它適合內存。如果它不能完全適應內存，請考慮使用this paper中描述的解決方案。另外，如果你真的想擠一點額外的性能，你可以使用一個Cuckoo Filter，但它會很難找到一個開源的實現;這裏是Go中的一個。