偽陽性を許容して空間効率良くキーの存在を確認するBloom filterとCuckoo filter

algorithm

例えばデータストアへのアクセス抑制のためにキーの存在を確認する際、 全てのキーを保持して探索すれば100%正しく判定できるが、キーが長く数が膨大になるとメモリの使用量が問題になることがある。 もし偽陽性が許容できるなら、次のフィルタを使うことで空間効率良くキーの存在を確認できる。

Bloom filter

1970年に考案されたフィルタで、 LevelDBやCassandraで使われている。

GoogleのkvsライブラリLevelDBを使う - sambaiz-net

Bloom filter

初期値0のビット配列と、そのいずれかのビットにデータをマッピングするk個のハッシュ関数を定義し、 含めるデータを各ハッシュ関数に通して、マッピングされたビットを1に更新していく。 これにより、いずれかのハッシュ関数によって0のビットにマッピングされるデータは、必ずフィルタに含まれないことが分かる。

データの追加と存在の確認を、いずれも要素数に依存しないO(k)で行うことができるが、削除はできない。 0/1ではなくインクリメントしていくCounting filterという実装にすると空間効率は劣るが、デクリメントすることで削除できるようになる。

偽陽性率はビット配列長を大きくすると低くなり、データの数が増えると高くなる。 kはビット配列の情報量を最大化させる、つまり半分のビットが1になるように最適化する。

自己情報量、エントロピー、KL情報量、交差エントロピーと尤度関数 - sambaiz-net

Cuckoo filter

2014年に発表されたフィルタ。

Cuckoo Filter: Practically Better Than Bloom

Cuckoo filter

データを追加する際は、そのままハッシュ関数に通したi_1と、フィンガープリントfをハッシュ関数に通したものとi_1のXORであるi_2を取って、 対応するいずれかのバケットが空いていたらそこにfを入れる。 いずれも空いていなければ、そのどちらかから一つ追い出して、その値とindexのXORを取れば分かるもう片方のバケットに再度入れる。 既にそこも一杯ならそこからも追い出し、同様の処理を行う。これを追い出されなくなるまで繰り返す。 そして、もしfがいずれのバケットにも入っていない場合、キーが存在しないことが分かる。それをバケットから除けば削除される。

バケットの空きが十分ならCounting filterよりも高速にデータを追加できるが、埋まるに連れて追い出しが頻発しパフォーマンスが下がっていく。

フィンガープリントを長くすると、Bloom Filterと比較して少ない容量で偽陽性率を低くできる。

参考

確率的データ構造の比較:カッコウフィルタ対ブルームフィルタ | POSTD

ブルームフィルタ - Wikipedia