Bloom filter

1.4K Views

April 11, 23

スライド概要

profile-image

分散システムとかデータベースとかロックフリーとかが好きです。

シェア

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

よく分かるBloomFilter

2.

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

3.

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

4.

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

5.

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

6.

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

7.

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

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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