ブルームフィルタダイナミックセットを扱うときに考えられる問題

Question

ダイナミックセットを使用したブルームフィルタの考えられる問題を理解していません。

要素の追加/削除時に発生する可能性のある問題を教えてください。

Answer 1

主な問題はブルームフィルタが除去のために設計されていないことです。

たとえば、

h1(x) = x %5 
h2(x) = (x+2) % 5 

を想定し、あなたはセットでの2つの要素持って考えてみます。2,4を。

あなたはビットセットを持っている：

bitset = { 0, 1, 1, 0, 1 } 

は今、あなたはセットから2を削除したいです。どうやってやるの？あなたは、あなたが4がそれであるかどうかを確認しようとした場合、今

bitset' = { 0, 0, 1, 0, 0 } 

しかし：あなたはビットセット[4]の両方の要素に共通する見当がつかない、とあなたはそれを削除したら、新しいビットセットを取得します間違った答えを得るだろう。

ブルームフィルタへの除去を可能にする解決策は、counting bloom filtersですが、ネガもあります。

---

もう1つの問題は、あなたのセットがダイナミックで成長し続けることができる場合です。サイズを大きくすることは自明ではありません。単純にスペースを2倍にしてコレクション全体を再ハッシュすることはできません。オリジナルの要素が何であるか分かりません。

したがって、サイズが既知（または有界）の場合、ブルームフィルタが使用されます。