algorithm - ブルームフィルターの使用法

Question

ブルームフィルターの有用性を理解するのに苦労しています。その基礎となるロジック、スペースの圧縮、高速ルックアップ、誤検知などを取得します。その概念を実際の状況に有益なものとして組み込むことはできません。よくあるアプリケーションの1つは、Webキャッシングでのブルームフィルターの使用です。ブルームフィルターを使用して、特定のURLがキャッシュにあるかどうかを判断します。それを判断するために、単にキャッシュにアクセスしないのはなぜですか？はいの場合は、キャッシュに移動してWebページ（そこにない可能性があります）を取得する必要がありますが、いいえの場合は、キャッシュを使用して同じ答えを得ることができます（おそらく高速ルックアップ用に最適化されています）とりあえず？）。

Answer 1

ブルームフィルターは、誤検知が非常に悪いことであり、誤検知が許容される状況向けに設計されています。

たとえば、Webブラウザを作成していて、詐欺Webサイトの既知のブラックリストがあるとします。ブラックリストは膨大で（数百ギガバイト）、ブラウザに同梱することはできません。ただし、独自のサーバーに保存することはできます。その場合、すべてのURLを保持する適切なサイズのブルームフィルターを備えたブラウザーを出荷できます。サイトにアクセスする前に、フィルターで検索します。次に、「いいえ」の回答が得られた場合、URLはブラックリストに登録されておらず、サイトにアクセスできることが保証されます。「はい」と答えた場合、サイトは悪意のあるものである可能性があるため、ブラウザにメインサーバーを呼び出して、実際の答えを得ることができます。精度を犠牲にすることなく、ここでサーバーへの膨大な数の呼び出しを節約できるという事実は重要です。

キャッシュの考え方は、この設定に似ています。フィルタをクエリして、ページがキャッシュにあるかどうかを確認できます。「いいえ」の答えが得られた場合は、キャッシュされていないことが保証され、メインソースからデータをプルするためにコストのかかる操作を実行できます。それ以外の場合は、キャッシュをチェックして、実際にキャッシュが存在するかどうかを確認できます。まれに、キャッシュをチェックして、キャッシュが存在しないことを確認してから、メインソースからプルする必要がある場合がありますが、実際にキャッシュにあるものを誤って見逃すことはありません。

お役に立てれば！

Answer 2

ブルームフィルターは、次の両方の条件が満たされている場合に役立つことがあります。

• 偽陰性は受け入れられません
• ブルームフィルターでのルックアップのコストに比べて、ルックアップのコストは高くなります

最初のポイントは非常に単純です。ブルームフィルターをプライマリメモリに格納できる場合、2番目のポイントは一般に重要になりますが、実際のルックアップではデータベースヒットが発生する可能性があり、キーに対していくつかのハッシュを実行してからメモリ内ルックアップを実行する場合に比べて非常に「コストがかかる」可能性があります。ブルームフィルター）。

上記の基準の1つだけが満たされている場合、ブルームフィルターは問題の最善の解決策ではありません。

一致する可能性がないことがわかっているため、コストのかかるルックアップを排除できる場合に節約になります。これは最初のポイントの値です-ブルームフィルターはフォールスネガティブを生成しないため、フィルターで一致が見つからない場合、キーに関連付けられたデータを取得する次のよりコストのかかるステップに進むポイントはありません。

フィルタにヒットがあった場合、ヒットを検証し（誤検知を排除）、関連データを取得するために、コストのかかるルックアップが必要になります。ここでは、誤検知が原因で何も見つからない可能性があります。そのため、このリスクを許容レベルに最小化するためにフィルターを調整する必要があります。機能的なブルームフィルターは、ルックアップの全体的なコストを低く抑えるために、偽陽性率を低くする必要があります。

さて、あなたが言うように、あなたのキャッシュがすでに高速ルックアップのために最適化されているなら、ブルームフィルターの有用性は疑わしいかもしれません。

Answer 3

問題は、あなたの例がそれほど素晴らしいものではないということです。

Webキャッシュでは、URLが存在しない場合は、とにかくネットに高額な呼び出しを行う必要があるため、ディスクアクセスを節約することは大したことではありません。ですから、あなたはこれに疑問を投げかけるのは正しいです（そして、Diego Baschのコメントはあまりよく考えられていません、imho）。

だから私はあなたがその例を使った理由を探しに行きました。ウィキペディアの記事には、イカのWebキャッシュがブルームフィルターを使用していると記載されていることがわかりました。しかし、それらはあなたが説明した方法では使用されていません。代わりに、分散キャッシュのセットから選択するキャッシュを決定するために使用されます。そして、それらは主にスペースを節約するために使用されます（squidは多くのオブジェクトをキャッシュできるため、これらのテーブルは非常に大きくなります）。

イカとブルームフィルターの詳細については、http： //wiki.squid-cache.org/SquidFaq/CacheDigestsを参照してください。

それ以外の場合は、templatetypedefからの別の回答で問題ありません。不良サイトのチェックは、はるかに良い例です。