- 巨大なデータストリームに含まれる各アイテムの出現頻度を、近似的にカウントするための[[確率的データ構造]] - メモリ使用量がサブリニア $O(w \times d)$ # アルゴリズム ## カウント - $w \times d$ の2次元配列（テーブル） $C$ を用意し、すべて $0$ で初期化する（$w$: 幅, $d$: 深さ / ハッシュ関数の数）。 - 列ごと、$d$ 個の互いに独立なハッシュ関数 $h_1, h_2, \dots, h_d$ （出力範囲は $1 \dots w$）を用意する。 - 要素 $x$ が出現した（またはカウントを $+c$ する）とき： - 各行 $i = 1, 2, \dots, d$ について、ハッシュ値 $h_i(x)$ を計算する - 対応するセルに値を加算する： $C[i, h_i(x)] \leftarrow C[i, h_i(x)] + c$ ## ルックアップ（頻度の問い合わせ） - 要素 $x$ の頻度を推定するとき： - 各行 $i = 1, 2, \dots, d$ の値 $C[i, h_i(x)]$ を取得する - それらの**最小値**を推定頻度 $\hat{a}_x$ として返す： $\hat{a}_x = \min_{1 \le i \le d} C[i, h_i(x)]$ - ハッシュ衝突により他の要素のカウントが混ざる可能性があるため、常に真の頻度 $a_x$ 以上になる（$\hat{a}_x \ge a_x$）→ 上から抑える - 各行の最小値をとることで、ハッシュ衝突の影響を最も抑えられた行の値を採用できる # メモ - マージ可能。[[CRDT]]の一種なのでは? # 参考 - https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch -