Counting filter
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/15 00:00 UTC 版)
「ブルームフィルタ」の記事における「Counting filter」の解説
Counting filter はブルームフィルタの実装の一種で、再生成をせずに要素の削除ができるものである。Counting filter では、配列の各要素はビットから n ビットのカウンタへと拡張されている。通常のブルームフィルタは Counting filter でカウンタのサイズが 1 ビットの場合であると見なせる。Counting filter は L. Fan, P. Cao, J. Almeida, and A. Broder. Summary cache: A scalable wide-area Web cache sharing protocol. In Proceeding of SIGCOMM ’98, 1998 で紹介された。 集合への要素の追加は各配列要素を1ずつ増やすことになり、参照は各配列要素がゼロではないことを確認することになる。要素の削除をおこなう場合には、対応する配列要素のカウンタを1つずつ減らせばよい。 カウンタのオーバフローが発生する問題が考えられるため、カウンタサイズ n はそのようなことがなるべく発生しないように十分大きくしなければならない。もしもオーバフローが発生したら、ブルームフィルタ本来の偽陽性発生がありうるという性質に基づいて、そのカウンタを要素の追加や削除で変更せずに、最大値のままにしておくのがよいとされている。
※この「Counting filter」の解説は、「ブルームフィルタ」の解説の一部です。
「Counting filter」を含む「ブルームフィルタ」の記事については、「ブルームフィルタ」の概要を参照ください。
- Counting filterのページへのリンク
