ブルームフィルターを数える

基本概念

カウントブルームフィルターは、要素のシーケンスが指定されたときに、指定された要素のカウント数が指定されたしきい値よりも小さいかどうかをテストするために実装されるブルームフィルターの一般化されたデータ構造として定義されます。ブルームフィルターの一般化された形式として、誤検知の一致の可能性はありますが、誤検知の可能性はありません。つまり、クエリは「おそらくしきい値以上」または「間違いなくしきい値未満」のいずれかを返します。

アルゴリズムの説明

• ブルームフィルターのカウントで使用されるパラメーターのほとんどは、n、kなどのブルームフィルターと同じように定義されます。 mは、カウントブルームフィルターのカウンター数として表されます。これは、ブルームフィルターのmビットの拡張です。
• 空のカウントブルームフィルターがmカウンターとして設定され、すべて0に初期化されます。
• ブルームフィルターと同様に、k個のさまざまなハッシュ関数を定義する必要があります。各ハッシュ関数は、いくつかのセット要素をm個のカウンター配列位置の1つにマッピングまたはハッシュし、均一なランダム分布を作成します。また、kが定数であり、mよりはるかに小さく、追加する要素の数に比例します。
• ブルームフィルターの主な一般化は、要素の追加です。要素を追加するには、要素をk個のハッシュ関数のそれぞれに挿入してk個の配列位置を取得し、これらすべての位置でカウンター1をインクリメントします。
• しきい値がθの要素をクエリするには（要素のカウント数がθ未満かどうかを確認します）、k個のハッシュ関数のそれぞれに挿入してk個のカウンター位置を取得します。
• これらの位置にあるカウンターのいずれかがθよりも小さい場合、要素のカウント数は間違いなくθよりも小さくなります。それが高くて等しい場合、対応するすべてのカウンターはθ以上であるはずです。
• すべてがθ以上の場合、カウントが実際にθ以上であるか、カウンターが偶然にθ以上であるかのいずれかです。
• カウントがθ未満であっても、すべてがθ以上である場合、この状況は誤検知と定義されます。ブルームフィルターと同様に、これも最小限に抑える必要があります。