ブルームフィルタはいつ便利ですか？

Question

私はブルームフィルタを魅力的なデータ構造にする理由を理解しています。しかし、私はあなたが偽陽性を発見していないことを確かめるために避けようとしている高価な操作をまだ実行しなければならないので、いつ使用することができるのかを本当に理解するのが難しいと感じています。このため、一般的にオーバーヘッドを増やすことはありませんか？例えば、ブルームフィルタのためのウィキペディア記事は、それらがデータ同期に使用できることを示唆しています。ブルームフィルタが空になっても、何も変更していないと言い、データを再度同期させると言うと、初めて周りがうまくいく方法がわかります。今度はBloomフィルタを検索するたびに、そのファイルがすでにコピーされているとレポートされますが、実際に正しいかどうかを確認するために避けようとしている低速ルックアップタスクを実行する必要はありませんか？

Answer 1

基本的には、Bloomフィルタを使用して、アイテムがデータ構造内に存在しないことを証明する、長くて厄介な作業を回避します。何かが欠けているかどうかを判断することはほとんどいつも難しいので、フィルタはあなたが見つけられないものを探し出す損失を助長します。それはいつもうまくいくわけではありませんが、いつそれは大きな利益を得るのですか？

Answer 2

メンバーシップクエリの場合、つまり要素がセットに属しているかどうかを調べるのに、Bloomフィルタは非常に効率的です。セット内の要素の数は、クエリのパフォーマンスに影響しません。