ブルーム フィルターが Web クローリングでどのように役立つか、特に URL が既にクロールされているかどうかを判断するのに役立つという話をよく耳にします (ブルーム フィルターはセット メンバーシップのテストでメモリ効率が高いため)。
しかし、Web クローリングの使用例では、遭遇する URL の数がほぼ無限であることを考えると、ビット/バケットの数を膨大にする必要があるのではないでしょうか? 特に、毎日データをクロールしようとしている Google や検索エンジンの場合はなおさらです。
私の質問は、URL の数が増え続け、バケットの数が一定のままである場合に、URL が既にクロールされているかどうかを判断するのにブルーム フィルターがどのように役立つかということです。
ブルーム フィルターは、有限範囲の値を生成するハッシュ関数に基づいています。遭遇する URL の数に関係なく、各関数はその範囲内の値の 1 つを返します。複数のハッシュ関数を使用してビットを選択すると、誤検知の可能性が低くなりますが、常に可能性があります。ただし、確率は低く、精度と効率の間で計算されたトレードオフです。
URL の長さには実質的な制限があります。この質問を参照してください。確かにそれは驚異的な数です。より多くの URL が作成されると、ハッシュ関数とバケット サイズをアップグレードする必要があるかもしれませんが、現在利用可能なものは、許容できるほど小さいエラー率で、現在利用可能な URL に十分対応できます。
このユース ケースでは、膨大な数のバケットがない限り、大量の誤検知が発生することになります (小さなアプリであっても、誤検知を完全に排除することはほとんど不可能です)。
興味深い回避策の 1 つは、フラットな構造ではなく複数レベルのブルーム フィルターを使用することです。たとえば、最初のレベルはドメイン名 (cnn.com など) のみに基づいており、次のレベルには拡張 URL (など) が含まれる場合があります。 cnn.com/sports/athletics として）。しかし、文字列操作と複数のハッシュ関数が関係している場合、これがどれだけうまく機能するかはわかりません.