論文メモ 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)} $$ という関係になる。

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