きまぐれ日記: 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"、つまり「キーが存在していないのに存

[k1m]

複数のハッシュ値域をいっしょくたにして扱う

[yzatkatamayu]

「Bloom filter は、キー(通常は文字列)の存在のみをコンパクトなデータ構造で高速に判定するためのアルゴリズムです。キーの存在のチェックでしたら通常の hash でいいのですが、コンパクトになるとは限りません。」

[lockcole]

「あるかもしれない」を許容するアルゴリズム。「確実に無い」を排除していく。以前に勉強したけど，ここの説明は初めての人でも分かりやすい。

[rhosoi]

「キーの存在のみをコンパクトなデータ構造で高速に判定するためのアルゴリズム」へぇ〜