ブロックされたブルームフィルター

• 最初にメモリブロックを選択します。
• 次に、各ブロック内のローカルブルームフィルターを選択します。
• メモリブロック間の不均衡を引き起こす可能性があります
• このフィルターは効率的ですが、偽陽性率（FPR）が低くなります。
• 最初に、ブロックされたブルームフィルターは、同じサイズの標準のブルームフィルターと同じFPR（偽陽性率）を持つ必要があります。
• ブロックブルームフィルターは、標準のブルームフィルター（ブルームフィルターブロック）よりも比較的少ないブロックbのシーケンスで構成され、各ブロックは1つのキャッシュラインに収まります。
• ブロックブルームフィルタースキームは、各ビットが異なるブロックに挿入されるパーティションスキームとは異なります。

ブロックブルームフィルターは、次の方法で実装されます-

ビットパターン（パット）

このトピックでは、事前計算されたビットパターンを実装するブロックブルームフィルターの実装について説明します。 k個のハッシュ関数の評価によってkビットを設定する代わりに、単一のハッシュ関数が幅Bのランダムなkビットパターンのテーブルから事前計算されたパターンを選択します。多くの場合、このテーブルはキャッシュに収まります。このソリューションでは、（ビットに関して）1つの小さなハッシュ値のみが必要であり、操作は少数のSIMD（単一命令複数データ）命令を使用して実装できます。ブルームフィルターを転送するときに、テーブルをデータに明示的に含める必要はありませんが、シード値を実装して再構築できます。

ビットパターン方式の主な欠点は、2つの要素が同じパターンにハッシュされると、テーブルの衝突が発生する可能性があることです。これによりFPRが増加します。

多重化パターン

このアイデアをもう一度洗練するために、ビット単位で、または平均k / xセットビット数のxパターンを実行することにより、単一のテーブルからより多様なパターンを実現できます。

マルチブロッキング

FPRの改善に役立つもう1つのバリアントは、マルチブロッキングと呼ばれます。クエリ操作でXブルームフィルターブロックにアクセスし、各ブロックでそれぞれk/Xビットを設定またはテストすることを許可します。 （kがXで割り切れない場合は、最初のk mod Xブロックに追加のビットを設定します。）マルチブロッキングは、ブロックサイズをXB（B-各ブロックサイズ）に増やすよりもパフォーマンスが優れています。仕方。セットビットをいくつかのブロックに分割すると、ブロックあたりの1ビットの期待数は同じままです。ただし、要素にアクセスするときは、参加している各ブロックでk/Xビットのみが考慮されます。