ブルームフィルタ - Wikipedia

この項目では、確率的データ構造について説明しています。画像にぼかし効果を付加する画像フィルタについては「川瀬のブルームフィルター」をご覧ください。 ブルームフィルタ（英語: Bloom filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。なお集合に要素を追加することはできるが、集合から要素を削除することはできない（ただし、拡張をした counting filter であれば削除もできる）。集合に要素を追加していくにつれて偽陽性の

[shiumachi]

"空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。偽陽性による誤検出はあるが、偽陰性はない。追加はできるが、削除はできない"

[SWIMATH2]

確率的データ構造。集合の要素判定を、 偽陽性は生じものの空間計算量をおさえられるらしい。アルゴリズムはシンプル

[vanbraam]

Mutually ExclusiveではないがCollectively Exhaustiveな検出が行えるfilter.一度filterを作ってしまえば元データを(メモリ上から)捨てられて,極めて小さなデータ量で検出が行えるのが利点,という理解

[asonas]

データ集合の話

[rin51]

[データ構

[mooz]

"空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる"

[takahi-i]

bloom filters

[ytoku]

なるほど。集合Aに対して ハッシュ関数集合H={h_1, ..., h_k}; フィルタのデータF={h(x)|h∈H, x∈A}; でxがAの要素かどうかの判定が(∀h∈H)h(x)∈F

[tettsyun]

bloom filter

[kuenishi]

だめだわけわからん

[H_Holon]

使い道があるわけじゃないけど、発想が面白いなぁと。

[pipehead]

Bloom filter; Counting filter, Bloomier filter