確率的データ構造ブルームフィルタについて

Scalable Packet Classification on FPGA - IEEE Journals & Magazine

論文を読んでいて初見のデータ構造があったので記事にしておく、wikiのほうが確かだし詳しいので自分用のまとめです。

内容はルーターのようなネットワーク機器に実装されるパケットクラシファイア[1]のFPGA実装に関するもので、パケットの分類方法としてブルームフィルタというデータ構造が利用されていた。

ブルームフィルタ[2]

ブルームフィルタは確率的データ構造と呼ばれるもので偽陽性(false positive)による誤検出の可能性があるが偽陰性(false negative)はそうでなはいという特徴を持つ。空間的/時間的に他のデータ構造と比較して優位性があり、省メモリで高速に集合に要素が含まれるかを判定できる。

例えばm=18のビット列とk=3個のハッシュ関数(hash_k1,k2,k3)を仮定し、集合{x,y,z}と要素{w}について以下が成り立つとすると

hash_k1(x)->1
hash_k2(x)->5
hash_k3(x)->13

hash_k1(y)->4
hash_k2(y)->11
hash_k3(y)->16

hash_k1(z)->3
hash_k2(z)->5
hash_k3(z)->11

hash_k1(w)->4
hash_k2(w)->13
hash_k3(w)->15

初期状態のブルームフィルタは18ビット全てが0であり

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

集合{x,y,z}それぞれにハッシュ関数を適用して該当のインデックスのビットを立てることを考えると対応は以下のようになる。

-	1	3	4	5	11	13	16
x	1	0	0	1	0	1	0
y	0	0	1	0	1	0	1
z	0	1	0	1	1	0	0

上記操作を行った最終的なビット列は以下のようになる。

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
0	1	0	1	1	1	0	0	0	0	0	1	0	1	0	0	1	0

要素{w}が集合に含まれるかは生成したビット列の対応するビットが立っているかを見れば良く13ビット目が0となっていることから要素{w}は集合に含まれていないことがわかる。

-	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
-	0	1	0	1	1	1	0	0	0	0	0	1	0	1	0	0	1	0
w	0	0	0	0	1	0	0	0	0	0	0	0	0	1	0	1	0	0

偽陽性・偽陰性

上記のようにブルームフィルタはk個のハッシュ関数によりビット列のインデックスを得て対応するビットを立てるという処理を繰り返す。省メモリで高速に集合の判定を行えるというメリットはあるものの、ハッシュ関数の衝突により集合からビット列を生成する際に同じインデックスのビットを立てることや、判定時に衝突により誤判定をする可能性がある。

実際には集合に存在しないが存在すると判定する偽陽性(false positive)による誤判定の可能性がある一方で、集合に存在するときに存在しないと判定する偽陰性(false negative)の可能性はないという特徴を持つ。