Bloom Filter

概要

1970年にBloom氏が開発。とある集合に、目的の要素が存在するか確認する為の不確定なAlgorithm。
偽陰性があってはならない。「セットに要素が入っている」状態をTrueとすると以下の様になる。

結果、このAlgorithmを利用すると
「未だに登録されていないDataに対して登録されている」という偽陽性を示す事はあるが
「既に登録されているDataに対して登録されてない」という偽陰性を示す事はない。特性上、Dataの蓄積が進むほどに偽陽性が高まっていく。

詳細な説明はや、に載っている。