分散ストリーム環境における多様性を考慮したデータモニタリング

DEIM Forum 2016 A7-1

分散ストリーム環境における多様性を考慮したデータモニタリング

天方 大地

†

_原

_隆浩

†

†

大阪大学大学院情報科学研究科 〒 565-0871 大阪府吹田市山田丘 1-5

E-mail:

†{

amagata.daichi,hara

}

@ist.osaka-u.ac.jp

あらまし

分散ストリーム環境におけるデータモニタリングは，センサネットワーク等のアプリケーションに代表さ

れるように，基礎的な問題である．この問題を扱うアプリケーションは，時間計算量や空間計算量だけでなく，通信量

も効率的な技術を必要とする．また，検索結果の多様化は，結果から得られる情報量を増加し，ユーザの満足度を向

上させる手段として，近年多くの注目を集めている．そこで本稿では，分散ストリーム環境において，多様性を考慮

しながら k 個のデータをモニタリングする問題に取り組む．この問題には，NP 困難およびデータ集合の動的な変化と

いう 2 つの課題がある．提案アルゴリズムは，これらの課題に対して，近似解をモニタリングすることにより，デー

タ集合の更新が頻繁に起きる場合にも効率的に解を更新する．実データを用いた実験から，提案アルゴリズムは通信

量を抑制し，多様性を保持しながらリアルタイムモニタリングを実現できることを確認した．

キーワード

分散ストリーム，データモニタリング，多様化

1.

は じ め に

近年，ローカルストリームを受信する複数のデータサイトか ら構成される分散ストリーム環境を想定するアプリケーション が多く存在する．例えば，IPネットワークモニタリング[14]， センサネットワーク[7]，および財務データモニタリング[8]な どが挙げられる．ストリーム環境では，アドホックな検索では なく，継続的なデータのモニタリングが必要である．先述した アプリケーションでは，DDoS攻撃を検出するため[14]や環境 モニタリングを行うため[7]に，データサイトから必要なデー タを取得し，それらを要求に応じて更新する必要がある．これ を効率的に実現するため，分散ストリーム環境におけるデータ モニタリングアルゴリズムがこれまでに提案されている[13]． 1. 1 研 究 動 機 データベースや情報検索の分野では，検索結果の多様化に 多くの注目が集まっている[3]．多様化されたデータ集合をO とすると，あるデータo∈ Oは，別のデータo′ ∈ Oとの類 似度が低く，分布に偏りがあるデータ集合よりも情報量が多い と考えられている．本稿では，分散ストリーム環境において， Oのようなデータ集合を継続的にモニタリングする問題に取 り組む．具体的には，スライディングウィンドウを用いてスト リームデータを管理し，多様性を考慮しながらk個のデータを モニタリングする．この多様性を考えるにあたり，本稿では， MAXMIN関数[9]を用いる．これは，あるデータ集合からk個 のデータを抽出する際，そのk個のデータ間の距離の最小値 を最大とするものである．ここで，動的データは時間と関連す る属性を保持しており，多くのアプリケーションでは現在時刻 の直近に発生したデータのみを対象とすることが一般的であ る[14]．そのため，本稿では，時間に基づくスライディングウィ ンドウ[1]を想定する．さらに，ユーザは，ある範囲（価格帯 やセンサ値）に含まれるデータのみを対象とすることも多いた

め，region of interest (RoI)を指定できることが望ましい．要約

すると，本稿では，ユーザが指定した範囲内に存在し，現在時 刻（tcur）からウィンドウズサイズ以内に発生したデータの集 合の内，MAXMINとなるk個のデータ集合をモニタリングの 対象とする．この問題は，例1および例2に示すように多くの アプリケーションが存在するにも関わらず，これまでに着手さ れていない． 例1．スライディングウィンドウを用いる代表例であるIPネッ トワークモニタリングについて考える[14]．ネットワーク管理 者は，追跡可能なデータサイズ（k）および懸念しているデー タ領域（RoI）を指定し，k個のネットワークデータをモニタリ ングする．モニタリングされているデータ集合が多様化されて いる場合，あるデータは他のデータと互いに類似していないた め，異常データが含まれていることが多いと考えられる．つま り，このアプローチは，異常検出を容易に実現できる． 例2．複数のデータサイト（データソース）から構成される株 市場分析システムについて考える．あるユーザは，価格や株数 などの範囲を指定し，その範囲内に存在するデータを俯瞰する ことが考えられる．しかし，該当する株データは大量に存在す ることが予想され[8]，全てのデータを追跡し続けることは非現 実的である．そのため，k個の多様化された株データに絞り込 むことにより，モニタリングする情報量を大きく損なうことな く，ユーザは指定した範囲内のデータを俯瞰できる． 1. 2 課 題 本稿で取り組む問題に対する効率的な解法を設計するため， 以下の課題について考える必要がある． •空間計算量，時間計算量，および通信量の効率化．分散スト リーム環境では，空間計算量および時間計算量に加えて，通信 量の削減も求められる[8]，[14].メモリ使用量（空間計算量）は， ストリーム（ウィンドウ）サイズに対して線形であることが基 本的な要件として考えられている．時間計算量は，リアルタイ ムモニタリングを実現するための重要な要素である．また，通

信量の削減は，ネットワーク帯域の有効活用に代表されるよう に，分散環境において重要な要件である．つまり，全てのデー タを送信する必要がある集中管理方法は，分散ストリーム環境 において不適切であり，既存のアルゴリズム[4]，[5]は，本問題 の効率的な解法にはなり得ない． • NP困難問題.MAXMIN問題は，NP困難であることが知られ ている[6]．そのため，最適解をリアルタイムに計算することは 非現実的であり，近似解を計算するヒューリスティックな解法 が要求される．つまり，多様性を保持しつつ，リアルタイムか つ通信量を抑制できるアルゴリズムを設計する必要がある． 提案アルゴリズムの概要．本稿で提案するアルゴリズムは，サ イズがO(k)のみのキャッシュを利用している．各データサイ トがk個のモニタリングデータをキャッシュすることにより， あるデータが発生または消滅した際の解の更新を並列計算でき る．また，既存の研究では，多様性が最も増加するデータを計 算し，インクリメンタルにk個のデータを選出するアプロー チ[9]，または最初にランダムにk個のデータを選出し，多様 性を向上できる場合にスワップを繰り返すアプローチが用いら れている[12]．提案アルゴリズムは，これらのアプローチを統 合し，より多様化されたデータ集合をモニタリングする．先述 したように，このアプローチは並列に実行されるため，更新時 間を短縮することができ，通信量はデータサイト数に比例する 結果となる． 1. 3 貢献と構成 以下に，本研究の貢献を示す．(i)本稿では，分散ストリーム 環境における多様性を考慮したデータモニタリング問題に取 り組む（2.章）．筆者らの知る限り，この問題はこれまでに取 り組まれていない．(ii)まず，集中管理環境におけるMAXMIN 問題に対するアルゴリズムを，分散環境に適用できるように拡 張する．これにより，モニタリングの初期化を実現できる（3. 章）．(iii)次に，インクリメンタルアプローチを用いたベース ラインアルゴリズムを設計する（4.章）．(iv)さらに，インク リメンタルアプローチおよびスワップアプローチを統合し，よ り多様化が可能となるグリーディアルゴリズムを提案する．提 案アルゴリズムは，ベースラインアルゴリズムに対して，更新 時間および通信量を削減する（5.章）．(v)複数の計算機を用い た実分散環境において提案アルゴリズムを評価する．実データ を用いた実験により，提案アルゴリズムの有効性およびスケー ラビリティを確認する（6.章）．また，7.章において関連研究 について議論し，8.章で本稿をまとめる．

2.

予 備 知 識

本章では，まず，想定環境を説明し，本稿で取り組む問題を 定義する． 2. 1 システムおよびデータモデル 本稿で想定する分散ストリーム環境は，1台の集中管理サー バScおよびm台のデータサイトS1，S2，...，Smから構成 される．また，Si はScと直接通信可能である．このモデル は，これまでの研究で広く用いられている一般的なものであ 0 1 2 3 4 5 0 1 2 3 4 5

𝑜

1

𝑜

2

𝑜

3

𝑜

4

𝑂

* (a) tcur− 1 における O 0 1 2 3 4 5 0 1 2 3 4 5

𝑜

1

𝑜

2

𝑜

3

𝑜

5

𝑂

*

𝑜

4 (b) tcurにおける O 図 1 k = 2 かつI = R2_{において，O}∗ tcur\O∗tcur−1=∅ となる例 る[7]，[8]，[13]．各データサイトはローカルストリームを受信 し，現在時刻tcurからW 以内に発生したデータを保持する． ここで，W はウィンドウサイズである．つまり，各データサイ トは，tcur− W よりも前に発生したデータを全て削除する．あ るデータoiは，d次元のベクトルで表すことができ，各次元の 値は実数（oi∈ Rd）である． 2. 2 問 題 定 義 距離指標および2つのデータoi およびoj が与えられた 時，そのデータ間の距離dist(oi, oj)を計算できる．ここで， dist(oi, oj)が大きいほど，oiとojの類似度は小さいとする． 以下に，分散環境におけるk-多様集合（k-diverse set）モニタ リング問題を定義する． 定義1（k-多様集合モニタリング問題）．k（>_{= 2}），RoI（I ∈ Rd_）， およびm台のデータサイトが保持しているI上のデータの集 合Oが与えられた時，この問題は，Oの部分集合Ot∗cur を継 続的に計算する．また，Otcur∗ は式(1)–(2)を満たす． O∗tcur = argmax O′⊂ =O,|O′|=k f (O′) (1) f (O′) = min oi,oj∈O′, oi|=oj dist(oi, oj) (2) この問題は，MAXMIN問題であるが，多様化のための関数と して，k個のデータ間の距離の和を最大にするMAXSUM問題 も存在する[2]．しかし，MAXSUM関数は，k-多様集合の分布 を偏らせてしまうことが知られている[5]．そのため，本稿では MAXMIN問題に焦点を当てる． 要件の補足．モニタリングを必要とするアプリケーションでは， 連続した時間におけるk個のデータの集合には共通したデータ が存在することを想定している[5]．これを実現するため，2つ の制限を設ける． まず，“差分の制限”を設ける．これは，_|Otcur∗ _\O∗_tcur−1|の値 を制限するものである．k-多様集合モニタリング問題では，Oが 変わると（ウィンドウがスライドすると）O∗tcur∩ O ∗ tcur−1=∅ となる可能性がある．そのため，差分の制限が必要となる． 例3．図1に表される2次元のユークリッド空間を考える．デー タo1，o2，o3，およびo4はtcur−1に発生し，o5はtcurに発生 したとする．k = 2および_{I = R}2_{とすると，O}∗ tcur−1={o1, o4} であり，Otcur∗ ={o3, o5}である．

例3から，Oの変化が小さい場合でも，Ot∗curが大きく変化す る場合があることがわかる．これが頻繁に起こる場合，k-多様 集合の変化を追跡することは困難である．そのため，O∗tcur に 含まれるデータの内いくつかは，スライディングウィンドウ上 に存在する限りk-多様集合に残り続けることが望ましい[5]．こ れは，ユーザがパラメータδ（1 <_{= δ <= k}）を指定することによ り実現できる． 制限1．ユーザが指定するパラメータδが与えられた時，式(3) を満たす． |Ot∗cur\O ∗ tcur−1| <= δ (3) ここで，O_tcur−1∗ 内でウィンドウから除かれるデータの数がδ を超える場合，制限1が満たされない．これに対応するため， 以下の制限を追加する． 制限2（制限1の例外処理）．Otcur∗ −1内でウィンドウから除 かれるデータの数をeとする．δ < eである場合，式(4)を満 たす． |O∗ tcur\O∗tcur−1| = e (4) 次に，時間に関する制限について考える．多くのアプリケー ションでは，基本的に新しいデータにより関心を示すことが 知られている[5]．oiをO∗tcur 内の最も新しいデータとすると， O∗tcur を更新する場合，oiよりも新しいデータを選択するべき である．この制限が無い場合，oiよりも古いデータが選択され る可能性があり，発生順にO∗tcur に含まれるデータが更新され る保証は無い．以下に，この制限を定義する．ここで，o.arr はデータoが発生した時刻を表す． 制限3．oをO∗_tcur−1内で最も新しいデータとする．Onew =

O∗tcur\O∗tcur−1とすると，∀o′ ∈ Onewはo′.arr > o.arrを満

たす． 制限3より，Otcur∗ に新しく含まれるデータは，o.arr後に発 生したデータのみとなる．そこで，これ以降，O (Oi)はOt∗cur に含まれる可能性があるデータの集合とする．以上の制限から， 本稿で考える問題を定義する． 定義2（(k, δ)-多様集合モニタリング問題）．k（>_{= 2}），δ，I， およびm台のデータサイトが保持している_I上のデータで制限 3を満たすものの集合Oが与えられた時，この問題は，Oの部 分集合O∗tcur を継続的に計算する．また，O ∗ tcur は式(1)–(2)， 制限1，2，および3を満たす． (k, δ)-多様集合モニタリング問題もNP困難であるため，近 似解を計算するヒューリスティックアルゴリズムが必要である． 本稿では，多様性を維持しつつ，更新時間および通信量を削減 するアルゴリズムを設計する．

3.

初期化アルゴリズム

モニタリング開始時の解を取得するため，集中管理環境に おけるアルゴリズム[9]を拡張する．このアルゴリズムはイン クリメンタルアプローチに基いており，最適解に対して，近似 値が 1 2 以上であることが保証されている．まず，Oにおいて dist(op, oq)が最大となるopとoqを検索し，途中結果を保持 Algorithm 1:INITIALIZATION 1 {o∗_p, o∗_q} ← FindInitObjects 2 R← {o∗_p, o∗_q} 3 CacheUpdate({o∗p, o∗q}) 4 while|R| < k do 5 o∗← FindNextObject 6 R← R ∪ {o∗} 7 CacheUpdate({o∗}) 8 O∗_{tcur← R} 9 return O∗_tcur Algorithm 2:FindInitObjects

1 /* procedure of a data site Si*/

2 Compute distimaxin Oiand dist(o,·) for ∀o ∈ Oi 3 O′i← ∅

4 for∀o ∈ Oido

5 if dist(o,·) >= distimaxthen 6 Oi′← O′i∪ {o} 7 Forward O_i′to Sc

8 /* procedure of Sc*/ 9 if Screceives O′ifrom Sithen 10 Oc← Oc∪ Oi′

11 count← count +1 //count is initialized at 0 12 ifcount = m then 13 {o∗p, o∗q} ← argmax op,oq ∈Oc dist(op, oq) 14 Oc← ∅ 15 count← 0 16 return{o∗_p, o∗_q} するRに格納する．その後，R中のデータとの距離が最大と なるデータの検索を|R| = kになるまで繰り返す．分散環境に おけるアルゴリズムを説明する前に，データとデータ集合間の 距離を定義する． 定義3(dist(o, O′))．データoおよびデータ集合O′が与えれた 時，dist(o, O′)は以下の式で計算される． dist(o, O′) = min o′∈O′ dist(o, o′) (5) アルゴリズム1は，データキャッシュを用いて上のアプローチ を実現するアルゴリズムを示している．まず，FindInitObjects （アルゴリズム2）を用いて，先述したopとoqを検索する．こ の操作の課題は，Siは距離の最大値を計算できない点にある． これは，∀o ∈ Oiと∃o′∈ Oj（i |= j）間の距離を計算できない ためである．一方，全てのデータをScに送信するアプローチは 通信量に問題がある．この問題を解決するため，距離の上界値 を利用する．Siは，Oiにおける距離の最大値distimax，および ∀o ∈ Oiが取り得る最大の距離dist(o,·)を計算する（アルゴリ ズム2，2行）．dist(o,·)は，Iから計算できる．例えば，2次 元のユークリッド空間において，Iは長方形である．このとき， dist(o,·)は，oと長方形のいずれかの角の距離となる．もし dist(o,·) < disti maxであれば，oは最大の距離を持つことはな

Algorithm 3:CacheUpdate()

Input: O′//a set of data object(s) newly included in O∗_tcur 1 /* procedure of Sc*/

2 Broadcast O′

3 /* procedure of a data site Si*/ 4 Ci← Ci∪ O′

Algorithm 4:FindNextObject

1 /* procedure of a data site Si*/ 2 o∗← argmax

o∈Oi dist(o, Ci) 3 Forward < o∗, dist(o∗, Ci) > to Sc 4 /* procedure of Sc*/

5 if Screceives < o∗, dist(o∗, Ci) > from Sithen 6 T← T ∪ {< o∗, dist(o∗, Ci) >} 7 count← count +1 8 if count = m then 9 o∗← argmax o∈T dist(o, R) 10 T_{← ∅} 11 count_{← 0} 12 return o∗ Scに送信する．Scは，受信したデータからopとoqを検索でき る（アルゴリズム2，13行）．その後，CacheUpdate({op, oq}) を実行する．つまり，Scは{op, oq}をブロードキャストし，各 データサイトSiは、受信したデータをキャッシュCiに保存する． 次に，FindNextObject（アルゴリズム4）を用いてインクリ メンタルにRを計算する．この操作の目的は，以下の式で得ら れるo∗を検索することである． o∗= argmax o∈O dist(o, R). (6) これを実現するため，Siはdist(o, Ci)が最大となるo∈ Oiを 検索し，Scに< o, dist(o, Ci) >を送信する．データサイトから 送信されたm個のタプルの集合をTとする．R = Ciであるた め，式(6)を満たすデータはTに含まれている．つまり，Scは， o∗= argmaxo∈Tdist(o, R)を検索できる（9行）．また，o∗は O(m)コストで計算できる．これは，Siはoと共にdist(o, Ci) を送信しているためである．その後，CacheUpdate({o∗})を実 行し，これらの操作を_{|R| = k}になるまで繰り返す． コスト分析．アルゴリズム1の空間計算量，時間計算量，および 通信量を分析する．まず，各データサイトはOtcurをキャッシュ するため，空間計算量はO(k)である．また，FindInitObjectsは 部分的に並列処理を行い（アルゴリズム2，2–7行）， FindNex-tObjectは大部分が並列処理である（アルゴリズム4，2–3行）． nfをnl= maxi∈[1,m]|Oi|とし，nfをデータサイトから送信さ れたデータの数とする．FindInitObjectsおよびFindNextObject の時間計算量は，それぞれO(n2 l+n 2 f)およびO(knl)である．つ まりアルゴリズム1の時間計算量はmax(O(n2l+ n 2 f),O(k 2 nl)) である．また，FindInitObjectsおよびFindNextObjectの通信 量は，それぞれ_O(nf)およびO(m)であるため，アルゴリズ Algorithm 5:BASELINE 1 Deletion(O′) //O′= R or O′= Ci 2 if|R| = ∅ then

3 Execute lines 1–3 of Algorithm 1 4 while_{|R| < k do} 5 o∗_{← FindNextObject} 6 R_{← R ∪ {o}∗_} 7 CacheUpdate({o∗_}) 8 O∗_tcur← R 9 return O∗_tcur Algorithm 6:Deletion() Input: O′//O′= R or O′= Ci 1 Delete expired data objects from O′ 2 δ′_{← δ − e //e is #expired data objects}

3 if δ < k then 4 while δ′> 0 do 5 o∗_{← argmin} o∈O′ dist(o, O′_\{o}) 6 O′← O′\{o∗} 7 δ′← δ′− 1 8 else 9 O′← ∅ ム1の通信量は，O(nf+ km)である．

4.

ベースラインアルゴリズム

アルゴリズム1を実行後，各時刻でO∗tcur を更新する必要が ある．本章では，O∗tcurを更新するベースラインアルゴリズムを 紹介する．tcurにおいて，Ot∗cur−1中でウィンドウから除かれ るデータの数をeとする．ベースラインアルゴリズムは，まず， f (O∗_tcur−1)への貢献が最小であるδ− e個のデータをO_tcur−1∗ から取り除く．その後，FindNextObjectを用いてO∗tcurを計算 する．もしδ = k（またはe = k）の場合，アルゴリズム1を 実行する．以下では，e < kかつδ < kの場合における操作を 説明する． アルゴリズム5にベースラインアルゴリズムのフレームワー クを示す．ベースラインアルゴリズムは，まずDeletion(·)（ア ルゴリズム6）を実行する．その後，時刻がtcurになった時， Scおよび各データサイトSiは，ウィンドウから除かれたデー タをキャッシュ（RまたはCi）から取り除く（アルゴリズム6， 1行）．次に，Scおよび各データサイトSiは，δ′(= δ− e)個 のデータを消去する．（δ′ <_{= 0}である場合，この操作は行わな い．）この操作は，f (O∗tcur−1)への貢献度合いで消去するデー タを決定する．具体的には、キャッシュ中に存在するデータの 内，距離が最小となるデータo∗を順に取り除く．これは，以 下の式で求められる． o∗= argmin o∈O′ dist(o, O ′_{\{o}) (7)} ここで，O′はRまたはCiである．o∗となるデータはキャッ シュ中に2つ存在するが，発生した時刻が前のデータを消去す

るものとする．（発生時刻が同じ場合は，データの識別子などに より消去するデータを決定する．）この操作は，Scおよびデー タサイト間で並列に行われる．δ′個のデータを消去した後，ア ルゴリズム1と同様の方法により，Ot∗curを計算する． コスト分析．ベースラインアルゴリズムの空間計算量，時間計 算量，および通信量について分析する．まず空間計算量はO(k) である．Deletion(·)の時間計算量はO(δ′_k2 )である．また，nl をローカルデータ集合の最大サイズとすると，FindNextObject の時間計算量は_O(δknl)である．そのため，ベースラインアル ゴリズムの時間計算量は_O(δknl)である．最後に，ベースライ ンアルゴリズムの通信量はO(δm).である．

5.

提案アルゴリズム

ベースラインアルゴリズムは新しいデータを取り入れながら 多様集合を計算するが，大きな問題がある．このアルゴリズム は，O∗tcur−1から必ずδ個のデータを変えているが，f (·)の値 を考慮していないため，結果として多様性を失う更新を行って しまう．提案アルゴリズムは，この点を考慮してO∗tcur の更新 を行う．5. 1節では，ケーススタディによりf (·)の向上が可能 かどうかを分析する．5. 2節では，ケーススタディの結果に基 づいてグリーディアルゴリズムを設計する． 5. 1 ケーススタディ 式 (7)を 満 た す デ ー タo∗ に つ い て 考 え る ．o∗ をR（= O∗_tcur−1）から取り除き，あるデータoをRに加えるとする． このとき，f (O∗tcur−1) < f (R)であれば，o∗とoをスワップす るべきである．図2を用いて，具体例を示す． 𝑓(𝑂_𝑡∗_{𝑐𝑢𝑟−1)} 𝑜𝑥 𝑜𝑦 図 2 f (·) を更新する o が存在する領域（影付きの空間）の例（k = 6 かつ_{I = R}2_） 例4．図2に，多様集合（4つの灰色の点および2つの黒色の 点）を示す．今，k = 6，_{I = R}2_{，および距離メトリックはユー} クリッド距離である．図中の各円の半径は，f (Ot∗cur−1)であ る．もしoxが影付きの空間に存在するデータとスワップされ た場合，f (·)が更新されることが分かる． 例4の観測から，f (O∗tcur) > f (Otcur∗ −1)となるように多様集 合を計算する．ここで，O_tcur−1∗ 中のいくつかのデータはウィ ンドウから除かれる場合がある．その場合，_{|R| = k}となるまで FindNextObjectを実行する．ox∈ Rおよびoy∈ R（ox |= oy） を式(7)を満たすデータとする．（図2で示されているように， 式(7)を満たすデータは2つ存在する．）f (R) = dist(ox, oy)で あるため，oxとoyは，スワップされるデータの候補である． そこで，以下の3つの場合について，f (·)が向上可能かどうか について考える． （1） {ox, oy} ∈ R ∩ O∗tcur−1 （2） ox∈ R ∩ O_tcur−1∗ ∧ oy∈ R ∩ O/ ∗_tcur−1 （3） _{ox, oy} /∈ R ∩ O∗tcur−1 場合（1）は，oxおよびoyがともにOt∗cur−1に含まれている 場合である．場合（2）は，oyが新たにRに含まれた場合であ り，場合（3）は，f (·)を満たすデータがともRにのみ存在す る場合である． 場合（1）．各データサイトはキャッシュを保持しているため， 並列に“f (Otcur∗ ) > f (Otcur−1∗ )”が可能かどうかを計算する． 具体的には，各データサイトSiは，以下の式を満たすo∗およ びo∗∗を計算する． o∗∗= argmax

o∈Oi dist(o, Ci\{o ∗_}) f ({o∗∗} ∪ Ci\{o∗}) > f(Ci) これを満たすデータが存在する場合，f (·)を向上できる．Si は，< o∗∗, dist(o∗∗, Ci\{o∗}) >をScに送信し，Scは受信し たデータの中から，dist(·, R\{o∗_{})が最大となるoを検索す} る．また，Scはoをブロードキャストし，各データサイトは キャッシュを更新する．つまり，o∗とoをスワップする．その 後，f (R)（= f (Ci)）がさらに向上できるかどうかを計算し， 可能な場合は先述の操作を繰り返す．向上できない場合，解の 更新を終了する．以上の操作の詳細は，5. 2節で紹介する．ま た，以上の議論により，以下の性質が示される． 性質1．場合（1）におけるスワップは，f (O∗tcur) >= f (O∗tcur−1) となることを保証する． スワップの回数の上界値はδであるが，f (·)の向上ができなく なった時点で解の更新を終了するため，計算時間を削減できる． 場合（2）．まず，この場合においてoyのスワップではf (·)を 向上できないことを示す． 定理1．FindNextObjectによって更新されたRについて考え る．また，|R| = kである．oyが新しくRに追加されたデータ であり，f (R) = dist(ox, oy)である場合，oyのスワップによ りf (·)を更新できるデータは存在しない．

証明．R′= R\{oy}とすると，oy= argmaxo∈Odist(o, R′)で

あるためである． _□

定 理 1 か ら ，f (·) を 向 上 す る た め に は ，ox を ス ワップ

す る 必 要 が あ る ．つ ま り，各 デ ー タ サ イ ト Si は ，o =

argmaxo′_∈Oidist(o′, Ci\{ox})である oを検索し，場合（1）

と同様の方法で解を更新する．この場合の操作の詳細も，5. 2

節で紹介する．場合（2）が保持する性質を以下に示す．

性質2．場合（2）では，dist(ox, oy) < f (O∗tcur−1)であれば， f (O∗tcur) >= f (Otcur−1∗ )およびf (O∗tcur) < f (Otcur∗ −1)のいず

Algorithm 7:GREEDY 1 τ← f(R)

2 Delete the expired data objects from R (or Ci) 3 case|R| = k 4 for i = 1 to δ do 5 Swap(τ ) 6 τ← f(R) 7 case|R| < k 8 δ′← δ − (k − |R|) 9 while|R| < k do 10 o∗← FindNextObject 11 R← R ∪ {o∗} 12 CacheUpdate({o∗})

13 {ox, oy} ← {o, o′} where o, o′∈ R and dist(o, o′) = f (R) 14 case ox∈ R ∩ O∗_{tcur −1}∧ oy∈ R ∩ O/ ∗_{tcur −1}

15 while δ′> 0 do 16 Swap(τ ) 17 τ← f(R) 18 δ′← δ′− 1 19 case|R| = ∅ 20 Execute Algorithm 1 21 O∗_tcur← R 22 return O∗_tcur f (O∗tcur) >= f (O ∗ tcur−1)とできる． 場合（3）．この場合は，定理1により，f (R)を向上できない． つまり，場合（3）は以下の性質を持つ．

性 質 2．dist(ox, oy) < f (Ot∗cur−1) で あ れ ば ，f (O∗tcur) < f (O∗_tcur−1)である．また，dist(ox, oy) >_{= f (O}∗_tcur−1)であれ

ば，f (Otcur∗ ) >= f (O∗tcur−1)である． 5. 2 アルゴリズム設計 前節のケーススタディに基づき，効率的に多様集合を更新す るグリーディアルゴリズムを提案する．アルゴリズム7は，提 案アルゴリズムのフレームワークを示している． まず，f (O∗_tcur−1)（= f (R)）を保存し，ウィンドウから除か れるデータを削除する（1–2行）．もしR =∅の場合，アルゴ リズム1を実行する（20行）．R |= ∅の場合，Swap(·)（アル ゴリズム8）を，場合（1）（3–6行）および場合（2）（8–17行） に応じて実行する．（2行目の操作後に_{|R| < k}ならば，9–12行 の操作を実行する．） 場合（1）および（2）の時，アルゴリズム8によりf (·)を 向上する．各データサイトSiは式(7)を満たすデータo∗を検 索する（2行）．場合（2）では，o∗はo∗∈ Otcur∗ −1も満たす． 次に，f (·)を向上できるデータを検索する（3–11行）．この操 作中，dist(o, o′) <_{= f (C}i)（o′ ∈ Ci\{o∗}）となるデータoは f (·)を向上できないため，計算を枝刈りしている（7行）．ま た，Oi中の複数のデータがf (·)を向上できる場合，以下の式 を満たすo∗∗を検索する． o∗∗= argmax

o′_∈Oi dist(o ′_{, C}

i\{o∗})

その後，Scに< o∗∗, dist(o∗∗, Ci\{o∗}) >を送信する．一方，

Algorithm 8:Swap()

Input: τ (= f (R) = f (Ci)) 1 /* procedure of a data site Si*/ 2 o∗← argmin

o∈Ci dist(o, Ci\{o}) 3 for∀o ∈ Oido

4 dist(o,·) ← ∞ 5 for∀o′∈ Ci\{o∗} do 6 if dist(o, o′) <_{= τ then} 7 Otemp← Otemp∪ {o}

8 break

9 else

10 if dist(o,·) > dist(o, o′) then 11 dist(o,·) ← dist(o, o′)

12 if|Otemp| |= |Oi| //some data objects are not pruned then 13 o∗∗← argmax

o∈Oi dist(o, Ci\{o

∗_})

14 Forward < o∗∗, dist(o∗∗, Ci\{o∗}) > to Sc 15 else

16 Forward <-,-> to Sc

17 if Sireceives o from Sc//broadcasted data for cache update (line 33) then 18 Ci← {o} ∪ Ci\{o∗} //o∗has been computed in line 2 19 /* procedure of Sc*/

20 if Screceives < o∗∗, dist(o∗, Ci) > from Sithen 21 T← T ∪ {< o∗∗, dist(o∗, Ci) >} 22 count← count +1 23 if Screceives <-,-> then 24 count← count +1 25 if count = m then 26 count← 0 27 if T |= ∅ then 28 o∗← argmin o∈R dist(o, R\{o}) 29 R← R\{o∗} 30 o∗← argmax o∈T dist(o, R) 31 R← R ∪ {o∗} 32 T← ∅

33 Broadcast o∗//for cache update 34 else 35 break Oi 中にf (·)を向上できるデータが存在しない場合，Sc に <−, − >を送信する．Tをm個のタプルの集合とすると，Sc は，m個のタプルを受信後，Tを確認する．T |= ∅である場合， f (·)を最も大きく向上できるデータをTから検索し，解を更新 する．また，スワップしたデータをブロードキャストし，デー タサイトはキャッシュを更新する（18および33行）．次に，各 データサイトSiは，f (Ci)がさらに向上可能かどうかを確認す る．これらの操作は，T =∅となるまで繰り返される（最大δ 回）． コスト分析．アルゴリズム7の空間計算量，時間計算量，およ び通信量を分析する．まず，空間計算量は_O(k)である．次に， Swap(·)の時間計算量を分析する．2行におけるo∗の検索には O(k2 )のコストが必要である．13行におけるo∗∗の最悪時間計

算量はO(knl)であり，nlはローカルデータ集合の最大サイズ である．28行の操作は2行の操作と並列して実行でき，30行 の操作は_O(m)のコストが生じる．つまり，Swap(·)の最悪時 間計算量は_O(knl)である．ここで，場合（1）ではSwap(·)は 最大δ回実行されるため，時間計算量はO(δknl)となる．ま た，場合（2）ではFindNextObjectをe回実行する（eはキャッ シュ中のウィンドウから除かれるデータの数である）．この時 間計算量は_O(eknl)である．次にSwap(·)を最大δ′（= δ− e） 実行するため，その最悪時間計算量は_O(δ′knl)である．すな わち，アルゴリズム7の最悪時間計算量はO(δknl)であり，こ れはベースラインアルゴリズムの時間計算量と同じである．最 後に，通信量は_O(δm)となる．

6.

評 価 実 験

本章では，ベースラインアルゴリズムおよびグリーディアル ゴリズムの性能評価の結果を紹介する． 6. 1 セッティング 本実験は，1Gbpsイーサネットで接続されている実分散環境で

行った．Scは，Windows 7，3.4GHz Intel Core i7，および32GB

RAMを搭載した計算機であり，データサイトは，Windows 7，

3.46GHz Intel Xeon，および16GB RAMを搭載した計算機であ

る．また，本実験ではm = 10であり，全てのアルゴリズムは

C++で実装した．

データセット．本実験では，2つの実データ（Cdad [11]およ

びStock）を使用した．Cdadは，IBM Watsonで収集された

ネット ワ ー ク デ ー タ で あ り，4つ の 属 性 値（snmpInPkts，

snmpOutPkts，ipIn，およびipOut）を用いた．Stockは，

NYSE，NASDAQ，DOW JONESなどから収集した株データで

ある．データ数はそれぞれ2,726,251および2,740,470である． 評価値．本実験では，以下の3つの値を評価した．（i）通信量： モニタリングで発生したメッセージの総バイト数．（ii）更新時 間：多様集合の更新にかかった時間の平均．（iii）f (O∗)：目的 関数（式(2)）の平均値． 6. 2 評 価 結 果 kの影響．まず，kを変えて実験を行った．図3にその結果を 示す．ここで，δ = 30およびI = Rd_{とし，距離メトリックは} ユークリッド距離とした．ウィンドウサイズは，Cdadにおける 24時間に相当するサイズを用いた． 図3(a)–3(b)から，グリーディはベースラインを大きく上回る 性能を示していることが分かる．グリーディで生じた通信量は ベースラインの10分の1以下である．また，ベースラインは 各時刻でδ× m個のデータを送信するため，その通信量はkに 依存しない．一方，グリーディはkが大きくなると通信量が増 加する．これは，kが大きい時ほど，f (·)の値を更新できる確 率が高まる，つまりSwap(·)の実行回数が増加するからである． 図3(c)–3(d)から，グリーディは更新時間もベースライン を上回っていることが分かる．ベースラインの時間計算量は O(δ′_kn l)であるため，kが大きい時に更新時間が長い．グリー ディはf (·)の値が向上できる場合にのみ更新を行う点，および 1 10 100 1000 50 100 150 200 250 300 通信量 [MB] k (Cdad) ベースライン グリーディ (a) Cdad 1 10 100 50 100 150 200 250 300 通信量 [MB] k (Stock) ベースライン グリーディ (b) Stock 0 20 40 60 80 100 120 50 100 150 200 250 300 更新時間 [m sec] k (Cdad) ベースライン グリーディ (c) Cdad 0 20 40 60 80 100 120 140 160 180 50 100 150 200 250 300 更新時間 [m sec] k (Stock) ベースライン グリーディ (d) Stock 0 10000 20000 30000 40000 50000 60000 50 100 150 200 250 300 f(O *) k (Cdad) ベースライン グリーディ (e) Cdad 0 5 10 15 20 25 50 100 150 200 250 300 f(O *) k (Stock) ベースライン グリーディ (f) Stock 図 3 k の 影 響 Swap(·)中の枝刈りから不要な計算を削減している点により， 更新時間を短くできる． 図3(e)–3(f)はf (O∗)の結果を示している．ここで，データ セット間のf (O∗)のスケールの違いは，データの属性値のス ケールによるものである．図3(e)–3(f)から，kが大きくなる と，f (O∗)は小さくなることが分かる．これは，kが大きくな ると，mino,o′_∈O∗

tcurdist(o, o ′_{)が小さくなるからである．また，} グリーディの方が基本的にf (O∗)が大きく，特にkが小さい時 にはベースラインと大きな差がある．Stockかつk >_{= 250}の場 合，ベースラインの方がf (O∗)が大きいが，その差は非常に小 さい． δの影響．次に，δを変えて実験を行った．その他のパラメー タはkの影響を調べた実験と同様であり，kは100とした． 図4(a)–4(b)から，ベースラインの通信量は線形に増加してい ることが分かる．一方，グリーディの通信量はδに依存してい ないことが分かる．これは，f (O∗)の向上ができなくなった時 に更新を終了するからであり，この結果からスワップの回数は 少ないことが分かる．更新時間の結果についても同様のことが 言える．一方，図4(c)–4(d)から，δ = k（= 100）の時，ベー スラインの更新時間が短くなっていることが分かる．δ = kの 時，アルゴリズム6の時間計算量は_O(1)となり，制限3から FindInitObjectの計算時間も短くなる． 図4(e)–4(f)から，グリーディはベースラインよりも大きい f (O∗)を維持していることが分かる．グリーディは通信量およ び更新時間の観点からもベースラインを上回る性能を示してお

1 10 100 1000 10000 10 20 30 40 50 60 70 80 90 100 通信量 [MB] delta (Cdad) ベースライン グリーディ (a) Cdad 1 10 100 1000 10 20 30 40 50 60 70 80 90 100 通信量 [MB] delta (Stock) ベースライン グリーディ (b) Stock 0 10 20 30 40 50 60 70 80 10 20 30 40 50 60 70 80 90 100 更新時間 [m sec] delta (Cdad) ベースライン グリーディ (c) Cdad 0 20 40 60 80 100 120 10 20 30 40 50 60 70 80 90 100 更新時間 [m sec] delta (Stock) ベースライン グリーディ (d) Stock 0 5000 10000 15000 20000 25000 30000 35000 40000 10 20 30 40 50 60 70 80 90 100 f(O *) delta (Cdad) ベースライン グリーディ (e) Cdad 0 2 4 6 8 10 12 10 20 30 40 50 60 70 80 90 100 f(O *) delta (Stock) ベースライン グリーディ (f) Stock 図 4 δ の 影 響 り，アルゴリズム8の有効性を確認できる．

7.

関 連 研 究

分散ストリームモニタリング．これまでに多くの研究が分散ス トリーム環境におけるモニタリング問題に取り組んでいる．例 えば，閾値モニタリング[15]，スケッチング[14]，スカイライ ンモニタリング[13]が挙げられる．1.章で述べたように，分散 ストリーム環境では通信量の削減が重要な要件であるため，こ れらの研究では集中管理サーバとデータサイト間の通信を削減 するアルゴリズムを提案している．しかし，モニタリングの対 象となるデータが異なる点，および多様性を考慮していない点 から，既存のアルゴリズムを本問題に適用することはできない． 検索結果の多様化．文献[3]によると，多様化問題は大きく3つ のカテゴリ（新規性，トピックカバレッジ，およびコンテンツ） に分類される．“新規性”を考慮した場合，前回計算された結果 に対して，新しい情報を追加するように結果を更新する．“ト ピックカバレッジ”では，検索結果に含まれるトピック（ジャ ンル）の数を最大にするように結果を計算する．“コンテンツ” では，互いに異なるデータを検索結果に含めるように計算する． 本問題は，コンテンツを考慮した多様化に焦点を当てている． コンテンツを考慮した多様化について，動的データに対する 多様化問題を扱う既存研究が存在する[2]，[5]．しかし，これら は集中管理環境を想定しており，本問題に適用できない．また， 分散環境における多様化問題に取り組んだ既存研究も存在す る[10]，[16]．しかし，これらは静的データのみを対象としてお り，動的データに対しては再計算が必要となるため，本問題へ の効率的な解法にはなり得ない．

8.

お わ り に

分散ストリーム環境を想定したアプリケーションの増加，お よび多様化された結果の有用性の背景から，分散ストリーム環 境におけるk-多様集合モニタリング問題に取り組んだ．本稿で は，空間計算量，時間計算量，および通信量が効率的な，キャッ シュを利用する近似アルゴリズムを提案した．実分散環境での 実験から，提案アルゴリズムの有効性を示した． 本稿では，MAXMIN関数のみに着目したが，提案アルゴリ ズムの適用先をさらに広げるため，多くの目的関数を利用でき るように拡張することが今後の課題として挙げられる． 謝辞．本研究の一部は，文部科学省科学研究費補助金・基盤研究 (A)(26240013)およびJST国際科学技術共同研究推進事業（戦 略的国際共同研究プログラム）の研究助成によるものである． ここに記して謝意を表す． 文 献

[1] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In PODS, pages 1–16, 2002. [2] A. Borodin, H. C. Lee, and Y. Ye. Max-sum diversification,

mono-tone submodular functions and dynamic updates. In PODS, pages 155–166, 2012.

[3] M. Drosou and E. Pitoura. Search result diversification. SIGMOD

Record, 39(1):41–47, 2010.

[4] M. Drosou and E. Pitoura. Dynamic diversification of continuous data. In EDBT, pages 216–227, 2012.

[5] M. Drosou and E. Pitoura. Diverse set selection over dynamic data.

IEEE TKDE, 26(5):1102–1116, 2014.

[6] E. Erkut. The discrete p-dispersion problem. European Journal of

Operational Research, Elsevier, 46(1):48–60, 1990.

[7] M. Ghashami, J. M. Phillips, and F. Li. Continuous matrix approxi-mation on distributed data. PVLDB, 7(10):809–820, 2014. [8] N. Giatrakos, A. Deligiannakis, M. Garofalakis, I. Sharfman, and

A. Schuster. Distributed geometric query monitoring using predic-tion models. ACM TODS, 39(2):16, 2014.

[9] S. Gollapudi and A. Sharma. An axiomatic approach for result diver-sification. In WWW, pages 381–390, 2009.

[10] M. Hasan, A. Mueen, and V. Tsotras. Distributed diversification of large datasets. In IC2E, pages 67–76, 2014.

[11] A. Lazerson, I. Sharfman, D. Keren, A. Schuster, M. Garofalakis, and V. Samoladas. Monitoring distributed streams using convex de-compositions. PVLDB, 8(5):545–556, 2015.

[12] E. Minack, W. Siberski, and W. Nejdl. Incremental diversification for very large sets: a streaming-based approach. In SIGIR, pages 585–594, 2011.

[13] O. Papapetrou and M. Garofalakis. Continuous fragmented skylines over distributed streams. In ICDE, pages 124–135, 2014.

[14] O. Papapetrou, M. Garofalakis, and A. Deligiannakis. Sketching dis-tributed sliding-window data streams. The VLDB Journal, pages 1– 24, 2015.

[15] I. Sharfman, A. Schuster, and D. Keren. A geometric approach to monitoring threshold functions over distributed data streams. ACM

TODS, 32(4):23, 2007.

[16] G. Tsatsanifos, D. Sacharidis, and T. Sellis. Ripple: A scalable framework for distributed processing of rank queries. In EDBT, pages 259–270, 2014.