Lossy Countingアルゴリズムの仕組み：データストリームから頻出アイテムを効率的に検出する方法

Lossy Countingアルゴリズムの概要

Lossy Countingは、大量のデータストリームから頻出アイテムを近似的に検出するための有名なアルゴリズムです。ユーザーは2つの入力パラメータを指定します。1つは最小サポート閾値σ（シグマ）、もう1つは許容誤差の上限ε（イプシロン）です。理論上、入力ストリームは幅 w = ⌈1/ε⌉ のバケットに分割されて処理されます。

データ構造：頻度リスト

Nを現在のストリーム長、つまりそれまでに処理済みのアイテム総数とします。このアルゴリズムでは、頻度が0より大きいすべての要素を管理するために「頻度リスト」というデータ構造を使用します。各アイテムのエントリには、次の2つの値が保持されます。

• f：近似的な頻度カウント
• Δ：fに含まれ得る最大誤差

アルゴリズムの処理手順

新しいバケットが到着すると、そのバケット内のアイテムが順次頻度リストへ挿入されます。対象アイテムがすでにリストに存在する場合は、頻度カウントfを1だけ増加させます。存在しない場合は、頻度カウント1として新規に追加します。さらに、そのアイテムがb番目のバケットから来たものであれば、頻度カウントに含まれる可能性のある最大誤差Δを b−1 に設定します。

バケット境界での剪定（プルーニング）

バケット境界に達するたび、つまりNが幅wの倍数（w、2w、3w…）に達するたびに、頻度リストの整理が行われます。現在のバケット番号をbとすると、あるエントリが次の条件を満たす場合、そのエントリは削除されます。

f + Δ ≤ b

この剪定処理により、アルゴリズムは頻度リストを常に小さく保ち、主記憶（メインメモリ）に収まるように設計されています。リストに保存された各アイテムの頻度カウントは、真の頻度そのものか、それ以下の値（過小評価）になります。

近似精度の保証（誤差解析）

近似アルゴリズムにおいて本質的な要素は近似比、すなわち誤差上限です。ここで、アイテムが削除されるケースを考えてみましょう。削除は、あるアイテムが f + Δ ≤ b を満たすときに発生し、ここでbは現在のバケット番号です。

b ≤ N/w が成り立つことから、b ≤ εN であることが分かります。アイテムの真の頻度は最大でも f + Δ であるため、剪定によって生じる過小評価は最大で εN に抑えられます。

あるアイテムの実際のサポートがσ（頻出とみなされるための最小サポート、つまり下限）である場合、その実際の頻度はσNとなり、頻度リスト上の頻度fは少なくとも σN − εN 以上であることが保証されます。

頻出アイテムの出力

したがって、頻度リストの中から f ≥ σN − εN を満たすすべてのアイテムを出力すれば、真に頻出なアイテムは漏れなく出力されます。一方で、実際の頻度が σN − εN 以上 σN 未満である「準頻出アイテム」も一部混ざって出力される点に注意が必要です。

このわずかな偽陽性こそがLossy Countingの「損失を許容する（lossy）」性質であり、厳密な正確性と引き換えに、限られたメモリで大規模ストリームを高速処理できる実用性を実現しています。