Count-Min Sketch
Count-Min Sketch は複数のハッシュ関数で頻度を推定し、過大評価と引き換えに副線形の空間を使う。ストリームの頻度統計に使われる。
目的
データストリーム上で、空間効率の良い近似頻度統計を提供する。
メカニズム
d 行 w 列のカウント行列。更新 x: 各行 i で count[i][h_i(x)]+=1。照会 x: min_i count[i][h_i(x)] を取る。過大評価の確率は高々 we^(-d) で、誤差は ≤ε||f||_1。
ユースケース
- ストリームの統計処理
- 頻度の見積もり
- Top-k の検出