ブルームフィルタは、要素がセットのメンバーであるかをテストするために使用される確率的データ構造です。 彼らは、スペースと速度の面で効率的であり、クイックメンバーシップの問い合わせがいくつかの許容された偽陽性で要求されるアプリケーションに適しています。

ブルームフィルターの仕組み

Bloom filter はビット配列と複数のハッシュ関数を使用します。要素が追加されると、各ハッシュ関数は配列の位置にマップし、そのビットを 1 に設定します。要素が存在するかどうかを確認するには、同じハッシュ関数が適用され、対応するビットが検査されます。もし、全ての要素が 1 に設定されている場合、要素はセットにおそらく存在します。もし 0 なら、それは間違いなくありません。

フローズンフィルターの計算

偽陽性確率はビット配列(m)、インサートされた要素(n)、ハッシュ関数(k)の数値の大きさによって異なります。偽陽性の確率(p)は、次の方法で推定できます。

p ≈(1 - e]-kn/m]])k ]

k と m の最適な値が与えられた n に対して false の正当を最小限にすることができます。通常、k は次のように選択されます。

k = (m/n) * ln 2

ブルームフィルターのケースを使用する

さまざまなフィールドで、Bloom filter が使用されます。

  • クイックメンバーシップテストのためのデータベースシステム
  • ディスクの検索を減らすWebキャッシュ
  • データの同期のための分散システム
  • スパムフィルタリングのためのネットワークセキュリティ

ブルームフィルタの制限

効率的な中、ブルームフィルタは制限があります。それらは偽陽性を生成することができますが、偽のマイナスを生成することはできません。ビットが1に設定されると、それらはリセットされず、それは時間の経過とともに不正確につながることができます。彼らはまた、追加のデータ構造なしで個々の要素を削除するために適していません。