ブルームフィルタ

ブルームフィルタは、1970 年にバートン ハワード ブルームによって考案された、スペース効率の高い確率的 データ構造で、要素がセットのメンバーであるかどうかをテストするために使用されます。誤検出は可能ですが、検出漏れは発生しません。つまり、クエリは「セットに含まれる可能性がある」か「セットに含まれない」かのいずれかを返します。セットに要素を追加することはできますが、削除することはできません (ただし、カウント ブルーム フィルタのバリアントを使用すれば、この問題に対処できます)。追加される項目が多いほど、誤検出の確率が高くなります。

ブルームは、従来のエラーのないハッシュ技術を適用すると、ソース データの量によって非現実的なほど大量のメモリが必要になるアプリケーション向けにこの技術を提案しました。彼は、500,000 語の辞書のハイフネーション アルゴリズムの例を示しました。この辞書の 90% は単純なハイフネーション ルールに従いますが、残りの 10% は特定のハイフネーション パターンを取得するために高価なディスク アクセスを必要とします。十分なコア メモリがあれば、エラーのないハッシュを使用して不要なディスク アクセスをすべて排除できます。一方、コア メモリが限られている場合、ブルームの技術では、より小さなハッシュ領域を使用しますが、それでもほとんどの不要なアクセスを排除できます。たとえば、理想的なエラーのないハッシュに必要なサイズの 18% しかないハッシュ領域でも、87% のディスク アクセスを排除できます。^[1]

より一般的には、セット内の要素のサイズや数に関係なく、1％の誤検出確率を達成するには、要素あたり10ビット未満が必要です。 ^[2]

空のブルーム フィルタは、すべて 0 に設定されたmビットのビット配列です。k個の異なるハッシュ関数が装備されており、セット要素をm 個の可能な配列位置の 1 つにマッピングします。最適にするには、ハッシュ関数が均一に分散され、独立している必要があります。通常、k は、望ましい誤エラー率 εに依存する小さな定数ですが、m はkと追加される要素の数に 比例します。

要素を追加するには、それをk 個のハッシュ関数のそれぞれに入力して、k個の配列の位置を取得します。これらの位置のビットをすべて 1 に設定します。

要素がセット内にあるかどうかをテストするには、その要素をk 個のハッシュ関数のそれぞれに入力して、 k個の配列の位置を取得します。これらの位置のビットのいずれかが 0 の場合、その要素は間違いなくセット内にありません。もしセット内にあれば、挿入時にすべてのビットが 1 に設定されているはずです。すべてが 1 の場合、その要素はセット内にあるか、他の要素の挿入時にビットが偶然 1 に設定されて誤検知が発生したかのいずれかです。単純なブルーム フィルタでは、この 2 つのケースを区別する方法はありませんが、より高度な手法を使用すれば、この問題に対処できます。

k 個の異なる独立したハッシュ関数を設計するという要件は、 k が大きい場合には困難です。出力が広い優れたハッシュ関数の場合、そのようなハッシュの異なるビット フィールド間の相関はほとんどないかまったくないはずです。そのため、このタイプのハッシュを使用して、出力を複数のビット フィールドにスライスすることにより、複数の「異なる」ハッシュ関数を生成できます。または、初期値を取るハッシュ関数にk個の異なる初期値 (0、1、...、k  − 1 など) を渡すか、これらの値をキーに追加 (または追加) することができます。mおよび/またはk が大きい場合、ハッシュ関数間の独立性は、偽陽性率の増加を無視できる程度に緩和できます。^[3] (具体的には、Dillinger と Manolios (2004b) は、 2 つまたは 3 つのハッシュ値をシードとする実質的に単純な乱数ジェネレータである、拡張ダブル ハッシュ とトリプル ハッシュを使用してkインデックスを導出する有効性を示しています。)

この単純なブルーム フィルターから要素を削除することは不可能です。これは、その要素がマップされているkビットのうちのどれをクリアすべきか判断できないためです。k ビットのいずれかを 0 に設定すれば要素を削除できますが、そのビットにマップされている他の要素もすべて削除されます。この単純なアルゴリズムでは、削除する要素のビットに影響を与える他の要素が追加されているかどうかを判断する方法がないため、いずれかのビットをクリアすると偽陰性が発生する可能性があります。

ブルーム フィルターから要素を 1 回削除することは、削除されたアイテムを含む 2 番目のブルーム フィルターを用意することでシミュレートできます。ただし、2 番目のフィルターの偽陽性は複合フィルターの偽陰性になり、望ましくない場合があります。このアプローチでは、以前に削除したアイテムを再度追加することはできません。「削除された」フィルターからアイテムを削除する必要があるためです。

すべてのキーが使用可能であっても、列挙にコストがかかる (たとえば、多くのディスク読み取りが必要) ことがよくあります。誤検出率が高すぎる場合は、フィルターを再生成できますが、これは比較的まれなイベントです。

ブルーム フィルタは、誤検知のリスクはあるものの、自己平衡二分探索木、トライ、ハッシュ テーブル、エントリの単純な配列やリンク リストなどのセットを表す他のデータ構造に比べて、スペース面で大きな利点があります。これらのほとんどでは、少なくともデータ項目自体を格納する必要があり、小さな整数の場合は少数のビット、文字列の場合は任意の数のビットが必要になります (トライは同じプレフィックスを持つ要素間でストレージを共有できるため例外です)。ただし、ブルーム フィルタはデータ項目をまったく格納しないため、実際のストレージには別のソリューションを用意する必要があります。リンク構造では、ポインタ用に追加の線形スペース オーバーヘッドが発生します。これに対し、誤差が 1% でkの値が最適であるブルーム フィルタでは、要素のサイズに関係なく、要素あたり約 9.6 ビットしか必要ありません。この利点は、配列から継承されたコンパクトさや、確率的な性質に一部由来しています。要素あたり約 4.8 ビットを追加するだけで、1% の誤検出率を 10 分の 1 に削減できます。

しかし、潜在的な値の数が少なく、その多くがセット内に存在する可能性がある場合、ブルームフィルタは、各潜在的な要素に1ビットしか必要としない決定論的ビット配列によって簡単に上回られます。ハッシュテーブルは、衝突を無視し、各バケットにエントリが含まれているかどうかのみを保存すると、スペースと時間の面で有利になります。この場合、ハッシュテーブルは事実上、k = 1のブルームフィルタになります。^[4]

ブルーム フィルタには、アイテムを追加するか、アイテムがセット内にあるかどうかを確認するのに必要な時間が、セット内の既存のアイテムの数とはまったく関係なく、固定定数O( k )であるという珍しい特性もあります。他の定数空間セット データ構造にはこの特性はありませんが、スパースハッシュ テーブルの平均アクセス時間により、実際には一部のブルーム フィルタよりも高速になる可能性があります。ただし、ハードウェア実装では、ブルーム フィルタのk 回の参照が独立しており、並列化できる ため、優れています。

空間効率を理解するには、一般的なブルームフィルタとk = 1の特殊なケースを比較すると有益です。k = 1の場合、偽陽性率を十分に低く保つには、ビットのごく一部を設定する必要があります。つまり、配列は非常に大きく、ゼロが長く続く必要があります。配列のサイズに対する情報量は少ないです。一般化ブルームフィルタ ( k > 1) では、偽陽性率を低く保ちながら、さらに多くのビットを設定できます。パラメータ ( kとm ) が適切に選択されていれば、約半分のビットが設定され、^[5]これらは明らかにランダムになり、冗長性が最小限に抑えられ、情報量が最大化されます。

ハッシュ関数が各配列の位置を等確率で選択すると仮定します。配列のビット数をmとすると、要素の挿入時に特定のハッシュ関数によって特定のビットが1に設定されない確率は

${\displaystyle 1-{\frac {1}{m}}.}$

kがハッシュ関数の数であり、各ハッシュ関数間に有意な相関がない場合、どのハッシュ関数によってもビットが1に設定されない確率は

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}.}$

e ⁻¹のよく知られた恒等式を使用することができる。

${\displaystyle \lim _{m\to \infty }\left(1-{\frac {1}{m}}\right)^{m}={\frac {1}{e}}}$

結論として、mが大きい場合、

${\displaystyle \left(1-{\frac {1}{m}}\right)^{k}=\left(\left(1-{\frac {1}{m}}\right)^{m}\right)^{k/m}\approx e^{-k/m}.}$

n個の要素を挿入した場合、特定のビットがまだ0である確率は

${\displaystyle \left(1-{\frac {1}{m}}\right)^{kn}\approx e^{-kn/m};}$

したがって、それが1である確率は

${\displaystyle 1-\left(1-{\frac {1}{m}}\right)^{kn}\approx 1-e^{-kn/m}.}$

次に、セットに含まれない要素のメンバーシップをテストします。ハッシュ関数によって計算されたk個の配列の各位置は、上記の確率で 1 になります。すべてが 1 になる確率は、アルゴリズムが誤って要素がセットに含まれていると主張する原因となり、次のように表されることがよくあります。

${\displaystyle \varepsilon =\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}.}$

これは、各ビットが設定される確率が独立していると仮定しているため、厳密には正しくありません。ただし、これが近似値であると仮定すると、m (配列内のビット数) が増加すると誤検出の確率は減少し、n (挿入される要素の数) が増加すると誤検出の確率は増加することがわかります。

独立性を仮定しない場合の偽陽性の真の確率は

${\displaystyle {\frac {1}{m^{k(n+1)}}}\sum _{i=1}^{m}i^{k}i!{m \choose i}\left\{{kn \atop i}\right\}}$

ここで{括弧}は第二種スターリング数を表す。^[6]

独立性を仮定せずに同じ近似値に到達する別の分析は、ミッツェンマッハーとウプファルによって提供されています。^[7] n 個のアイテムがすべてブルーム フィルタに追加された後、0 に設定されているmビットの割合をqとします (つまり、0 に設定されているビットの数はqmです)。次に、セットに含まれない要素のメンバーシップをテストする場合、k 個のハッシュ関数のいずれかによって指定された配列の位置について、ビットが 1 に設定されていることが見つかる確率は です。したがって、 k 個のハッシュ関数すべてがビットが 1 に設定されていることを検出できる確率は です。さらに、 qの期待値は、n 個のアイテムのそれぞれについて、 k 個のハッシュ関数のそれぞれによって指定された配列の位置が変更されない確率であり、(上記のように) ${\displaystyle 1-q}$${\displaystyle (1-q)^{k}}$

${\displaystyle E[q]=\left(1-{\frac {1}{m}}\right)^{kn}}$。

独立性の仮定なしに、 qがその期待値の周囲に非常に強く集中していることを証明することは可能である。特に、東-ヘフディング不等式から、彼らは^[8]

${\displaystyle \Pr(\left|qE[q]\right|\geq {\frac {\lambda }{m}})\leq 2\exp(-2\lambda ^{2}/kn)}$

このため、偽陽性の正確な確率は

${\displaystyle \sum _{t}\Pr(q=t)(1-t)^{k}\approx (1-E[q])^{k}=\left(1-\left[1-{\frac {1}{m}}\right]^{kn}\right)^{k}\approx \left(1-e^{-kn/m}\right)^{k}}$

以前と同じように。

ハッシュ関数の数kは正の整数でなければならない。この制約を別にすれば、与えられたmとnに対して、偽陽性確率を最小にする kの値は

${\displaystyle k={\frac {m}{n}}\ln 2.}$

必要なビット数mは、n (挿入された要素の数) と望ましい偽陽性確率ε (およびkの最適値が使用されていると仮定) が与えられた場合、上記の確率式にkの最適値を代入することによって計算できます。

${\displaystyle \varepsilon =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}{m}}}\right)^{{\frac {m}{n}}\ln 2}=\left({\frac {1}{2}}\right)^{{\frac {m}{n}}\ln 2}}$

これは次のように簡略化できます。

${\displaystyle \ln(\varepsilon )=-{\frac {m}{n}}\ln(2)^{2}.}$

結果は次のようになります:

${\displaystyle m=-{\frac {n\ln(\varepsilon )}{\ln(2)^{2}}}}$

したがって、要素あたりの最適なビット数は

${\displaystyle {\frac {m}{n}}=-{\frac {\ln(\varepsilon )}{\ln(2)^{2}}}\approx -2.08\ln(\varepsilon )}$

対応するハッシュ関数の数k（整数性を無視）:

${\displaystyle k=-{\frac {\ln(\varepsilon )}{\ln(2)}}.}$

これは、与えられた偽陽性確率εに対して、ブルームフィルタの長さmはフィルタリングされる要素の数nに比例し、必要なハッシュ関数の数は対象の偽陽性確率εのみに依存することを意味する。^[9]

この式が近似的である理由は 3 つあります。まず、最も懸念される点ですが、 は と近似しますが、これは適切な漸近近似です (つまり、m →∞ のときに が成り立ちます)。次に、より懸念される点ですが、メンバーシップ テスト中に、テストされた 1 つのビットが 1 に設定されるイベントは、テストされた他のビットが 1 に設定されるイベントとは無関係であると想定しています。最後に、最も懸念される点ですが、 は偶然に整数であると想定しています。 ${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$${\displaystyle 1-{\frac {1}{m}}}$${\displaystyle e^{-{\frac {1}{m}}}}$${\displaystyle k={\frac {m}{n}}\ln 2}$

しかし、 GoelとGupta ^[10]は、近似や仮定を必要としない厳密な上限を与えている。彼らは、mビット（）とn要素、kハッシュ関数を持つ有限ブルームフィルタの偽陽性確率は最大で ${\displaystyle m>1}$

${\displaystyle \varepsilon \leq \left(1-e^{-{\frac {k(n+0.5)}{m-1}}}\right)^{k}.}$

この境界は、最大で半分の追加要素と最大で 1 ビット少ないペナルティで近似式を適用できること を意味していると解釈できます。${\displaystyle \left(1-e^{-{\frac {kn}{m}}}\right)^{k}}$

ブルームフィルタの項目数は、次の式で近似できます。

${\displaystyle n^{*}=-{\frac {m}{k}}\ln \left[1-{\frac {X}{m}}\right],}$

ここで、はフィルタ内のアイテム数の推定値、mはフィルタの長さ（サイズ）、kはハッシュ関数の数、Xは1に設定されているビットの数です。^[11]${\displaystyle n^{*}}$

ブルームフィルタは、アイテムの集合をコンパクトに表現する方法です。2つの集合の交差または結合のサイズを計算しようとするのはよくあることです。ブルームフィルタは、2つの集合の交差と結合のサイズを概算するために使用できます。長さmの2つのブルームフィルタの場合、それぞれのカウントは次のように推定できます。

${\displaystyle n(A^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A|}{m}}\right]}$

そして

${\displaystyle n(B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|B|}{m}}\right].}$

彼らの組合の規模は次のように推定できる。

${\displaystyle n(A^{*}\cup B^{*})=-{\frac {m}{k}}\ln \left[1-{\frac {|A\cup B|}{m}}\right],}$

ここで、2つのブルームフィルタのいずれかで1に設定されているビットの数です。最後に、交差は次のように推定できます。 ${\displaystyle n(A\cup B)}$

${\displaystyle n(A^{*}\cap B^{*})=n(A^{*})+n(B^{*})-n(A^{*}\cup B^{*}),}$

３つの式を組み合わせて使用​​する。^[11]

• 衝突解決にオープン アドレスを使用する標準のハッシュ テーブルとは異なり、固定サイズのブルーム フィルターは、任意の数の要素を持つセットを表すことができます。要素の追加は、データ構造が「いっぱいになる」ため、失敗することはありません。ただし、要素が追加されるにつれて、フィルターのすべてのビットが 1 に設定されるまで、誤検出率は着実に増加します。この時点で、すべてのクエリは肯定的な結果を生成します。オープン アドレス ハッシュでは、誤検出は発生しませんが、線形検索に近づくまでパフォーマンスは着実に低下します。
• 同じサイズとハッシュ関数のセットを持つブルーム フィルターの結合と交差は、それぞれビット単位のOR 演算と AND 演算で実装できます。ブルーム フィルターの結合演算は、結果として得られるブルーム フィルターが 2 つのセットの結合を使用して最初から作成されたブルーム フィルターと同じであるという意味でロスレスです。交差演算は、より弱い特性を満たします。結果として得られるブルーム フィルターの偽陽性確率は、構成するブルーム フィルターの 1 つの偽陽性確率以下ですが、2 つのセットの交差を使用して最初から作成されたブルーム フィルターの偽陽性確率よりも大きくなる可能性があります。
• いくつかの種類の重ね合わせコードは、物理的なエッジノッチカードで実装されたブルームフィルターとして考えることができます。一例として、1947 年にCalvin Mooersによって発明されたZatocodingがあります。これは、情報に関連付けられたカテゴリのセットがカード上のノッチで表され、カテゴリごとに 4 つのノッチがランダムにパターン化されます。

• ショウジョウバエは、匂いの新奇性を検出するためにブルームフィルターの改良版を使用するが、これには新しい匂いと以前に経験した匂いの類似性や、同じ匂いを以前に経験してから経過した時間などの追加機能が含まれる。^[12]
• コンテンツ配信プロバイダーであるAkamai Technologiesのサーバーは、ブルーム フィルターを使用して、「一発屋」がディスク キャッシュに保存されるのを防いでいます。一発屋とは、ユーザーが一度だけリクエストした Web オブジェクトで、Akamai の調査では、この現象が自社のキャッシュ インフラストラクチャの 4 分の 3 近くで発生していました。ブルーム フィルターを使用して Web オブジェクトに対する 2 回目のリクエストを検出し、そのオブジェクトを 2 回目のリクエストでのみキャッシュすると、一発屋がディスク キャッシュに入るのを防ぐことができ、ディスクの負荷が大幅に軽減され、ディスク キャッシュのヒット率が向上します。^[13]
• Google Bigtable、Apache HBase、Apache Cassandra、ScyllaDB、PostgreSQL ^{[14] は、}ブルームフィルタを使用して、存在しない行や列のディスク検索を削減します。コストのかかるディスク検索を回避すると、データベースクエリ操作のパフォーマンスが大幅に向上します。^[15]
• Google Chromeウェブブラウザは以前、悪意のあるURLを識別するためにブルームフィルタを使用していました。URLはまずローカルブルームフィルタと照合され、ブルームフィルタが肯定的な結果を返した場合にのみURLの完全なチェックが行われました（そして、肯定的な結果が返された場合はユーザーに警告しました）。^{[16] [17]}
• Microsoft Bing（検索エンジン）は、検索インデックスBitFunnelに階層型ブルームフィルタを使用しています。ブルームフィルタは、反転ファイルに基づいた以前のBingインデックスよりも低コストでした。^[18]
• Squid Web Proxy Cacheはキャッシュ ダイジェストにブルームフィルタを使用します。^[19]
• ビットコインは、ブルームフィルタの実装によるプライバシーの脆弱性が発見されるまで、ウォレットの同期を高速化するためにブルームフィルタを使用していました。^[20]
• Ventiアーカイブストレージシステムは、ブルームフィルタを使用して以前に保存されたデータを検出します。^[21]
• SPINモデルチェッカーはブルームフィルタを使用して、大規模な検証問題の到達可能な状態空間を追跡します。^[22]
• カスケード分析フレームワークはブルームフィルタを使用して、結合されたデータセットの1つがもう1つよりも大幅に大きい非対称結合（データベースの文献ではブルーム結合と呼ばれることが多い）を高速化します。^[23]
• Eximメール転送エージェント (MTA) は、レート制限機能で Bloom フィルターを使用します。^{[引用が必要]}
• Mediumは、ユーザーが以前に読んだ記事を推奨しないようにブルームフィルターを使用しています。^{[24] [ユーザー生成ソース? ]}
• Ethereum は、 Ethereum ブロックチェーン上のログをすばやく見つけるために Bloom フィルターを使用します。
• Grafana Tempoは、各バックエンドブロックにブルームフィルターを保存することでクエリのパフォーマンスを向上させるためにブルームフィルターを使用しています。これらは各クエリでアクセスされ、指定された検索条件を満たすデータを含むブロックを決定します^[25]

古典的なブルームフィルタは、挿入されたキーごとにビットのスペースを使用します。ここで、はブルームフィルタの偽陽性率です。ただし、ブルームフィルタと同じ役割を果たすデータ構造に厳密に必要なスペースは、キーごとにのみです。 ^[26]したがって、ブルームフィルタは、同等の最適なデータ構造よりも44％多くのスペースを使用します。 ${\displaystyle 1.44\log _{2}(1/\varepsilon )}$${\displaystyle \varepsilon }$${\displaystyle \log _{2}(1/\varepsilon )}$

Paghらは、ビットを使用しながら定数償却期待時間演算をサポートするデータ構造を提供している。^[27]彼らのデータ構造は主に理論的なものだが、広く使用されている商フィルタと密接に関連しており、任意のパラメータに対してビット空間を使用するようにパラメータ化でき、時間演算をサポートする。^{[28]ブルームフィルタと比較した場合の商フィルタの利点には、}参照の局所性と削除をサポートする機能 が含まれる。${\textstyle (1+o(1))n\log _{2}(1/\epsilon )+O(n)}$${\displaystyle (1+\delta )n\log \epsilon ^{-1}+3n}$${\displaystyle \delta >0}$${\displaystyle O(\delta ^{-2})}$

古典的なブルームフィルタのもう一つの代替手段は、カッコウハッシュのスペース効率の良い変種に基づくカッコウフィルタです。この場合、ハッシュテーブルが構築され、キーも値も保持されませんが、キーの短い指紋（小さなハッシュ）が保持されます。キーを検索して一致する指紋が見つかった場合、キーはおそらくセット内にあります。カッコウフィルタは削除をサポートしており、ブルームフィルタよりも参照の局所性が優れています。 ^[29]さらに、いくつかのパラメータレジームでは、カッコウフィルタをパラメータ化して、ほぼ最適なスペース保証を提供することができます。^[29]

ブルームフィルタの代替となる多くの手法、たとえば商フィルタやカッコウフィルタなどは、キーをランダムなビットの指紋にハッシュし、その指紋をコンパクトなハッシュテーブルに格納するというアイデアに基づいています。この手法は、1978 年に Carter らによって初めて導入されました^[26] 。これは、コンパクトなハッシュテーブルは、コンパクトでないハッシュテーブルよりもおよそ ビット少ないスペースで実装できるという事実に基づいています。簡潔なハッシュテーブルを使用すると、さまざまなパラメータ領域で定数時間の操作をサポートしながら、スペースの使用量をビットまで削減できます^[30]。 ${\displaystyle (\log n+\log \epsilon ^{-1})}$${\displaystyle n\log n}$${\displaystyle n\log _{2}(e/\epsilon )+o(n)}$

Putze、Sanders、Singler (2007) は、従来のブルーム フィルタよりも高速であるか、または使用するスペースが少ないブルーム フィルタのいくつかのバリエーションを研究しました。高速バリエーションの基本的な考え方は、各キーに関連付けられた k ハッシュ値を、プロセッサのメモリ キャッシュ ブロック (通常は 64 バイト) と同じサイズの 1 つまたは 2 つのブロックに配置することです。これにより、潜在的なメモリキャッシュ ミスの数が減少し、パフォーマンスが向上すると考えられます。ただし、提案されたバリエーションには、従来のブルーム フィルタよりも約 32% 多くのスペースを使用するという欠点があります。

スペース効率の高いバリアントは、各キーに対して、要求された偽陽性率の範囲の値を生成する単一のハッシュ関数を使用することに依存しています。値のシーケンスは、ビットに近いスペースを占めるように、ゴロム符号化 (またはその他の圧縮手法) を使用してソートおよび圧縮されます。特定のキーについてブルーム フィルタをクエリするには、対応する値がブルーム フィルタに格納されているかどうかを確認するだけで十分です。各クエリでブルーム フィルタ全体を解凍すると、このバリアントはまったく使用できなくなります。この問題を克服するために、値のシーケンスは同じサイズの小さなブロックに分割され、個別に圧縮されます。クエリ時には、平均してブロックの半分だけを解凍する必要があります。解凍のオーバーヘッドのため、このバリアントは従来のブルーム フィルタよりも遅くなる可能性がありますが、単一のハッシュ関数を計算する必要があることでこれを補うことができます。 ${\displaystyle \left[0,n/\varepsilon \right]}$${\displaystyle \varepsilon }$${\displaystyle n\log _{2}(1/\varepsilon )}$

Graf & Lemire (2020) は、XOR フィルターと呼ばれるアプローチについて説明しています。このアプローチでは、特定の種類の完全ハッシュテーブルにフィンガープリントを保存し、ブルーム フィルターやカッコウ フィルターよりもメモリ効率が高く (キーあたりのビット数)、高速なフィルターを生成します。(時間の節約は、ルックアップに 3 回のメモリ アクセスが必要であり、これらをすべて並列に実行できるという事実によって実現されます。) ただし、フィルターの作成はブルーム フィルターやカッコウ フィルターよりも複雑であり、作成後にセットを変更することはできません。 ${\displaystyle 1.23\log _{2}(1/\varepsilon )}$

ブルームフィルタには60種類以上の変種があり、この分野の調査も数多く行われ、アプリケーションも絶えず変化しています（例えば、Luoら ^[31]を参照）。変種の中には、元の提案とは大きく異なるものもあり、元のデータ構造とその哲学から逸脱したり、分岐したりしています。 ^{[31]ブルームフィルタを、}ランダム射影、圧縮センシング、局所性に敏感なハッシュに関する他の研究と統合する処理はまだ行われていません（ただし、神経科学に触発された1つの試みについては 、Dasguptaら^{[32]を参照）。}

コンテンツ配信ネットワークは、 Web コンテンツをキャッシュしてユーザーに提供し、パフォーマンスと信頼性を向上させるために、世界中にWeb キャッシュを展開しています。ブルーム フィルタの主な用途は、これらの Web キャッシュに保存する Web オブジェクトを効率的に決定することです。一般的な Web キャッシュからアクセスされる URL のほぼ 4 分の 3 は、ユーザーが 1 回だけアクセスして二度とアクセスしない「ワンヒット ワンダー」です。ワンヒット ワンダーは二度とアクセスされないため、Web キャッシュに保存するのは明らかにディスク リソースの無駄です。ワンヒット ワンダーのキャッシュを防ぐために、ユーザーがアクセスするすべての URL を追跡するブルーム フィルタが使用されます。Web オブジェクトは、少なくとも 1 回アクセスされた場合にのみキャッシュされます。つまり、オブジェクトは 2 回目の要求でキャッシュされます。このようにブルーム フィルタを使用すると、ほとんどのワンヒット ワンダーはディスク キャッシュに書き込まれないため、ディスク書き込みの作業負荷が大幅に軽減されます。さらに、一発屋を除外することでディスク上のキャッシュスペースも節約でき、キャッシュヒット率も向上します。^[13]

Kissら ^[33]は、偽陽性に加えて、典型的な偽陰性が存在しないという点も回避するブルームフィルタの新しい構成について説明した。この構成は、集合要素が取り出される有限の宇宙に適用され、Eppstein、Goodrich、Hirschbergによる既存の非適応型組み合わせ群テスト方式に依存している。典型的なブルームフィルタとは異なり、要素は決定論的かつ高速で計算が簡単な関数によってビット配列にハッシュされる。偽陽性が完全に回避される最大の集合サイズは、宇宙サイズの関数であり、割り当てられたメモリの量によって制御される。

あるいは、標準的な方法で最初のブルーム フィルタを構築し、有限かつ扱いやすい列挙可能なドメインを使用して、すべての誤検知を網羅的に検出し、そのリストから 2 番目のブルーム フィルタを構築することもできます。2 番目のフィルタの誤検知は、3 番目のフィルタを構築することで同様に処理されます。宇宙は有限であり、誤検知の集合は各ステップで厳密に縮小するため、この手順により、ブルーム フィルタの有限カスケードが生成され、(この閉じた有限のドメインでは) 真陽性と真陰性のみが生成されます。フィルタ カスケードのメンバーシップを確認するには、最初のフィルタを照会し、結果が陽性の場合は 2 番目のフィルタを参照します。この構成は、 Web PKI 用に提案されている証明書失効ステータス配布メカニズムであるCRLiteで使用されており、証明書の透明性を利用して、既存の証明書のセットを閉じます。^[34]

カウンティング フィルターは、フィルターを新たに再作成することなく、ブルーム フィルターで削除操作を実装する方法を提供します。カウンティング フィルターでは、配列の位置 (バケット) が 1 ビットからマルチビット カウンターに拡張されます。実際、通常のブルーム フィルターは、バケット サイズが 1 ビットのカウンティング フィルターと見なすことができます。カウンティング フィルターは Fan ら (2000) によって導入されました。

挿入操作はバケットの値を増分するように拡張され、検索操作は必要な各バケットがゼロ以外であることを確認します。削除操作は、それぞれのバケットの値を減分する操作で構成されます。

バケットの算術オーバーフローは問題であり、この問題が発生する可能性がほとんどないようにバケットは十分に大きくなければなりません。この問題が発生した場合、ブルーム フィルターの特性を維持するために、増分および減分操作によってバケットを可能な限り最大値に設定しておく必要があります。

カウンターのサイズは通常 3 または 4 ビットです。そのため、カウント型ブルーム フィルターは静的ブルーム フィルターよりも 3 ～ 4 倍多くのスペースを使用します。対照的に、Pagh、Pagh & Rao (2005) および Fan ら (2014) のデータ構造でも削除が可能ですが、静的ブルーム フィルターよりもスペースは少なくて済みます。

カウンティング フィルターのもう 1 つの問題は、スケーラビリティが限られていることです。カウンティング ブルーム フィルター テーブルは拡張できないため、フィルターに同時に保存できるキーの最大数を事前に把握しておく必要があります。テーブルの設計容量を超えると、挿入されるキーが増えるにつれて誤検出率が急激に増加します。

Bonomi ら (2006) は、機能的には同等ですが、ブルーム フィルターをカウントする場合の約半分のスペースしか使用しない、d-left ハッシュに基づくデータ構造を導入しました。このデータ構造ではスケーラビリティの問題は発生しません。設計された容量を超えると、キーは 2 倍のサイズの新しいハッシュ テーブルに再挿入できます。

Putze、Sanders、Singler (2007) によるスペース効率の高いバリアントは、挿入と削除をサポートすることでカウント フィルターを実装するためにも使用できます。

Rottenstreich、Kanizo、Keslassy (2012) は、変数の増分に基づく新しい一般的な方法を導入しました。この方法は、削除をサポートしながら、ブルーム フィルターとそのバリアントのカウントの誤検出確率を大幅に改善します。ブルーム フィルターのカウントとは異なり、各要素の挿入時に、ハッシュ カウンターは単位増分ではなくハッシュ変数の増分で増分されます。要素を照会するには、カウンターの正確な値を考慮し、正の値だけを考慮しません。カウンター値で表される合計が、照会された要素の対応する変数の増分で構成できない場合、クエリに対して否定的な回答を返すことができます。

Kimら(2019)は、カウンティングブルームフィルタの偽陽性がk=1から定義された点まで減少し、から正の無限大まで増加し、カウント閾値の関数として見つかることを示しています。^[35]${\displaystyle k_{opt}}$${\displaystyle k_{opt}}$${\displaystyle k_{opt}}$

ブルームフィルタは、分散データ構造で編成され、集約関数の完全な分散計算を実行することができます。分散集約により、この目的のために集中型の計算エンティティを介さずに、分散ネットワークのすべてのノードで集合的な測定値をローカルに利用できるようになります。^[36]

並列ブルームフィルタは、並列シェアードナッシングマシンに存在する複数の処理要素（PE）を利用するために実装できます。並列ブルームフィルタの主な障害の1つは、一般に開始時またはバッチ挿入時にすべてのPEに均等に分散される順序付けられていないデータの編成と通信です。データを順序付けるには、2つのアプローチを使用できます。1つは、各PEに格納されているすべてのデータに対するブルームフィルタ（複製ブルームフィルタと呼ばれる）で、もう1つは、すべてのデータを均等に分割し、各PEがその一部を格納しているブルームフィルタです。^[37]どちらのアプローチでも、「シングルショット」ブルームフィルタが使用され、1つのハッシュのみを計算し、要素ごとに1ビットを反転して、通信量を削減します。

分散ブルーム フィルタは、最初にローカル PE 上のすべての要素をハッシュし、次にハッシュによってローカルにソートすることによって開始されます。これは、バケット ソートなどを使用して線形時間で実行でき、ローカルでの重複検出も可能になります。ソートは、割り当てられた PE を区切り文字としてハッシュをグループ化し、各グループのブルーム フィルタを作成するために使用されます。これらのブルーム フィルタをGolomb コーディングなどを使用してエンコードした後、各ブルーム フィルタは、挿入されたハッシュ値を担当する PE にパケットとして送信されます。PE p は、値と の間のすべてのハッシュを担当します。ここで、s は、すべてのデータに対するブルーム フィルタの合計サイズです。各要素は 1 回だけハッシュされ、したがって 1 つのビットだけが設定されるので、要素がブルーム フィルタに挿入されたかどうかを確認するには、要素のハッシュ値を担当する PE のみを操作する必要があります。ブルーム フィルタを複製するとすべての PE がブルーム フィルタを更新する必要があるのに対し、単一の挿入操作は 1 つの PE のブルーム フィルタのみを変更すればよいため、効率的に実行できます。グローバルブルームフィルタを各PEに個別に保存するのではなく、すべてのPEに分散することで、ブルームフィルタのサイズを大幅に大きくすることができ、容量が大きく、誤検出率が低くなります。分散ブルームフィルタは、最も「ユニークな」要素をフィルタリングすることで、重複検出アルゴリズム^[38] を改善するために使用できます。これらは、要素のハッシュのみを通信し、要素自体の容量がはるかに大きいため、要素をセットから削除することで計算でき、その後に使用される重複検出アルゴリズムの作業負荷が軽減されます。 ${\displaystyle p*(s/|{\text{PE}}|)}$${\displaystyle (p+1)*(s/|{\text{PE}}|)}$

ハッシュの通信中、PE は複数の受信パケットで設定されているビットを検索します。これは、2 つの要素が同じハッシュを持ち、したがって重複している可能性があることを意味するためです。これが発生した場合、ビットのインデックス (重複している可能性がある要素のハッシュでもある) を含むメッセージが、設定されたビットを含むパケットを送信した PE に送信されます。1 人の送信者によって同じ PE に複数のインデックスが送信された場合は、インデックスもエンコードすると有利です。ハッシュが送り返されなかったすべての要素は重複していないことが保証され、それ以上評価されません。残りの要素には、再パーティション化アルゴリズム^[39]を使用できます。最初に、ハッシュ値が送り返されたすべての要素が、そのハッシュが担当する PE に送信されます。すべての要素とその重複は、同じ PE 上にあることが保証されます。2 番目のステップでは、各 PE は、開始要素の数のほんの一部である受信要素に対して、重複検出のためのシーケンシャル アルゴリズムを使用します。重複の誤検出率を許可することで、PE は重複ハッシュを持つ要素をまったく送信する必要がなくなり、代わりに重複ハッシュを持つ要素を重複としてマークするだけで済むため、通信量をさらに削減できます。その結果、重複検出の誤検出率は、使用されるブルーム フィルターの誤検出率と同じになります。

最も「ユニークな」要素をフィルタリングするプロセスは、各フィルタリング ステップでハッシュ関数を変更することで、複数回繰り返すこともできます。フィルタリング ステップを 1 回だけ使用すると、誤検出率が低く抑えられますが、フィルタリング ステップを 1 回繰り返すと、最初のステップでは誤検出率が高くなり、2 番目のステップでは誤検出率が高くなりますが、前のフィルタリング ステップですでに多くの要素が削除されているため、処理する要素が少なくなります。セット内の重複数が少ない場合は、繰り返しを 2 回以上使用すると通信量をさらに減らすことができますが、追加の複雑さに対する見返りは小さくなります。

複製ブルームフィルタは、例えば^{[40] の}ようなよく知られたゴシップ用のハイパーキューブアルゴリズムを使用してデータを整理します。まず、各PEはすべてのローカル要素に対してブルームフィルタを計算し、それを保存します。各ステップ i で PE が次元 i に対してローカルブルームフィルタを送信し、その次元に対して受信したブルームフィルタをローカルブルームフィルタとマージするループを繰り返すことで、各ブルームフィルタに含まれる要素を反復ごとに 2 倍にすることができます。すべての次元に対してブルームフィルタを送受信した後、各 PE にはすべての要素に対するグローバルブルームフィルタが含まれます。 ${\displaystyle \log |{\text{PE}}|}$

クエリの数がブルーム フィルターに含まれる要素の数よりはるかに多い場合、複製ブルーム フィルターはより効率的です。分散ブルーム フィルターと比較した損益分岐点は、ブルーム フィルターの誤検出率として 、アクセス後約 です。${\displaystyle |{\text{PE}}|*|{\text{Elements}}|/\log _{f^{\text{+}}}|{\text{PE}}|}$${\displaystyle f^{\text{+}}}$

ブルーム フィルタは、Byers ら (2004) のように、近似データ同期に使用できます。ブルーム フィルタのカウントは、2 つのセット間の差異の数を近似するために使用でき、このアプローチは Agarwal と Trachtenberg (2006) で説明されています。

ブルームフィルタは、ストリーミングデータのコンテキストに適応できます。たとえば、Deng & Rafiei (2006) は、安定ブルームフィルタを提案しました。これは、新しい要素の挿入によって関連するカウンタが値cに設定され、その後、固定量のカウンタsのみが 1 減少するカウントブルームフィルタで構成されます。したがって、メモリには最近の要素に関する情報がほとんど含まれます (直感的には、 N 個のカウンタの SBF 内の要素の寿命は約 であると想定できます)。もう 1 つのソリューションは、エイジングブルームフィルタです。これは、使用可能なメモリの半分をそれぞれが占める 2 つのブルームフィルタで構成されます。1 つのフィルタがいっぱいになると、2 番目のフィルタが消去され、新しい要素がこの新しく空になったフィルタに追加されます。^[41]${\displaystyle c{\tfrac {s}{N}}}$

しかし、^[42]によれば、フィルタに関係なく、n 回の挿入後、偽陽性と偽陰性の確率の合計は 以下に制限されることが示されています。ここで、 Lはすべての可能な要素の数 (アルファベットのサイズ)、m はメモリ サイズ (ビット単位) で、 と仮定します。この結果は、L が十分に大きく、n が無限大になると、下限が に収束することを示しています。これは、ランダム フィルタの特性関係です。したがって、十分な挿入後、アルファベットがメモリに格納するには大きすぎる場合 (確率フィルタのコンテキストでは想定されます)、フィルタがランダム性よりも優れたパフォーマンスを発揮することは不可能です。この結果は、フィルタがストリーム全体ではなくスライディング ウィンドウに対してのみ動作することを想定することで活用できます。この場合、上記の式の指数n はwに置き換えられ、 wが小さすぎない 場合、1 から逸脱する可能性のある式になります。${\displaystyle FP}$${\displaystyle FN}$$${\displaystyle FP+FN\geq 1-{\frac {1-\left(1-{\frac {1}{L}}\right)^{m}}{1-\left(1-{\frac {1}{L}}\right)^{n}}}}$$${\displaystyle n>m}$${\displaystyle FP+FN=1}$

Chazelle ら (2004) は、挿入された各要素に値を関連付け、連想配列を実装できるブルーム フィルタの一般化を設計しました。ブルーム フィルタと同様に、これらの構造は、誤検知の可能性を低く抑えることで、スペースのオーバーヘッドを小さく抑えます。「Bloomier フィルタ」の場合、誤検知は、キーがマップ内に存在しない場合に結果を返すことと定義されます。マップは、マップ内にあるキーに対して間違った値を返すことはありません。

Boldi と Vigna (2005) は、ブルーム フィルタの格子ベースの一般化を提案しました。コンパクトな近似器は、各キーに格子の要素を関連付けます (標準のブルーム フィルタは、ブール 2 要素格子の場合です)。ビット配列の代わりに、格子要素の配列があります。キーと格子の要素の間に新しい関連付けを追加すると、格子要素を持つキーに関連付けられたk個の配列位置の現在の内容の最大値が計算されます。キーに関連付けられた値を読み取ると、キーに関連付けられたk個の位置にある値の最小値が計算されます。結果の値は、元の値から近似されます。

この実装では、ハッシュ関数ごとに別々の配列を使用しました。この方法により、挿入と照会の両方で並列ハッシュ計算が可能になります。^[43]

Almeida ら (2007) は、保存されている要素の数に動的に適応しながら、偽陽性確率を最小限に抑えることができるブルーム フィルタのバリエーションを提案しました。この手法は、容量が増加し、偽陽性確率が厳しくなる標準ブルーム フィルタのシーケンスに基づいており、挿入される要素の数に関係なく、事前に最大の偽陽性確率を設定できるようにします。

空間ブルームフィルタ（SBF）は、もともとPalmieri、Calderoni、Maio（2014）によって、位置情報、特に位置情報プライバシーのための暗号化プロトコルのコンテキストを格納するために設計されたデータ構造として提案されました。しかし、SBFの主な特徴は、単一のデータ構造に複数のセットを格納できることであり、これにより、SBFはさまざまなアプリケーションシナリオに適しています。 ^[44]特定のセットへの要素のメンバーシップを照会することができ、偽陽性の確率はセットによって異なります。構築中にフィルタに入力される最初のセットは、最後に入力されたセットよりも偽陽性の確率が高くなります。^[45]この特性により、セットの優先順位付けが可能になり、より「重要な」要素を含むセットを保持できます。

階層型ブルームフィルタは、複数のブルームフィルタ層で構成されています。階層型ブルームフィルタでは、アイテムがいくつの層に含まれているかをチェックすることで、アイテムがブルームフィルタに何回追加されたかを追跡できます。階層型ブルームフィルタでは、チェック操作では通常、アイテムが見つかった最も深い層の番号が返されます。^[46]

深さ D の減衰ブルーム フィルタは、D 個の通常のブルーム フィルタの配列として見ることができます。ネットワークでのサービス検出のコンテキストでは、各ノードは通常のブルーム フィルタと減衰ブルーム フィルタをローカルに格納します。通常またはローカルのブルーム フィルタは、ノード自体が提供するサービスを示します。レベル i の減衰フィルタは、現在のノードから i ホップ離れたノードで見つかるサービスを示します。i 番目の値は、ノードから i ホップ離れたノードのローカル ブルーム フィルタの和集合を取ることによって構築されます。^[47]

たとえば、下のグラフに示すような小さなネットワークを考えてみましょう。ID がビット 0、1、3 にハッシュされるサービス A (パターン 11010) を探しているとします。n1 ノードを出発点とします。まず、ローカル フィルターをチェックして、n1 がサービス A を提供しているかどうかを確認します。パターンが一致しないため、減衰ブルーム フィルターをチェックして、どのノードが次のホップになるかを決定します。n2 はサービス A を提供していませんが、サービスを提供するノードへのパス上にあることがわかります。したがって、n2 に移動して同じ手順を繰り返します。すぐに n3 がサービスを提供していることがわかり、宛先が見つかります。^[48]

複数の層からなる減衰ブルームフィルタを使用することで、より遠くのソースによって設定されたビットを減衰（シフトアウト）することでブルームフィルタの飽和を回避しながら、1ホップ以上の距離にあるサービスを発見することができます。^[47]

ブルーム フィルターは、大規模な化学構造データベースの検索によく使用されます (化学的類似性を参照)。最も単純なケースでは、フィルターに追加される要素 (この分野ではフィンガープリントと呼ばれます) は、分子に存在する原子番号、または各原子の原子番号と結合の数および種類に基づくハッシュだけです。このケースは単純すぎて役に立ちません。より高度なフィルターでは、原子数、カルボキシル基などのより大きなサブ構造の特徴、リングの数などのグラフ プロパティもエンコードされます。ハッシュ ベースのフィンガープリントでは、原子と結合のプロパティに基づくハッシュ関数を使用してサブグラフをPRNGシードに変換し、最初の出力値を使用してブルーム フィルターのビットを設定します。

分子指紋は、パンチカードで検索された化学構造を検索する方法として、1940 年代後半に始まりました。しかし、Daylight Chemical Information Systems, Inc. が、事前計算されたテーブルを使用するのではなく、ハッシュベースのビット生成方法を導入したのは、1990 年頃になってからでした。辞書アプローチとは異なり、ハッシュ方法は、以前には見られなかったサブ構造にビットを割り当てることができます。1990 年代初頭には、「指紋」という用語は「構造キー」とは異なると考えられていましたが、その後、構造キー、スパース カウント指紋、3D 指紋など、類似性の比較に使用できるほとんどの分子特性を包含するようになりました。ブルーム フィルターとは異なり、Daylight ハッシュ方法を使用すると、機能ごとに割り当てられるビット数を機能サイズの関数にすることができますが、Daylight のような指紋の実装のほとんどは、機能ごとに固定されたビット数を使用するため、ブルーム フィルターになります。オリジナルの Daylight 指紋は、類似性とスクリーニングの両方の目的で使用できます。一般的な ECFP2 などの他の多くの指紋タイプは、類似性には使用できますが、スクリーニングには使用できません。これは、スクリーニングとして使用すると偽陰性をもたらすローカル環境特性が含まれているためです。これらは同じメカニズムで構築されていますが、フィルタリングに使用できないため、ブルーム フィルターではありません。

• カウント・ミニマムスケッチ – コンピュータサイエンスにおける確率的データ構造
• 特徴ハッシュ – ハッシュ関数を使用して特徴をベクトル化する
• MinHash  – データマイニング技術
• 商フィルター
• スキップリスト – 確率的データ構造
• バイオインフォマティクスにおけるブルームフィルタ
• カッコウフィルタ – 近似集合メンバーシップのデータ構造

• 「ブルーム フィルタの使用」Perlを使用したブルーム フィルタの詳細な説明
• ブルーム フィルターがなぜそのように機能するのか (マイケル ニールセン、2012)
• ブルーム フィルタ - チュートリアル、分析、調査 (Blustein & El-Maazawi、2002)、ダルハウジー大学
• ウィスコンシン大学マディソン校のウェブサイトに掲載されている、さまざまな設定での誤検出率の表
• 「より最適なブルーム フィルタ」、Ely Porat (2007 年 11 月) YouTubeの Google TechTalk ビデオ