Bloom Filter
ブルームフィルタは k 個のハッシュ関数とビット配列で集合の所属を近似し、偽陽性率と引き換えに容量効率を得る。
目的
キャッシュやデータベースに対して、容量効率の良い近似所属問い合わせを提供する。
メカニズム
挿入では要素を k 個の関数でハッシュして対応するビットを立てる。問い合わせでは k 個のビットがすべて 1 なら要素は存在する可能性が高い（偽陽性率は p≈(1-e^(-kn/m))^k）。偽陰性は決して生じない。標準版では削除はサポートされない。
ユースケース
- キャッシュのフィルタリング
- データベースクエリの最適化
- データの重複排除