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