Mining of Massive Datasetsの4.3節の概要を書きます。
- ストリームの中から集合を見つける
- メモリーに載り切らない時どうするか？
- Bloom filteringでしょ！
4.3.1 A Motivating Example
- メールアドレスの中からスパムと登録されたアドレスをdropしたい
- 最大10億個のメールアドレスの集合Sを仮定する
- ストリームはメールアドレスと、メール自身のペアとする
全メールアドレスをメモリに保持するのは辛いし、ディスクアクセスもしたくない
Bloom filteringの基本は、bit arrayで集合Sの要素を表現する
要素に対して、k個のhash関数を通した値を保持しておく
streaming dataに対してhash関数を書けて、全ての値が0になったらspamとして捨てる
hashの衝突で、ざっくり1/8くらいはfalse positiveが発生するが、7/8殺せるなら問題ない
4.3.2 The Bloom Filter
Bloom filterの構成要素は以下からなる。
- 0で初期化された、n-bitのarray
- ハッシュ関数 h_1, h_2, ..., h_k。 "key"となる値をn個のbucketに保管し、n bitのbit-arrayを作る
- m個の値を持った集合S
集合Sのkey Kに対して、h_i(K)を計算して対応するbitについて、bit-arrayに1を立てる
ここのFigure. 1-4がわかりやすい
4.3.3 Analysis of Bloom Filtering
原理上、false positiveが発生してしまう。
その確率は、bit-arrayを持つ数でコントロールできる。
- x個のダーツの的とy本のダーツがあったとする
- どのダーツも当確率で的に当たるとする
- いくつの的に1本以上のダーツが当たるか？
ある的にダーツが1本も当たらない確率は (x-1)/x
y本のダーツがある的にあたらない確率は
$$ \left(\frac{x-1}{x} \right)^y = \left(1-\frac{1}{x} \right)^{x \left( \frac{y}{x} \right)} $$
1.3.5 の近似より、εが小さい時
$$ (1-ε)^{1/ε} = 1/e $$
とかけるので
$$ e^{-y/x} $$
になる。
example 4.3はわかりやすい例
実際の問題だと、
集合S は要素を m 個持っていて、bit-arrayはn-bit、k個のハッシュ関数を仮定する。
的の数はx = n, ダーツの数は y=kmとなり
0のままのbitの数は
$$ e^{-km/n} $$
全部1が立つfalse positiveなケースは
$$ 1-e^{-km/n} $$
ハッシュの数を増やすと
$$ \left( 1-e^{-km/n} \right)^{k} $$
4.3.4 Exercises for Section 4.3
省略