修士論文 要旨

Min-hash 法の拡張を用いた
ストリームモデルにおける L0 ノルム計算
数理情報学専攻 48156219
指導教員

定兼邦彦教授1. Cash register model: 更新値 a が常に正である.

1 ストリームモデル

2. Strict turnstile model: 更新値 a が負の値を取ること

ストリームモデルは大規模かつ高速に生じるデータ
を 処 理 す る た め の 計 算 モ デ ル で あ る.

ストリームモデルは形式的には次のように定義される: 入力として(i1 , a1 ), (i2 , a2 ), . . . , (im , am ) が与えられるとする. ここで it ∈ {i, 2, . . . , n}, at ∈ {−r, −r + 1, . . . , r} とし, nは扱うベクトルのサイズ, r は更新値の上限である. この入力ストリーム (it , at ) は「時刻 t においてベクトルの第 it 成分が at だけ更新された」と解釈される. すな
わちストリームモデルにおいては, (初期状態で零ベクトルである) ベクトル x ∈ Zn を考え, ストリーム入力(it , at ) (t = 1, 2, . . . , m) が x を
xit = xit + a,豊岡祥xj = xj (j ̸= it )として更新するものと定義する (図 1). このベクトル xを, ストリーム (i1 , a1 ), . . . , (im , am ) が与える累積ベクトルと呼ぶ. いま, ストリーム入力としては n, m が非常に大きい場合を扱うので, この累積ベクトル x は明示的に持つことができない. ストリームアルゴリズムの目的は, 限られた計算領域のみを用いて, x に関する情報を計算することである. 多くの場合 O(log n) ビットの計算領域で動作するアルゴリズムが求められることになる. 例えば, x の非零成分数やノルムなどを限られた計算領域で計算するアルゴリズムが盛んに研究されている[1, 2, 3, 4]. ストリームモデルはその入力の取りうる値のを許すが, 累積ベクトルの成分 xi の値は常に非負である.

3. Non-strict turnstile model: 更新値 a も累積ベクトルの成分 xi も負の値を取ることを許す.

1. はデータが入力される一方のモデルで, 2,3 がデータの削除を許すモデルと解釈できる. 後者のモデルほど一般性が高いことに注意されたい.
ストリームモデルの応用例としてネットワーク管理が挙げられる. 入力ストリームの (i, a) において i を IP アドレス, a をそのアドレスが行った通信量とすると, 累積ベクトル x の第 i 成分 xi はアドレス i が行った総通信量ということになる. また, x の非零成分やノルムは通信を行ったアドレスの総数や, その分布に関する情報を与える.

2 研究の流れ
本研究では, ストリームモデルにおける累積ベクトルx の L0 ノルム (非零成分数) を求める問題を扱う. この問題はモデルを 1. Cash register model に限ったとき,入力中の異なる i の種類をカウントする問題に帰着する(a > 0 ならば一度現れた i に対して必ず xi > 0 となるためである). そこで本研究では種類カウント問題のアルゴリズムである (次節で述べる)LogLog counting [3]というアルゴリズムを 3. Non-strict turnstile model において動作するように改良し, L0 ノルムを求めるアルゴリズムを提案する. LogLog counting は Min-hash法と呼ばれる方法を用いたアルゴリズムの一種で, これは入力ストリーム上でハッシュ関数の最大値を求めることによって動作する. 本研究ではこの Min-hash 法を 3.

Non-strict turnstile model で動作するように拡張することによって LogLog counting の改良を行う.

3 先行研究: LogLog counting
図 1. ストリームモデル[3] は入力ストリーム i1 , i2 , . . . , im の中の異なるアイテムの種類数を推定するアルゴリズムとして, 以下のよ範囲によって 3 種類に分けることができる.

うなものを与えた:Min-hash 法の拡張を用いたストリームモデルにおける L0 ノルム計算 (豊岡祥)初期化:

ハッシュ関数族 H = {h : [n] → [log n]} からハッシュ関数 h をランダムにひとつ選び, 固定する.
更新:

ストリーム入力 i に対し M = max{M, h(i)} と更新する.
出力:

上記の計算を O(ϵ−2 ) 個並行して行い, 得られたM の平均値 M̃ に対して α2M̃ を返す.

近似アルゴリズムは Ω(N ) ビットを必要とする

2. (1 ± ϵ) 近似を定数確率で求める乱択近似アルゴリズ
ムは log N ビットを必要とする.
この結果から提案アルゴリズムの計算量は理論的下界に近い (それぞれ下界の log log mr 倍, log ϵ−1 + log log mr倍) であることが示された. 計算量下界の証明には, 通信

ここで α は適当な比例定数, H は一様ランダムに h を決

複雑度 [5] という道具を用いた.

jめたときに, ハッシュ値が j を取る確率が 1/2 となるようなハッシュ関数族である. 求めたい種類数を x とおく

5 提案アルゴリズム (L0 ノルム)と, このような方法で求められた M は期待値が log x に

LogLog counting の更新ステップを前節で与えた Min-なり, 分散が定数で抑えられることが示すことができる.

hash 法の拡張アルゴリズム 1 で置き換えることによっ

LogLog counting はハッシュ関数 h の入力ストリーム上て, 最終的に得られるアルゴリズムは次のようになる:での最大値を求めることによって動作している. このような方法はストリームアルゴリズムの設計においてしばしば用いられる手法であり, Min-hash 法と呼ばれる.

4 Min-hash 法の拡張

ハッシュ関数族 H = {h : [n] → [log n]} から初期化:

ハッシュ関数 h をランダムにひとつ選び, 固定する.
更新:

ストリーム入力 (i, a) に対し Min-hash 法の拡張

アルゴリズム (前節の 1) を動作させ, ハッシュ関数

LogLog counting は Cash register model においてハッシュ関数の最大値を求めることによってアイテムの種類数 (=L0 ノルム) を求めた. したがって Lo ｇ Logの最大値 M を得る.
出力:

上記の計算を O(ϵ−2 ) 個並行して行い, 得られたM の平均値 M̃ に対して α2M̃ を返す.

counting を拡張してより一般のモデルである Non-strict

前 節 の 提 案 ア ル ゴ リ ズ ム 1 に お い て δ = O(ϵ2 ) とturnstile model において L0 ノルムを求めるには, Non-すれば O(ϵ−2 ) 個全てのアルゴリズムが正しく M をstrict turnstile model においてハッシュ関数の最大値を出 力 す る.

求めることができれば良いことになる. 本研究ではこのO(ϵ−2 log n(log ϵ−1 + log log mr)) ビットで動作する. こ問題, すなわち, 入力ストリームが与える累積ベクトルののアルゴリズムは空間計算量の観点で従来の最良結果 [4]非零成分を持つインデックス i 上での h(i) の最大値 Mと一致し, よりシンプルなアルゴリズムの構成を与えるを求める問題に対して, 以下の 2 つのアルゴリズムを提ものとなっている.

案した.
提案アルゴリズム 1 O(N (log δ

したがってこのアルゴリズムは全体で参考文献−1+log log mr)) ビット

で確率 1 − δ で M を求める乱択アルゴリズム.
提案アルゴリズム 2 O(ϵ−2 log N (log ϵ−1 +log log mr))
ビットで M の (1 ± ϵ) 近似を求める乱択近似アルゴリズム.
ここで N はハッシュ関数の値域の大きさである. アルゴ
リズムは, 各ハッシュ値を管理するようなサイズ N のベクトルを保持し (1), さらにそのベクトルを log N サイズになるように線形写像によって圧縮する (2) ことによって構成される.
また, 本研究では Non-strict turnstile model においてハッシュ値の最大値を求めるために必要な空間計算量の下限を与えた. 具体的には以下の 2 つを証明した.

1. 乱択アルゴリズムもしくは ((1 ± ϵ) 近似を求める)[1] N. Alon, Y. Matias and M. Szegedy,The
space complexity of approximating the frequency moments, Journal of Computer and System Science(1999) 58(1), pp. 137–147.
[2] G. Cormode, M. Datar, P. Indyk and S.
Muthukrishnan, Comparing data stream using hamming norms (how to zero in), IEEE Transactions andKnowledge and Data Engineering (2003) 15(3), pp.
529–540.
[3] M. Durand and P. Flajolet, Loglog counting oflarge cardinalities (extended abstract), In Proceedingsof ESA (2003), pp. 605–617.
[4] D. M. Kane, J. Nelson and D. P. Woodruff, An
optimal algorithm for the distinct elements problem,
In Proceedings of POD (2010) pp. 41–52.
[5] E. Kushlevitz and N. Nisan, Communication complexity , Cambridge University Press(1997)