ブルームフィルタとは？
ぶるーむふぃるた
ブルームフィルタとは、あるデータが集合に含まれているかどうかを高速かつ省メモリで確率的に判定するデータ構造です。
ブルームフィルタ（Bloom Filter）は、1970年にバートン・ハワード・ブルームが考案した確率的データ構造です。大量のデータの中に特定の要素が「存在しない」ことを確実に、また「存在する可能性がある」ことを高速・省メモリで判定できるのが特長です。
仕組みはビット配列と複数のハッシュ関数を組み合わせたものです。要素を追加する際は、複数のハッシュ関数でハッシュ値を計算し、対応するビットを1に立てます。判定時も同様にハッシュを計算し、すべての対応ビットが1であれば「含まれている可能性あり（偽陽性あり）」、ひとつでも0なら「確実に含まれていない」と判断します。
主な特性は以下の通りです。
- 偽陰性（falseになるべきものがtrueになる）は絶対に起きない
- 偽陽性（trueになるべきものがfalseになる）は一定確率で起きる
- 要素を削除することは基本的に不可能（変形版のカウンティングブルームフィルタでは可能）
- メモリ使用量が非常に少ない
実際の活用例としては、Webブラウザの安全でないURLの高速チェック、データベースの不要なディスクアクセス削減、ネットワークルーターのパケットフィルタリング、分散システムでのキャッシュ確認などがあります。精度よりも速度・省メモリを優先する場面で威力を発揮するデータ構造です。
使い方・例文
「GoogleのBigtableやApache Cassandraはブルームフィルタを使って、存在しないキーへのディスクI/Oを事前に弾くことで読み取り性能を向上させている。」
この用語をシェア
最終更新: