布盧姆過濾器的替代品

Question

我曾嘗試使用布隆過濾器進行會員資格測試。我希望對800億個條目進行會員測試，只允許發生大約100次衝突，即只有100個條目可能會出現假陽性結果。

我知道這可以通過布隆過濾器來實現，但是使用公式來確定每個條目所需的位數以及給定允許的誤報率的哈希函數的數量。我想我最終會使用270 GB的內存和19個散列函數。

我也看過杜鵑過濾器，但其內存要求與我的要求不符。我的要求如下：在最大6位每個元素

使用不超過7-8散列函數

1. 使用。

有人可能會建議我一個概率數據結構，除了上面提到的可以幫助實現我的要求嗎？

Answer 1

散列函數的數量問題並不是真正的問題 - 只需選擇一個具有多位輸出的散列函數，並將這些位分成好幾個位，就好像它們來自單獨的散列函數一樣。這裏真正的問題是存儲空間的誤報率。

你說

我想只有 允許大約100碰撞發生，即只有100個條目可以 給出假陽性結果80個十億條目執行成員測試。

根據定義，地圖中的條目可以不是false肯定。他們是true positives。

接下來的問題是「你打算測試多少個條目 需要100個誤報？」如果答案奇怪的話，也就是800億，那麼你就要求大約100/80,000,000,000 = 1/800,000,000，小於2^-29的假陽性率。

布魯姆濾波器或布穀鳥濾波器等任何近似成員數據結構的最小空間是n lg 1 /ε位，其中n是結構中元素的數量，lg是對數基2，ε是假陽性率。換句話說，每個元素需要超過29位才能達到每800億100個假陽性率。每個元素6位會得到1.56％的假陽性率最多爲。這是每80億十億12.5億，或每6400 100.

據我所知，沒有已知的實際數據結構接近實現這一目標。例如，布盧姆過濾器不會，因爲他們使用每個項目超過lg 1 /ε比特。杜鵑過濾器並不是因爲它們每個項目至少使用了兩個額外的元數據位，並且具有與lg n一致的每項比特率。