ブロック型ブルームフィルタ（Blocked Bloom Filter）の仕組みと実装方法を解説

ブロック型ブルームフィルタ（Blocked Bloom Filter）は、標準的なブルームフィルタのキャッシュ効率を高めるために考案されたデータ構造です。まず、基本的な特徴を整理してみましょう。

• まずメモリブロックを選択し、その後、各ブロック内でローカルなブルームフィルタを選択します。
• この方式では、メモリブロック間に不均衡（偏り）が生じる可能性があります。
• 処理は高速・効率的である一方、偽陽性率（FPR：False Positive Rate）が悪化しやすいという課題があります。
• 理想としては、同サイズの標準的なブルームフィルタと同等のFPRを実現することが求められます。
• ブロック型ブルームフィルタは、それぞれが1つのキャッシュラインに収まる大きさの、標準的なブルームフィルタよりも小規模な複数のブロックbから構成されます。
• なお、各ビットを異なるブロックへ振り分ける「パーティション方式」とは、ブロック型ブルームフィルタの仕組みは区別されます。

ブロック型ブルームフィルタは、主に以下のような方法で実装できます。

ビットパターン（Bit Patterns）

ここでは、事前計算されたビットパターンを用いてブロック型ブルームフィルタを実装する手法について解説します。k個のハッシュ関数を評価してkビットをセットする代わりに、たった1つのハッシュ関数によって、幅Bのランダムなkビットパターンを格納したテーブルから、事前計算済みのパターンを選び出します。多くの場合、このテーブルはキャッシュに収まるサイズです。

この手法では、必要なハッシュ値が1つ（ビット数としても小さな値）で済むため、少ないSIMD（Single Instruction Multiple Data）命令で操作を実装できます。さらに、ブルームフィルタを転送する際にテーブルをデータへ明示的に含める必要はなく、シード値をもとに再構築することも可能です。

一方、ビットパターン方式の主な欠点は、2つの要素が同一のパターンへハッシュされるとテーブル衝突（コリジョン）が発生する点です。この衝突が原因で、FPRが上昇してしまいます。

パターンの多重化（Multiplexing Patterns）

このアイデアをさらに発展させると、平均k/x個のセットビットを持つx個のパターンをビット単位のOR演算で組み合わせることで、1つのテーブルからより多くのバリエーションパターンを生成できます。

マルチブロッキング（Multi-Blocking）

FPRを改善するもう一つの手法として、「マルチブロッキング」と呼ばれる方式があります。この方式では、クエリ操作がX個のブルームフィルタブロックへアクセスすることを許可し、各ブロックに対しそれぞれk/Xビットずつの設定またはテストを行います（kがXで割り切れない場合は、先頭のk mod X個のブロックに余分なビットを1つ設定します）。

マルチブロッキングは、単純にブロックサイズをXB（Bは各ブロックのサイズ）に拡大する場合よりも優れた性能を発揮します。これは、この方法によってより大きな多様性がもたらされるためです。セットビットを複数のブロックに分散させても、ブロックあたりの「1」ビットの期待値は変わりません。ただし、要素へアクセスする際には、関与する各ブロック内でk/Xビットのみが評価対象となる点に注意が必要です。