フィルタで偽陽許して含むか判定したい

特殊なデータ構造を持つことで、データがあるデータの集合に含まれるかをどうかを効率よく判定する技術について紹介します. フィルタと呼ばれるデータ構造を用いることで、高速にそしてメモリを贅沢に消費することなく判定することができます. データベース、ファイルシステムなどでよく用いられ、Google BitTable, ApacheHBase, Apache CassndraやLevelDB等において使用されています. ここで紹介するのは、以下の4つです. <手法> ・Bloom Filter(ブルームフィルタ) 　　データの新規挿入とハッシュデータの照合が可能でどちらもO(k).フラグを格納する長さkの配列を持つ. ・Counting Filter(カウンティングフィルタ) 　　Bloom Filterに削除を含めたもの.ブルームフィルタでは常に配列に1を立てていたが、インクリメントするように変更.削除するとデクリメント. ・Quotient Filter 　　こちらも削除ができるフィルタで、各配列でis_occupied, is_continuation, is_shiftedを持つのが特徴. ブルームフィルタよりメモリを使うがCounting Filterよりは省メモリ.また二つ以上のQuotient Filterはマージができるのも特徴 ・Cuckoo Filter(カッコウフィルタ) 　　削除操作が可能。ブルームフィルタより必要なハッシュもメモリアクセスも一般的に少ないため高速.

ブルームフィルタの手順はとてもシンプルです. 手順 1. データ群とは別にkの長さの配列を用意します.0で配列を初期化します. データの登録時 2. 登録するデータを複数のハッシュ関数でハッシュ化して対応している箇所の配列の要素の値を1にします. データの判定時 3. 探すデータを複数のハッシュ関数でハッシュ化して対応した箇所の配列の要素が全てが1になっていることを確認します. 全て1になっている⇒「含まれている可能性あり」、一つでも1になっていない⇒「含まれていることはない」

Counting FilterとはBloom Filterの配列の各要素において1を立てるのではなく、登録のたびに1を足していく方針に変えた手法. このようにすることで、削除を行うことができ削除操作の度に1を引くようにすることで実現することが可能になる.ただ1を足していくときにオーバーフローしないように注意する必要がある.

詳しく紹介はしないので、右のWikipediaのリンクで詳細は確認願います.

Quotient FilterはCounting Filterよりもメモリ効率をよくしたBloom Filterの改良になります. Quotient Filterではハッシュがかぶったときの工夫が含まれており、is_occupied, is_continuation, is_shiftedの3つのフラグが各配列において保持されていることも特徴的です.

カッコウフィルタはカッコウハッシュテーブルを用いたフィルタです. 二つの配列と二つのハッシュ関数を用意してこのフィルタ処理を行います. またフィルタのFingerPrintとしてデータの最初の方の数bitも保持しておきます. <データの登録手順> (結構やっていることはシンプル) 1. データを一つ目のハッシュ関数で一つ目の配列で入れる要素の箇所を決める.もし何もなかったらそこにデータの先頭数bitにあたるFingerPrintを入れて登録終了 . 2. もし1.でかぶっていたら、二つ目のハッシュ関数で二つ目の配列で入れる要素の箇所を決める.もし何もなかったらそこにデータの先頭数bitにあたるFingerPrintを入れて登録終了. 3. もし2.で既にデータが入っていたら、入っているデータを追い出してそこに2.でハッシュ関数を通してデータのFingerPrintを登録. 追い出されたデータは入っていた配列とは別の配列に別のハッシュ関数で該当する要素の入れに行く.もし入っていたら今度は入っている要素を追い出す. 4. 3.を追い出しがなくなるまでまたは操作が上限回数まで行われたら終了する. こうすることでデータの登録は終わる. <データの判定手順> データを二つのハッシュ関数に通してどちらかの配列に自身のFingerPrintと一致するものがあれば「存在する可能性がある」と判定される.データのFingerPrintがなければ存在しない。 偽陽性になるときは、FingerPrintの先頭数bitをどれほどの長さにするかまたハッシュの配列がどれほど長いかによる. FingerPrintによる一致の確認を行っていることもあり、BloomFilterよりは偽陽性の確率が低い.