論文メモ Space/Time Trade-offs in Hash Coding with Allowable Errors

February 20, 2021

ハッシュコーディングで要素がハッシュエリアにあるかを高速に調べる手法で、ブルームフィルタの名で知られる。 偽陽性を認めることで、ハッシュ値の保持に必要なハッシュエリアを小さくしているため、ハッシュエリアが大きくなるデータでも利用することができる。 例えば、データベースのストレージで使われており、検索するキーがデータベースに存在するか事前に確かめることで、存在しないキーのための不要なディスクの読み取りを省くことができる。 なお、偽陰性の誤りはない。

ハッシュエリアを\(0\)から\(N-1\)までのアドレスをもつ\(N\)ビットの空間とする。 何も要素のない初期状態では、すべて\(0\)に初期化されている。 ある要素をハッシュエリアに追加するときは、ハッシュコーディングで\(0\)から\(N-1\)までの値をとりえる\(d\)個の値を要素から計算し、その\(d\)個のアドレスに1を格納する。 要素がハッシュエリアに含まれるか確かめるときは、追加時と同様、\(d\)個のアドレスを求める。 そして、\(d\)個のアドレスにある全ての値が\(1\)であれば要素がハッシュエリアに存在し、それ以外は存在しないとみなす。

要素の存在を確かめる時間、ハッシュエリアの大きさ、偽陽性の確率にはトレードオフがある。 確認にかかる時間の単位を、1ビットにアクセスして値を調べる時間として、3つのトレードオフの関係を求める。 \(n\)個の要素が追加されたときに、ハッシュエリアの全てのビットに対する0のままのビットの割合\(\phi\)は $$ \phi = \left(1-\frac{d}{N}\right)^n $$ これは\(d< <N\)と仮定すると $$ \begin{align} \log_2{\phi}&=\log_e\left(1-\frac{d}{N}\right)^n\log_2e\\
&=-n\left(\frac{d}{N}\right)\log_2e \end{align} $$ に近似できる。また、あるハッシュエリアに存在しない要素が誤って存在すると判定される確率\(P\)は $$ P=(1-\phi)^d $$ であり、近似式と組みあわせると $$ N=n\left(-\log_2P\right)\frac{\log_2e}{\log_2\phi\log_2(1-\phi)} $$ になる。次に時間について考えると、\(x\)ビットが検査されるのは、最初の\(x-1\)ビットが1で\(x\)番目のビットが0のときであり、その確率は $$ \phi(1-\phi)^{x-1} $$ になる。\(P«1\)かつ\(d»1\)と仮定すると、ハッシュエリアに存在しないと判定される要素の検査でアクセスされるビット数の期待値\(T\)は $$ \begin{align} T&=\sum_{x=1}^{\infty}x\phi(1-\phi)^{x-1}\\
&=\frac{1}{\phi} \end{align} $$ 以上から、時間とハッシュエリアのサイズと偽陽性の確率は $$ N=n(-\log_2P)\frac{\log_2e}{\log_2(1/T)\log_2(1-1/T)} $$ という関係になる。

論文をこちらからダウンロードできます。