ブルームフィルター

ハッシュ関数の数kは正の整数でなければなりません。この制約を無視すると、与えられたmとnに対して、偽陽性確率を最小にするkの値は次のようになります。

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

挿入する要素の数nと望ましい偽陽性確率εが与えられた場合、必要なビット数m は、上記の確率式に最適な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 ]}

式${\displaystyle m=-{\frac {n\ln \varepsilon }{(\ln 2)^{2}}}}$3 つの理由から近似値である。まず、最も重要ではないが、近似値である。 ${\displaystyle 1-{\frac {1}{m}}}$として${\displaystyle e^{-{\frac {1}{m}}}}$これは良い漸近近似です（つまり、m → ∞ のときに成り立ちます）。次に、より懸念されるのは、メンバーシップ テスト中に、テストされたビットの 1 つが 1 に設定されるという事象が、他のテストされたビットが 1 に設定されるという事象とは独立であると仮定していることです。3 番目に、最も懸念されるのは、${\displaystyle k={\frac {m}{n}}\ln 2}$偶然にも不可欠な要素である。

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

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

この境界は、近似式が${\displaystyle \left(1-e^{-{\frac {kn}{m}}}\right)^{k}}$最大で要素が半分増え、ビットが1つ減るというペナルティで適用できます。

ブルームフィルタは、アイテムの集合をコンパクトに表現する方法です。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],}$

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

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

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

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

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

あるいは、標準的な方法で最初のブルームフィルタを構築し、有限かつ扱いやすい列挙可能なドメインで、すべての偽陽性を網羅的に見つけ出し、そのリストから 2 番目のブルームフィルタを構築することもできます。2 番目のフィルタの偽陽性は、同様に 3 番目のフィルタを構築することで処理され、以下同様です。宇宙は有限であり、偽陽性のセットは各ステップで厳密に縮小するため、この手順は、（この閉じた有限ドメインでは）真陽性と真陰性のみを生成する有限のブルームフィルタのカスケードをもたらします。フィルタカスケードへの所属を確認するには、最初のフィルタに問い合わせ、結果が陽性であれば、次に 2 番目のフィルタを参照し、以下同様です。この構成は、 Web PKIの証明書失効ステータス配信メカニズムとして提案されているCRLiteで使用されており、証明書の透明性を利用して既存の証明書のセットを閉じます。^{[ 37 ]}

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

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

バケットの算術オーバーフローは問題であり、このような事態がまれになるよう、バケットは十分に大きくする必要があります。万が一オーバーフローが発生した場合は、ブルームフィルタの特性を維持するために、インクリメントおよびデクリメント操作によってバケットが最大値に設定されるようにする必要があります。

カウンタのサイズは通常3ビットまたは4ビットです。そのため、カウントブルームフィルタは静的ブルームフィルタよりも3～4倍のスペースを必要とします。一方、Pagh、Pagh & Rao (2005)およびFan et al. (2014)のデータ構造は削除も可能ですが、静的ブルームフィルタよりも少ないスペースしか使用しません。

カウンティングフィルタのもう一つの問題点は、拡張性の制限です。カウンティングブルームフィルタテーブルは拡張できないため、フィルタに同時に格納できるキーの最大数を事前に把握しておく必要があります。テーブルの設計容量を超えると、キーが挿入されるにつれて誤検出率が急速に上昇します。

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

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

Rottenstreich、Kanizo 、 Keslassy (2012)は、変数インクリメントに基づく新しい汎用的な手法を導入しました。この手法は、削除をサポートしながら、ブルームフィルタとその変種のカウントにおける偽陽性確率を大幅に改善します。ブルームフィルタのカウントとは異なり、要素が挿入されるたびに、ハッシュカウンタは単位インクリメントではなく、ハッシュ変数インクリメントによってインクリメントされます。要素を照会するには、カウンタの正値だけでなく、その正確な値が考慮されます。カウンタ値で表される合計が、照会された要素に対応する変数インクリメントで構成されない場合、クエリに対して否定的な回答が返されます。

Kimら（2019）は、Counting Bloomフィルタの偽陽性がk=1から定義された点まで減少することを示している。${\displaystyle k_{opt}}$、そして増加します${\displaystyle k_{opt}}$正の無限大に、そして${\displaystyle k_{opt}}$カウント閾値の関数として。^{[ 38 ]}

ブルームフィルタは、分散データ構造に構成することで、集約関数の完全分散計算を実行できます。分散集約により、中央集権的な計算エンティティを介することなく、分散ネットワークの各ノードで集合的な測定値をローカルで利用できるようになります。^{[ 39 ]}

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

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

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

最も「固有」な要素を除外する処理は、各フィルタリングステップでハッシュ関数を変更することで複数回繰り返すことができます。フィルタリングステップを1回だけ使用する場合は、偽陽性率を低く抑える必要がありますが、フィルタリングステップを1回繰り返す場合は、最初のステップで偽陽性率が高くなっても構いません。2回目のステップでは偽陽性率は高くなりますが、前のステップで既に多くの要素が除外されているため、処理対象となる要素は少なくなります。セット内の重複要素の数が少ない場合は、2回以上の繰り返しによって通信量をさらに削減できますが、複雑さが増す割に得られるメリットは小さいです。

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

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

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

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

しかし、フィルタの種類に関わらず、n 回挿入した後^、偽^陽性の合計^は${\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}}}}$$ここで、Lは可能なすべての要素の数（アルファベットのサイズ）、mはメモリサイズ（ビット単位）であり、${\displaystyle n>m}$この結果は、Lが十分に大きくnが無限大に近づく場合、下限が収束することを示している。${\displaystyle FP+FN=1}$これはランダムフィルタの特性関係です。したがって、十分な挿入が行われ、アルファベットがメモリに格納するには大きすぎる場合（確率フィルタの文脈では想定されます）、フィルタがランダム性よりも優れた性能を発揮することは不可能です。この結果は、フィルタがストリーム全体ではなくスライディングウィンドウでのみ動作することを想定することで活用できます。この場合、上記の式の指数nはwに置き換えられ、 w が小さすぎなければ、1 からずれる可能性のある式が得られます。

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

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

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

Almeidaら（2007）は、最小の偽陽性確率を保証しながら、格納される要素数に動的に適応できるブルームフィルタの変種を提案した。この手法は、容量が増加し、偽陽性確率が厳しくなる標準的なブルームフィルタのシーケンスに基づいており、挿入される要素数に関係なく、偽陽性確率の最大値が事前に設定できることを保証する。

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

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

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

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

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

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

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