きまぐれ日記: Bloom filter最近 Bloom filter というアルゴリズムを知りました。1970年に考案された古いアルゴリズムです。 http://en.wikipedia.org/wiki/Bloom_filter http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html#SECTION00053000000000000000 http://www.perl.com/pub/a/2004/04/08/bloom_filters.html Bloom filter は、キー(通常は文字列)の存在のみをコンパクトなデータ構造で高速に判定するためのアルゴリズムです。キーの存在のチェックでしたら通常の hash でいいのですが、コンパクトになるとは限りません。 Bloom filter は "false positive"、つまり「キーが存在していないのに存
http://www.ricoh.co.jp/rdc/techreport/No22/r7/r7.htm
