An Improved Data Stream Summary: The Count-Min Sketch and its Applications(2005)

#分散システム

December 7, 2022

Count-Min Sketch(CM Sketch)は、単位時間ごとに1要素ずつ更新される$n$次元のベクトルの要素を$n$の劣線形の計算量で集計できるデータ構造である。空間の大きさはパラメタで指定する誤差大きさと誤差の生じる確率に依存する。誤差と確率のパラメタを$\epsilon$と$\delta$とすると、CM sketchは$\lceil{\ln \frac{1}{\delta}\rceil}\times \lceil\frac{e}{\epsilon}\rceil$の二次元行列である。 $\ln$の底は$e$である。要素の値、ベクトルの内積、ある範囲の要素の和を劣線形の計算量で求めることができる。また、これらと二分探索を応用すれば、指定した値よりも大きい要素のみからなる範囲や分位数も計算できる。

時刻$t$の$n$次元のベクトルを$\boldsymbol{\rm a}(t)=[a_1(t),\dots a_i(t),\dots a_n(t)]$とする。はじめ$\boldsymbol{a}$は$\boldsymbol{0}$であり、時刻$t$に$i_t$番目の要素に$c_t$が加算される前提である。より厳密には $$ a_{i_t}(t) = a_{i_t}(t-1) + c_t;\ \ a_{i'}(t) = a_{i'}(t-1)\ \ i'\neq t_t \ \ c_t > 0 $$ という状況である。 $w=\lceil\frac{e}{\epsilon}\rceil, d=\lceil\ln\frac{1}{\delta}\rceil$とする$d\times w$の二次元行列$\text{count}$の全ての要素の初期値は0である。また、$\{1\dots n\}$から$\{1\dots w\}$に写像する$d$個のハッシュ関数$h_1\dots h_d$を$d$ワイズ独立なハッシュ関数の集合から無作為に$d$個選ぶ。このとき、時刻$t$における$i_t$番目の要素への$c_t$を加算は $$ \forall 1 \le j \le d: \textit{count}[j,h_j(i_t)] \leftarrow \textit{count}[j,h_j(i_t)] + c_t $$ に対応する。

$i$番目の要素の推定値$\hat{a}_i$は $$ \hat{a}_i = \min_j \textit{count}[j,h_j(i)] $$ であり、$a_i\le \hat{a}_i$、かつ、少なくとも$1-\delta$の確率で$\hat{a}_i\le a_i + \epsilon||\boldsymbol{\rm a}||_1$である。

内積の推定値$\widehat{\boldsymbol{\rm a}\odot \boldsymbol{\rm b}}$は$\min_j(\widehat{\boldsymbol{\rm a}\odot \boldsymbol{\rm b}})_j=\min_j \sum^w_{k=1}\textit{count}_{\boldsymbol{\rm a}}[j,k]*\textit{count}_{\boldsymbol{\rm b}}[j,k]$であり、$\epsilon$と$\delta$の間には $$ \textrm{Pr}\left[\widehat{\boldsymbol{\rm a}\odot \boldsymbol{\rm b}} -\boldsymbol{\rm a}\odot \boldsymbol{\rm b} > \epsilon ||\boldsymbol{\rm a}||_1||\boldsymbol{\rm b}||_1\right]\le\delta $$ が成立する。ある範囲の和については、$\boldsymbol{\rm b}$の内積を応用すれば求められる。

論文へのリンク

雑記

$n$を途中で変えられない不便さはあるが、アクセス頻度の集計とかに使えそう。