カウンティング・ブルームフィルターとは？基本概念とアルゴリズムを解説

基本概念

カウンティング・ブルームフィルター（Counting Bloom Filter）は、ブルームフィルターを一般化したデータ構造であり、要素のシーケンスが与えられた際に、特定の要素の出現回数（カウント数）が指定された閾値未満であるかどうかを判定するために用いられます。

ブルームフィルターの一般化形であるため、偽陽性（false positive）が発生する可能性はありますが、偽陰性（false negative）は発生しません。言い換えると、クエリに対する応答は「閾値以上である可能性がある」か「確実に閾値未満である」のいずれかとなります。

この特性により、カウンティング・ブルームフィルターは、ネットワークトラフィックの測定やパケットカウント、キャッシュシステムなど、頻度の推定が必要なさまざまな分野で活用されています。

アルゴリズムの説明

パラメータの定義

• カウンティング・ブルームフィルターで使用されるパラメータの多くは、ブルームフィルターと同じ定義です（n、kなど）。mはカウンティング・ブルームフィルター内のカウンターの数を表し、ブルームフィルターにおけるmビットを拡張したものです。
• 空のカウンティング・ブルームフィルターは、すべて0に初期化されたm個のカウンターとして構成されます。
• ブルームフィルターと同様に、k個の異なるハッシュ関数を定義する必要があります。各ハッシュ関数は、集合内の要素をm個のカウンター配列位置のいずれかに、一様なランダム分布となるようマッピング（ハッシュ）します。kはmよりはるかに小さい定数であり、追加される要素の数に比例します。

要素の追加

ブルームフィルターからの主な一般化は、要素の追加操作にあります。要素を追加するには、その要素をk個のハッシュ関数それぞれに入力してk個の配列位置を取得し、これらすべての位置にあるカウンターの値を1ずつ増加させます。

閾値を用いた照会

閾値θを指定して要素を照会する場合（要素の出現回数がθ未満であるかどうかを確認する）、その要素をk個のハッシュ関数それぞれに入力して、k個のカウンター位置を取得します。

• これらの位置にあるカウンターのいずれかがθ未満であれば、その要素の出現回数は確実にθ未満です。もし出現回数がθ以上であれば、対応するすべてのカウンターはθ以上の値になっているはずだからです。
• すべてのカウンターがθ以上である場合、出現回数が実際にθ以上であるか、あるいは偶然カウンターがθ以上になっているかのどちらかです。

偽陽性について

実際の出現回数がθ未満であるにもかかわらず、すべてのカウンターがθ以上である場合、この状況は偽陽性（false positive）と定義されます。ブルームフィルターと同様に、この偽陽性の確率は最小限に抑えることが重要です。