はてなブックマーク - ブルームフィルタ

ブルームフィルタ - Wikipedia

ja.wikipedia.org

タグ : algorithm bloomfilter アルゴリズム Programming プログラミング data structure wikipedia google ir 用語

コンピュータ・IT 92 users

ブルームフィルタ（Bloom Filter）は、1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。偽陽性（False Positive）による誤検出の可能性があるが、偽陰性（False Negative）はない。要素を集合に追加することができるが、削除することはできない（Counting filter を使えば削除できる）。集合に要素が追加されればされるほど、偽陽性の可能性が高くなる。 [編集] 使用例例え... > このページを見る

最終更新時間: 2007年05月25日15時32分

▼ブログで紹介する

みんなのブックマーク人気（0）新着

rin51 Bloom filter, ブルームフィルタ, アルゴリズム
[データ構 2012/03/22
makisyu
これ探索が定数時間で書けそうな気がする。実際に使ってみたい。 2011/06/04
mooz data_structure, algorithm
"空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる" 2010/11/04
takahi-i
bloom filters 2010/02/18
ytoku データ構造, プログラミング
なるほど。集合Aに対してハッシュ関数集合H={h_1, ..., h_k}; フィルタのデータF={h(x)|h∈H, x∈A}; でxがAの要素かどうかの判定が(∀h∈H)h(x)∈F 2009/12/10
korn_freak algorithm, google
bloom filter false positveを許容したデータ構築 2009/12/07
tettsyun algorithm
bloom filter 2009/10/28
kuenishi programming
だめだわけわからん 2009/04/30
H_Holon
使い道があるわけじゃないけど、発想が面白いなぁと。 2009/02/23
shiumachi algorithm, Hadoop, HBase, data structure
"空間効率の良い確率的データ構造であり、要素が集合のメンバーであるかどうかのテストに使われる。偽陽性による誤検出はあるが、偽陰性はない。追加はできるが、削除はできない" 2008/08/25