[解決済み] ブルームフィルターを使用するメリットは何ですか？

質問

ブルームフィルタについて読んでいるのですが、馬鹿馬鹿しいとしか思えません。 ブルーム・フィルターで達成できることはすべて、より少ないスペースで、より効率的に、複数のハッシュ関数ではなく単一のハッシュ関数を使用して達成できる、あるいはそのように思われます。 なぜブルームフィルターを使用するのでしょうか、そしてどのように役立つのでしょうか？

どのように解決するのか？

から ウィキペディア :

ブルームフィルタは、他のデータ構造よりも空間的に 他のデータ構造より優れています。 のような集合を表現するための 自己調整型バイナリ探索木 トライ，ハッシュテーブル，あるいは単純な配列や やエントリのリンクリストなど，集合を表現するための他のデータ構造よりも空間的に有利です．ほとんどの場合 これらのほとんどは、少なくともデータ項目そのものを格納する必要があります。 データ項目そのものを格納する必要があります。 小さな整数の場合は 小さな整数のような小さなビット数から のような任意の数のビットを必要とします。 文字列のような任意のビット数を必要とします（トライは例外です。 トライは例外で、同じ接頭辞を持つ要素間でストレージを共有することができます。 のような任意のビット数を必要とします（トライは例外で，同じ接頭辞を持つ要素間でストレージを共有することができます）．リンクされた 構造体では，ポインタのための線形空間オーバーヘッドが追加されます． 空間オーバーヘッドが発生します．ブルーム フィルタが1%の誤差で最適な 一方、誤差1%でkの値が最適なブルームフィルタは 要素あたり約9.6ビットを必要とします。 要素のサイズに関係なく で済む。この優位性は この利点は、配列から受け継いだコンパクトさ この利点は、配列から受け継いだコンパクトさと 確率的な性質がある。もし1%の誤検出率 誤検出率が1％では高すぎると思われる場合、その都度 1要素あたり約4.8ビットを追加するたびに を追加するたびに、10 倍に減少します。

私にはかなり明確です。

ブルーム・フィルターは要素そのものを保存するわけではない、これが重要なポイントです。要素が存在するかどうかをテストするためにブルームフィルタを使用するのではなく、要素が確かに存在するかどうかをテストするために使用するのです。 ではなく が存在するかどうかをテストするために使用します。これにより、セット内に存在しない要素のために余分な作業（それらを調べるためのディスクIOなど）をする必要がなくなります。

そして、ハッシュ テーブルのようなもの (大規模なデータ セットでは部分的にディスクになる可能性があります) よりも、はるかに少ないスペースですべてが行われます。ブルーム フィルターを使用することもできますが を併用することができます。 をハッシュ テーブルのような構造と組み合わせて使用することもできますが、要素が存在する可能性があることが確認されれば、ブルーム フィルターを使用することもできます。

というわけで、使用パターンの例としては、以下のようなものがあります。

ディスク上に大量のデータがある場合、どのようなエラー境界（例えば1％）が必要かを決定し、その境界で m . そして、最適な k が決定される(記事中の式から)。このディスクバインドされたデータから一度だけフィルタを投入するのです。

これでRAM上にフィルターができました。ある要素を処理する必要があるとき、その要素がデータセットに存在する可能性があるかどうかを確認するためにフィルタに問い合わせをします。存在しない場合、余分な作業は行われません。ディスクの読み出しなどもありません。(ハッシュやツリーなどであれば必要ですが)。

そうでなければ、フィルターが「はい、入っています」と言った場合、それが間違っている可能性が1%あるので、それを見つけるために必要な作業をします。99% の確率で、それは本当に になります。 99% の確率で、本当にそこにあるのですから、その作業は無駄ではありません。