カウンターサイズとカウンターオーバーフローの基礎知識

カウンターサイズ

カウンティングブルームフィルタなどの確率的データ構造では、オーバーフローを回避するために、各カウンターのサイズを十分に大きく設計する必要があります。ポアソン近似に基づく解析から、その適切なサイズが導かれています。

• ポアソン近似による解析では、カウンターあたり4ビットのサイズが推奨されています。
• k = (ln 2)m/n 個のカウンターを実装した場合、各カウンターの平均負荷は ln 2 になります。
• あるカウンターの負荷が16以上になる確率は、e^-ln2(ln 2)¹⁶/16! ≈ 6.78×10^-17 と極めて小さく、実用上ほぼ無視できます。
• これらの理由から、性能比較の際にはカウンターあたり4ビットの構成が標準的に採用されています。

カウンターオーバーフロー

カウンターがオーバーフローを起こすと、その値は最大値に達したまま更新されなくなります。この状態がシステムに与える影響について理解しておくことが重要です。

• カウンターがオーバーフローすると、その値は最大値に張り付いた状態になります。
• この状況が後から偽陰性（false negative）を引き起こすのは、本来ゼロ以外の値を保つべきカウンターが、最終的に0まで減少してしまった場合に限られます。
• このような状況に至るまでの期待時間は非常に長いものの、偽陰性が許容されないアプリケーションでは、この潜在的なリスクを常に念頭に置く必要があります。
• カウンターオーバーフローを回避するためには、カウンターのサイズを十分に大きく設計しなければなりません。解析の結果、カウンターあたり4ビットあれば十分であることが判明しています。

以上のように、ポアソン近似に基づく確率解析によって、4ビット/カウンターというコンパクトな設計でもオーバーフローのリスクを実用上問題ない水準まで抑えられることが示されています。