Bloom filter

よく分かるBloomFilter

BloomFilterって？ ◼ Bloomさんが1970年に発明したデータ構造 ◼ データの集合を保持し、登録および既登録チェッ クが行える ◼ 登録にかかる時間・メモリ効率が共にO(1)

すごいじゃん！ ◼ でも代償は大きい・・・ ◼ 今そこを詳しく話してもピンと来ないと思うので図 を使って説明します

まず集合って？ ◼ ダブったデータを保持しないデータ構造 ◼ 登録するときにダブるかどうか判定して、ダブる なら登録しない ◼ 普通のデータ構造(配列・線形リスト・木)でも簡 単に実現可能

で、Bloom Filterは？ ◼ いきなりハッシュ関数やビット列を持ち出すとや る気が削がれるのでイメージ先行で話します

Bloom Filterは？ これらの集合を保持したい ぶ る う む ふ い る た

Bloom Filterは？ これらの集合を保持したい る う む ふ い る た ぶ

Bloom Filterは？ これらの集合を保持したい う む ふ い る た ぶ る ガンガン重ね書き！

Bloom Filterは？ これらの集合を保持したい む ふ い る た ぶ る う ガンガン重ね書き！

Bloom Filterは？ これらの集合を保持したい ふ い る た ぶ む る う ガンガン重ね書き！

Bloom Filterは？ これらの集合を保持したい い る た ぶ ふ む る う ガンガン重ね書き！

Bloom Filterは？ これらの集合を保持したい る た ぶ ふ む い る う ガンガン重ね書き！

Bloom Filterは？ これらの集合を保持したい た ぶ ふ む い る う ガンガン重ね書き！

Bloom Filterは？ これらの集合を保持したい ぶ ふ む い た る う 完成！

どうやって使うの？ 検証対象の上に重ねて使います ぶ ふ む い た る う

どうやって使うの？ 検証対象の文字 う る と ら せ ぶ ん 検証対象の上に重ねて使います ぶ ふ む い た る う

どうやって使うの？ 検証対象の文字 ぶ ふ い た る う む ぶ ふ む い た る う む ぶ ふ い た る う む ぶ ふ い た る と う む ら せ ぶ ふ い た る う む ぶ ふ い た る う む ぶ ふ ん い た る う •フィルタにすっぽり覆われてしまった文字は登録済み （の疑いあり •下の赤い文字が1ピクセルでも見えるなら絶対に未登録

どうやって使うの？ 検証対象の文字 ぶ ふ い た る う む ぶ ふ む い た る う む ぶ ふ い た る う む ぶ ふ い た る と う む ら せ ぶ ふ い た る う む ぶ ふ い た る う む ぶ ふ ん い た る う •このように既登録・未登録のデータを判定する •ブルームフィルタが真っ黒なほど誤判定の確率が上がる •つまり、大量に登録したブルームフィルタほど精度が悪い •でも、登録済みの物を誤って未登録と見なす事だけはない

その他 •ブルームフィルタに割くビット数を増やせば精度が向上 •使用メモリ量と精度がトレードオフ •登録済みデータは消せません •何故ならどこまでがその文字だったのか切り分け出来 ないから •どうしても消したいならフィルタ丸ごと消して再登録 •全部のピクセルについて登録時に書き込まれた回数を カウントすればデータ削除可能なBloomFilterに •もちろんメモリ効率は悪くなる

世の中では… •遠い所にデータを保存する場合、データを保存しているか どうか判断する手がかりに使える •存在しない場合にアクセスしなくなるのでHDDやネット ワークの負荷を低減させる •偽陽性が出てもアクセスした時に見つからないだけ •検証が高速・高メモリ効率なので応用範囲は夢いっぱい •今回は説明のため文字の情報を例に挙げましたが、実態 はハッシュ関数の結果をビットフィールドに論理和で上書き していくアルゴリズムです •詳しい実装は世の中にあるソースコードを読んで下さい