DEIM Forum 2016 A7-1

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

原隆浩†† 大阪大学大学院情報科学研究科 〒 565-0871 大阪府吹田市山田丘 1-5
E-mail: †{amagata.daichi,hara}@ist.osaka-u.ac.jp
あらまし分散ストリーム環境におけるデータモニタリングは，センサネットワーク等のアプリケーションに代表されるように，基礎的な問題である．この問題を扱うアプリケーションは，時間計算量や空間計算量だけでなく，通信量も効率的な技術を必要とする．また，検索結果の多様化は，結果から得られる情報量を増加し，ユーザの満足度を向上させる手段として，近年多くの注目を集めている．そこで本稿では，分散ストリーム環境において，多様性を考慮しながら k 個のデータをモニタリングする問題に取り組む．この問題には，NP 困難およびデータ集合の動的な変化という 2 つの課題がある．提案アルゴリズムは，これらの課題に対して，近似解をモニタリングすることにより，データ集合の更新が頻繁に起きる場合にも効率的に解を更新する．実データを用いた実験から，提案アルゴリズムは通信量を抑制し，多様性を保持しながらリアルタイムモニタリングを実現できることを確認した．
キーワード

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

1. は じ め にすると，本稿では，ユーザが指定した範囲内に存在し，現在時
刻（tcur ）からウィンドウズサイズ以内に発生したデータの集

近年，ローカルストリームを受信する複数のデータサイトか合の内，M AX M IN となる k 個のデータ集合をモニタリングのら構成される分散ストリーム環境を想定するアプリケーション

対象とする．この問題は，例 1 および例 2 に示すように多くのが多く存在する．例えば，IP ネットワークモニタリング [14]，アプリケーションが存在するにも関わらず，これまでに着手さ

センサネットワーク [7]，および財務データモニタリング [8] なれていない．

どが挙げられる．ストリーム環境では，アドホックな検索では

例 1．スライディングウィンドウを用いる代表例である IP ネッ

なく，継続的なデータのモニタリングが必要である．先述した

トワークモニタリングについて考える [14]．ネットワーク管理

アプリケーションでは，DDoS 攻撃を検出するため [14] や環境者は，追跡可能なデータサイズ（k ）および懸念しているデー

モニタリングを行うため [7] に，データサイトから必要なデー

タ領域（RoI）を指定し，k 個のネットワークデータをモニタリタを取得し，それらを要求に応じて更新する必要がある．これングする．モニタリングされているデータ集合が多様化されてを効率的に実現するため，分散ストリーム環境におけるデータ

いる場合，あるデータは他のデータと互いに類似していないた

モニタリングアルゴリズムがこれまでに提案されている [13]．

め，異常データが含まれていることが多いと考えられる．つま1. 1 研 究 動 機
データベースや情報検索の分野では，検索結果の多様化に多くの注目が集まっている [3]．多様化されたデータ集合を Oとすると，あるデータ o ∈ O は，別のデータ o′ ∈ O との類似度が低く，分布に偏りがあるデータ集合よりも情報量が多いと考えられている．本稿では，分散ストリーム環境において，

O のようなデータ集合を継続的にモニタリングする問題に取り組む．具体的には，スライディングウィンドウを用いてスト
リームデータを管理し，多様性を考慮しながら k 個のデータをモニタリングする．この多様性を考えるにあたり，本稿では，

M AX M IN 関数 [9] を用いる．これは，あるデータ集合から k 個のデータを抽出する際，その k 個のデータ間の距離の最小値を最大とするものである．ここで，動的データは時間と関連する属性を保持しており，多くのアプリケーションでは現在時刻の直近に発生したデータのみを対象とすることが一般的である [14]．そのため，本稿では，時間に基づくスライディングウィ
ンドウ [1] を想定する．さらに，ユーザは，ある範囲（価格帯やセンサ値）に含まれるデータのみを対象とすることも多いため，region of interest (RoI) を指定できることが望ましい．要約り，このアプローチは，異常検出を容易に実現できる．
例 2．複数のデータサイト（データソース）から構成される株
市場分析システムについて考える．あるユーザは，価格や株数などの範囲を指定し，その範囲内に存在するデータを俯瞰することが考えられる．しかし，該当する株データは大量に存在することが予想され [8]，全てのデータを追跡し続けることは非現実的である．そのため，k 個の多様化された株データに絞り込
むことにより，モニタリングする情報量を大きく損なうことなく，ユーザは指定した範囲内のデータを俯瞰できる．

1. 2 課題

本稿で取り組む問題に対する効率的な解法を設計するため，
以下の課題について考える必要がある．

• 空間計算量，時間計算量，および通信量の効率化．分散ストリーム環境では，空間計算量および時間計算量に加えて，通信量の削減も求められる [8]，[14]. メモリ使用量（空間計算量）は，ストリーム（ウィンドウ）サイズに対して線形であることが基
本的な要件として考えられている．時間計算量は，リアルタイ
ムモニタリングを実現するための重要な要素である．また，通信量の削減は，ネットワーク帯域の有効活用に代表されるように，分散環境において重要な要件である．つまり，全てのデー
タを送信する必要がある集中管理方法は，分散ストリーム環境

4において不適切であり，既存のアルゴリズム [4]，[5] は，本問題3の効率的な解法にはなり得ない．

• NP 困難問題. M AX M IN 問題は，NP 困難であることが知られ𝑜4が要求される．つまり，多様性を保持しつつ，リアルタイムかつ通信量を抑制できるアルゴリズムを設計する必要がある．
提案アルゴリズムの概要．本稿で提案するアルゴリズムは，サイズが O(k) のみのキャッシュを利用している．各データサイ
トが k 個のモニタリングデータをキャッシュすることにより，あるデータが発生または消滅した際の解の更新を並列計算できる．また，既存の研究では，多様性が最も増加するデータを計算し，インクリメンタルに k 個のデータを選出するアプロー
チ [9]，または最初にランダムに k 個のデータを選出し，多様性を向上できる場合にスワップを繰り返すアプローチが用いられている [12]．提案アルゴリズムは，これらのアプローチを統合し，より多様化されたデータ集合をモニタリングする．先述
したように，このアプローチは並列に実行されるため，更新時間を短縮することができ，通信量はデータサイト数に比例する結果となる．

1. 3 貢献と構成
以下に，本研究の貢献を示す．(i) 本稿では，分散ストリーム

𝑜4

4

𝑂*

3

𝑂*
2

2

1

1

𝑜1 𝑜2 𝑜3ている [6]．そのため，最適解をリアルタイムに計算することは非現実的であり，近似解を計算するヒューリスティックな解法

𝑜5

5

5

0

𝑜1 𝑜2 𝑜3

0

0

1

2

3

4

5

0

(a) tcur − 1 における O

1

2

3

4

5

(b) tcur における O

図 1 k = 2 かつ I = R2 において，Ot∗cur \Ot∗cur −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）モニタ
リング問題を定義する．
d
定義 1（k-多様集合モニタリング問題）．k（>= 2），RoI（I ∈ R ），環境における多様性を考慮したデータモニタリング問題に取および m 台のデータサイトが保持している I 上のデータの集

り組む（2. 章）．筆者らの知る限り，この問題はこれまでに取合 O が与えられた時，この問題は，O の部分集合 Ot∗cur を継り組まれていない．(ii) まず，集中管理環境における M AX M IN
問題に対するアルゴリズムを，分散環境に適用できるように拡張する．これにより，モニタリングの初期化を実現できる（3.
章）．(iii) 次に，インクリメンタルアプローチを用いたベース
ラインアルゴリズムを設計する（4. 章）．(iv) さらに，インク続的に計算する．また，Ot∗cur は式 (1)–(2) を満たす．

Ot∗cur =f (O′ ) =O′

argmax f (O′ )⊂O, |O′ |=k=minoi ,oj ∈O ′ , oi =o| jdist(oi , oj )

(1)
(2)

リメンタルアプローチおよびスワップアプローチを統合し，よ

この問題は，M AX M IN 問題であるが，多様化のための関数とり多様化が可能となるグリーディアルゴリズムを提案する．提して，k 個のデータ間の距離の和を最大にする M AX S UM 問題

案アルゴリズムは，ベースラインアルゴリズムに対して，更新も存在する [2]．しかし，M AX S UM 関数は，k-多様集合の分布

時間および通信量を削減する（5. 章）．(v) 複数の計算機を用いを偏らせてしまうことが知られている [5]．そのため，本稿ではた実分散環境において提案アルゴリズムを評価する．実データ

M AX M IN 問題に焦点を当てる．

を用いた実験により，提案アルゴリズムの有効性およびスケー
ラビリティを確認する（6. 章）．また，7. 章において関連研究について議論し，8. 章で本稿をまとめる．

2. 予 備 知 識
本章では，まず，想定環境を説明し，本稿で取り組む問題を定義する．

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

要件の補足．モニタリングを必要とするアプリケーションでは，連続した時間における k 個のデータの集合には共通したデータが存在することを想定している [5]．これを実現するため，2 つの制限を設ける．
まず，“差分の制限” を設ける．これは，|Ot∗cur \Ot∗cur −1 | の値を制限するものである．k-多様集合モニタリング問題では，O が変わると（ウィンドウがスライドすると）Ot∗cur ∩ Ot∗cur −1 = ∅となる可能性がある．そのため，差分の制限が必要となる．
例 3．図 1 に表される 2 次元のユークリッド空間を考える．デー
タ o1 ，o2 ，o3 ，および o4 は tcur −1 に発生し，o5 は tcur に発生したとする．k = 2 および I = R2 とすると，Ot∗cur −1 = {o1 , o4 }であり，Ot∗cur = {o3 , o5 } である．

例 3 から，O の変化が小さい場合でも，Ot∗cur が大きく変化する場合があることがわかる．これが頻繁に起こる場合，k-多様集合の変化を追跡することは困難である．そのため，Ot∗cur に含まれるデータの内いくつかは，スライディングウィンドウ上に存在する限り k-多様集合に残り続けることが望ましい [5]．これは，ユーザがパラメータ δ（1 <=δ<= k）を指定することにより実現できる．

Algorithm 1: I NITIALIZATION1∗{o∗p , oq } ← FindInitObjects

2∗
R ← {o∗p , oq }3∗
CacheUpdate({o∗p , oq })4

while |R| < k do

5o∗ ← FindNextObject

6

R ← R ∪ {o∗ }7CacheUpdate({o∗ })制限 1．ユーザが指定するパラメータ δ が与えられた時，式 (3)

8

を満たす．

9

|Ot∗cur \Ot∗cur −1 | <=δreturn Ot∗cur(3)
Algorithm 2: FindInitObjects

ここで，Ot∗cur −1 内でウィンドウから除かれるデータの数が δを超える場合，制限 1 が満たされない．これに対応するため，
以下の制限を追加する．
制限 2（制限 1 の例外処理）．Ot∗cur −1 内でウィンドウから除かれるデータの数を e とする．δ < e である場合，式 (4) を満

1/* procedure of a data site Si */2

Compute distimax in Oi and dist(o, ·) for ∀o ∈ Oi

3Oi′ ← ∅

4for ∀o ∈ Oi do

5
6

たす．

|Ot∗cur \Ot∗cur −1 | = eOt∗cur ← R(4)i
if dist(o, ·) >= distmax thenOi′ ← Oi′ ∪ {o}7Forward Oi′ to Sc

8

次に，時間に関する制限について考える．多くのアプリケー/* procedure of Sc */9

if Sc receives Oi′ from Si then

ションでは，基本的に新しいデータにより関心を示すことが10

Oc ← Oc ∪ Oi′

知られている [5]．oi を Ot∗cur 内の最も新しいデータとすると，

11

count ← count +1 //count is initialized at 0

Ot∗cur を更新する場合，oi よりも新しいデータを選択するべき12

if count = m then

13

∗
{o∗
p , oq } ← argmax dist(op , oq )14

Oc ← ∅

15

count ← 0

16∗
return {o∗p , oq }op ,oq ∈Oc

である．この制限が無い場合，oi よりも古いデータが選択される可能性があり，発生順に Ot∗cur に含まれるデータが更新される保証は無い．以下に，この制限を定義する．ここで，o.arr
はデータ o が発生した時刻を表す．
制限 3．o を Ot∗cur −1 内で最も新しいデータとする．Onew =Ot∗cur \Ot∗cur −1 とすると，∀o′ ∈ Onew は o′ .arr > o.arr を満する R に格納する．その後，R 中のデータとの距離が最大とたす．

なるデータの検索を |R| = k になるまで繰り返す．分散環境に

制限 3 より，Ot∗cur に新しく含まれるデータは，o.arr 後に発おけるアルゴリズムを説明する前に，データとデータ集合間の生したデータのみとなる．そこで，これ以降，O (Oi ) は Ot∗cur

距離を定義する．

に含まれる可能性があるデータの集合とする．以上の制限から，

定義 3 (dist(o, O ′ ))．データ o およびデータ集合 O′ が与えれた

本稿で考える問題を定義する．

時，dist(o, O ′ ) は以下の式で計算される．

定義 2（(k, δ)-多様集合モニタリング問題）．k （>= 2），δ ，I，
および m 台のデータサイトが保持している I 上のデータで制限

dist(o, O′ ) = mindist(o, o′ )
′
′
o ∈O

(5)

3 を満たすものの集合 O が与えられた時，この問題は，O の部

アルゴリズム 1 は，データキャッシュを用いて上のアプローチ

分集合 Ot∗cur を継続的に計算する．また，Ot∗cur は式 (1)–(2)，を実現するアルゴリズムを示している．まず，FindInitObjects

制限 1，2，および 3 を満たす．

（アルゴリズム 2）を用いて，先述した op と oq を検索する．こ(k, δ)-多様集合モニタリング問題も NP 困難であるため，近の操作の課題は，Si は距離の最大値を計算できない点にある．

似解を計算するヒューリスティックアルゴリズムが必要である．

これは，∀o ∈ Oi と ∃o′ ∈ Oj （i =| j ）間の距離を計算できない

本稿では，多様性を維持しつつ，更新時間および通信量を削減ためである．一方，全てのデータを Sc に送信するアプローチはするアルゴリズムを設計する．

通信量に問題がある．この問題を解決するため，距離の上界値

3. 初期化アルゴリズムを利用する．Si は，Oi における距離の最大値 distimax ，および∀o ∈ Oi が取り得る最大の距離 dist(o, ·) を計算する（アルゴリ

モニタリング開始時の解を取得するため，集中管理環境に

ズム 2，2 行）．dist(o, ·) は，I から計算できる．例えば，2 次

おけるアルゴリズム [9] を拡張する．このアルゴリズムはイン元のユークリッド空間において，I は長方形である．このとき，クリメンタルアプローチに基いており，最適解に対して，近似

dist(o, ·) は，o と長方形のいずれかの角の距離となる．もし

値が 12 以上であることが保証されている．まず，O においてdist(o, ·) < distimax であれば，o は最大の距離を持つことはな> distimax を満たすデータ o の集合をい．そのため，dist(o, ·) =dist(op , oq ) が最大となる op と oq を検索し，途中結果を保持

Algorithm 5: BASELINE

Algorithm 3: CacheUpdate()′//a set of data object(s) newly included in Ot∗cur

1Deletion(O ′ ) //O ′ = R or O ′ = Ci

1/* procedure of Sc */2

Broadcast O ′if |R| = ∅ then

2

3

3

/* procedure of a data site Si */44

Ci ← Ci ∪ O ′5o∗ ← FindNextObject

6

R ← R ∪ {o∗ }7CacheUpdate({o∗ })Input: O

Algorithm 4: FindNextObject
1/* procedure of a data site Si */2o∗ ← argmax dist(o, Ci )3

Forward < o∗ , dist(o∗ , Ci ) > to Sc

4/* procedure of Sc */5

if Sc receives < o∗ , dist(o∗ , Ci ) > from Si then89

Execute lines 1–3 of Algorithm 1
while |R| < k do

Ot∗cur ← R

return Ot∗curo ∈Oi

Algorithm 6: Deletion()
Input: O ′ //O ′ = R or O ′ = Ci
1

Delete expired data objects from O ′6

T ← T ∪ {< o∗ , dist(o∗ , Ci ) >}2

δ ′ ← δ − e //e is #expired data objects

7

count ← count +1

3

if δ < k then8

if count = m then4∗

while δ ′ > 0 doo ← argmax dist(o, R)

5o∗ ← argmin dist(o, O ′ \{o})

10

T ←∅

6

O ′ ← O ′ \{o∗ }11count ← 07

δ′ ← δ′ − 1

9

o ∈T

12

o ∈O ′∗

return o89else
O′ ← ∅

Sc に送信する．Sc は，受信したデータから op と oq を検索できる（アルゴリズム 2，13 行）．その後，CacheUpdate({op , oq })を実行する．つまり，Sc は {op , oq } をブロードキャストし，各
データサイト Si は、受信したデータをキャッシュCi に保存する．

ム 1 の通信量は，O(nf + km) である．

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

次に，FindNextObject（アルゴリズム 4）を用いてインクリ

アルゴリズム 1 を実行後，各時刻で Ot∗cur を更新する必要がメンタルに R を計算する．この操作の目的は，以下の式で得らある．本章では，Ot∗cur を更新するベースラインアルゴリズムをれる o∗ を検索することである．

紹介する．tcur において，Ot∗cur −1 中でウィンドウから除かれo∗ = argmax dist(o, R).

るデータの数を e とする．ベースラインアルゴリズムは，まず，

(6)

o∈O

これを実現するため，Si は dist(o, Ci ) が最大となる o ∈ Oi を検索し，Sc に < o, dist(o, Ci ) > を送信する．データサイトから送信された m 個のタプルの集合を T とする．R = Ci であるため，式 (6) を満たすデータは T に含まれている．つまり，Sc は，o∗ = argmaxo∈T dist(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 をデータサイトから送信さf (Ot∗cur −1 ) への貢献が最小である δ − e 個のデータを Ot∗cur −1
から取り除く．その後，FindNextObject を用いて Ot∗cur を計算する．もし δ = k （または e = k ）の場合，アルゴリズム 1 を実行する．以下では，e < k かつ δ < k の場合における操作を説明する．
アルゴリズム 5 にベースラインアルゴリズムのフレームワー
クを示す．ベースラインアルゴリズムは，まず Deletion(·)（アルゴリズム 6）を実行する．その後，時刻が tcur になった時，

Sc および各データサイト Si は，ウィンドウから除かれたデー
タをキャッシュ（R または Ci ）から取り除く（アルゴリズム 6，1 行）．次に，Sc および各データサイト Si は，δ ′ (= δ − e) 個のデータを消去する．
（δ ′ <= 0 である場合，この操作は行わな
い．
）この操作は，f (Ot∗cur −1 ) への貢献度合いで消去するデー
タを決定する．具体的には、キャッシュ中に存在するデータの内，距離が最小となるデータ o∗ を順に取り除く．これは，以下の式で求められる．

れたデータの数とする．FindInitObjects および FindNextObjectの時間計算量は，それぞれ O(n2l +n2f ) および O(knl ) である．つまりアルゴリズム 1 の時間計算量は max(O(n2l + n2f ), O(k 2 nl ))o∗ = argmin dist(o, O′ \{o})
o∈O ′

(7)

である．また，FindInitObjects および FindNextObject の通信

ここで，O′ は R または Ci である．o∗ となるデータはキャッ

量は，それぞれ O(nf ) および O(m) であるため，アルゴリズ

シュ中に 2 つ存在するが，発生した時刻が前のデータを消去す

るものとする．
（発生時刻が同じ場合は，データの識別子などにを式 (7) を満たすデータとする．
（図 2 で示されているように，より消去するデータを決定する．
）この操作は，Sc およびデー

式 (7) を満たすデータは 2 つ存在する．
）f (R) = dist(ox , oy ) で

タサイト間で並列に行われる．δ ′ 個のデータを消去した後，アあるため，ox と oy は，スワップされるデータの候補である．

ルゴリズム 1 と同様の方法により，Ot∗cur を計算する．

そこで，以下の 3 つの場合について，f (·) が向上可能かどうか

コスト分析．ベースラインアルゴリズムの空間計算量，時間計について考える．

算量，および通信量について分析する．まず空間計算量は O(k)（ 1 ） {ox , oy } ∈ R ∩ Ot∗cur −1

である．Deletion(·) の時間計算量は O(δ ′ k 2 ) である．また，nl（ 2 ） ox ∈ R ∩ Ot∗cur −1 ∧ oy ∈/ R ∩ Ot∗cur −1

をローカルデータ集合の最大サイズとすると，FindNextObject（ 3 ） {ox , oy } ∈/ R ∩ Ot∗cur −1の時間計算量は O(δknl ) である．そのため，ベースラインアル場合（1）は，ox および oy がともに Ot∗cur −1 に含まれている

ゴリズムの時間計算量は O(δknl ) である．最後に，ベースライ場合である．場合（2）は，oy が新たに R に含まれた場合であンアルゴリズムの通信量は O(δm). である．

り，場合（3）は，f (·) を満たすデータがとも R にのみ存在す
る場合である．

5. 提案アルゴリズム

場合（1）．各データサイトはキャッシュを保持しているため，

ベースラインアルゴリズムは新しいデータを取り入れながら並列に “f (Ot∗cur ) > f (Ot∗cur −1 )” が可能かどうかを計算する．

多様集合を計算するが，大きな問題がある．このアルゴリズム

具体的には，各データサイト Si は，以下の式を満たす o∗ およは，Ot∗cur −1 から必ず δ 個のデータを変えているが，f (·) の値

び o∗∗ を計算する．

を考慮していないため，結果として多様性を失う更新を行ってしまう．提案アルゴリズムは，この点を考慮して Ot∗cur の更新

o∗∗ = argmax dist(o, Ci \{o∗ })
o ∈Oi

∗∗

f ({o } ∪ Ci \{o∗ }) > f (Ci )を行う．5. 1 節では，ケーススタディにより f (·) の向上が可能かどうかを分析する．5. 2 節では，ケーススタディの結果に基づいてグリーディアルゴリズムを設計する．

5. 1 ケーススタディ
式 (7) を 満 た す デ ー タ o∗ に つ い て 考 え る ．o∗ を R（=

Ot∗cur −1 ）から取り除き，あるデータ o を R に加えるとする．
このとき，f (Ot∗cur −1 ) < f (R) であれば，o∗ と o をスワップするべきである．図 2 を用いて，具体例を示す．

これを満たすデータが存在する場合，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 (Ot∗cur ) >= f (Otcur −1 )となることを保証する．

𝑜𝑥𝑜𝑦𝑓(𝑂𝑡∗𝑐𝑢𝑟 −1 )スワップの回数の上界値は δ であるが，f (·) の向上ができなくなった時点で解の更新を終了するため，計算時間を削減できる．
場合（2）．まず，この場合において oy のスワップでは f (·) を向上できないことを示す．
定理 1．FindNextObject によって更新された R について考える．また，|R| = k である．oy が新しく R に追加されたデータ

図 2 f (·) を更新する o が存在する領域（影付きの空間）の例（k = 6
かつ I = R2 ）例 4．図 2 に，多様集合（4 つの灰色の点および 2 つの黒色の点）を示す．今，k = 6，I = R2 ，および距離メトリックはユー
クリッド距離である．図中の各円の半径は，f (Ot∗cur −1 ) である．もし ox が影付きの空間に存在するデータとスワップされであり，f (R) = dist(ox , oy ) である場合，oy のスワップにより f (·) を更新できるデータは存在しない．
証明．R′ = R\{oy } とすると，oy = argmaxo∈O dist(o, R′ ) であるためである．

□

定 理 1 か ら ，f (·) を 向 上 す る た め に は ，ox を ス ワップ
す る 必 要 が あ る ．つ ま り，各 デ ー タ サ イ ト Si は ，o =た場合，f (·) が更新されることが分かる．

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

例 4 の観測から，f (Ot∗cur ) > f (Ot∗cur −1 ) となるように多様集

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

合を計算する．ここで，Ot∗cur −1 中のいくつかのデータはウィンドウから除かれる場合がある．その場合，|R| = k となるまで

FindNextObject を実行する．ox ∈ R および oy ∈ R（ox =| oy ）と同様の方法で解を更新する．この場合の操作の詳細も，5. 2
性質 2．場合（2）では，dist(ox , oy ) < f (Ot∗cur −1 ) であれば，∗∗∗f (Ot∗cur ) >= f (Otcur −1 ) および f (Otcur ) < f (Otcur −1 ) のいず∗れも起こり得る．一方，dist(ox , oy ) >= f (Otcur −1 ) であれば，

Algorithm 7: G REEDY
1

Algorithm 8: Swap()
Input: τ (= f (R) = f (Ci ))τ ← f (R)/* procedure of a data site Si */2

Delete the expired data objects from R (or Ci )1

3case |R| = k2o∗ ← argmin dist(o, Ci \{o})3for ∀o ∈ Oi do

4

o ∈Ci

for i = 1 to δ do5

Swap(τ )6τ ← f (R)7case |R| < k6

δ ′ ← δ − (k − |R|)7

9

while |R| < k do

810o∗ ← FindNextObject

911

R ← R ∪ {o∗ }10∗CacheUpdate({o }){ox , oy } ← {o, o′ } where o, o′ ∈ R and dist(o, o′ ) = f (R)14case ox ∈ R ∩ Ot∗cur −1 ∧ oy ∈/ R ∩ Ot∗cur −1

15while δ ′ > 0 do

16

Swap(τ )

break
else
if dist(o, ·) > dist(o, o′ ) thendist(o, ·) ← dist(o, o′ )12

if |Otemp | =| |Oi | //some data objects are not pruned then13o∗∗ ← argmax dist(o, Ci \{o∗ })14

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

o ∈Oi

17

τ ← f (R)18

δ′ ← δ′ − 1

15
16

20

Otemp ← Otemp ∪ {o}

11

13

19

for ∀o′ ∈ Ci \{o∗ } do
if dist(o, o′ ) <= τ then5812

dist(o, ·) ← ∞4case |R| = ∅17

Execute Algorithm 1

18

∗
21 Ot
←R
cur
∗
22 return Ot
cur∗f (Ot∗cur ) >= f (Otcur −1 ) とできる．

if Si receives o from Sc //broadcasted data for cache update (line 33) thenCi ← {o} ∪ Ci \{o∗ } //o∗ has been computed in line 2/* procedure of Sc */20

if Sc receives < o∗∗ , dist(o∗ , Ci ) > from Si then21

T ← T ∪ {< o∗∗ , dist(o∗ , Ci ) >}22

count ← count +1

23
24

つまり，場合（3）は以下の性質を持つ．

25∗
f (Ot∗cur −1 ) である．また，dist(ox , oy ) >= f (Otcur −1 ) であれ∗
ば，f (Ot∗cur ) >= f (Otcur −1 ) である．

Forward <-,-> to Sc

19

場合（3）．この場合は，定理 1 により，f (R) を向上できない．
性 質 2．dist(ox , oy ) < f (Ot∗cur −1 ) で あ れ ば ，f (Ot∗cur ) <else

if Sc receives <-,-> thencount ← count +1
if count = m then26

count ← 0

27

if T =| ∅ then28o∗ ← argmin dist(o, R\{o})29

R ← R\{o∗ }30o∗ ← argmax dist(o, R)

31

るグリーディアルゴリズムを提案する．アルゴリズム 7 は，提R ← R ∪ {o∗ }

32

T ←∅

案アルゴリズムのフレームワークを示している．

33

Broadcast o∗ //for cache update

5. 2 アルゴリズム設計

o ∈R

o ∈T

前節のケーススタディに基づき，効率的に多様集合を更新す

まず，f (Ot∗cur −1 )（= f (R)）を保存し，ウィンドウから除かれるデータを削除する（1–2 行）．もし R = ∅ の場合，アルゴ

34

else

35

break

リズム 1 を実行する（20 行）．R =| ∅ の場合，Swap(·)（アルゴリズム 8）を，場合（1）（3–6 行）および場合（2）（8–17 行）に応じて実行する．
（2 行目の操作後に |R| < k ならば，9–12 行の操作を実行する．
）
場合（1）および（2）の時，アルゴリズム 8 により f (·) をOi 中に f (·) を向上できるデータが存在しない場合，Sc に< −, − > を送信する．T を m 個のタプルの集合とすると，Scは，m 個のタプルを受信後，T を確認する．T =| ∅ である場合，向上する．各データサイト Si は式 (7) を満たすデータ o を検

f (·) を最も大きく向上できるデータを T から検索し，解を更新索する（2 行）．場合（2）では，o∗ は o∗ ∈ Ot∗cur −1 も満たす．

する．また，スワップしたデータをブロードキャストし，デー∗

次に，f (·) を向上できるデータを検索する（3–11 行）．この操′′∗

作中，dist(o, o ) <= f (Ci )（o ∈ Ci \{o }）となるデータ o は

f (·) を向上できないため，計算を枝刈りしている（7 行）．また，Oi 中の複数のデータが f (·) を向上できる場合，以下の式を満たす o∗∗ を検索する．

o∗∗ = argmax dist(o′ , Ci \{o∗ })o′ ∈Oi

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

タサイトはキャッシュを更新する（18 および 33 行）．次に，各データサイト Si は，f (Ci ) がさらに向上可能かどうかを確認する．これらの操作は，T = ∅ となるまで繰り返される（最大 δ回）．
コスト分析．アルゴリズム 7 の空間計算量，時間計算量，および通信量を分析する．まず，空間計算量は O(k) である．次に，Swap(·) の時間計算量を分析する．2 行における o∗ の検索にはO(k2 ) のコストが必要である．13 行における o∗∗ の最悪時間計

算量は O(knl ) であり，nl はローカルデータ集合の最大サイズ

最大 δ 回実行されるため，時間計算量は O(δknl ) となる．ま通信量 [MB]

間計算量は O(knl ) である．ここで，場合（1）では Swap(·) は

100

100

10

ベースライン
100

シュ中のウィンドウから除かれるデータの数である）．この時間計算量は O(eknl ) である．次に Swap(·) を最大 δ ′（= δ − e）

れはベースラインアルゴリズムの時間計算量と同じである．最後に，通信量は O(δm) となる．

50

100

150

グリーディ
200

k (Cdad)k (Stock)(a) Cdad(b) Stock

160

グリーディ

140

80
60
40

300

250

300

ベースライン
グリーディ

120

100
80
60
40
20

0
50

100

150

200

250

300

50

100

150

200

k (Cdad)k (Stock)(c) Cdad(d) Stock

60000

25

ベースライン
50000

ベースライン
20

グリーディ

f(O*)

40000

f(O*)

250

180

0

6. 1 セッティング

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

300

20

ゴリズムの性能評価の結果を紹介する．

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

250

ベースライン

本章では，ベースラインアルゴリズムおよびグリーディアル

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

200

100

6. 評 価 実 験

本実験は，1Gbps イーサネットで接続されている実分散環境で

150

120

更新時間 [msec]

わち，アルゴリズム 7 の最悪時間計算量は O(δknl ) であり，こベースライン
1

50

実行するため，その最悪時間計算量は O(δ ′ knl ) である．すな

10

グリーディ

1

た，場合（2）では FindNextObject を e 回実行する（e はキャッ

更新時間 [msec]の操作は O(m) のコストが生じる．つまり，Swap(·) の最悪時

通信量 [MB]である．28 行の操作は 2 行の操作と並列して実行でき，30 行

1000

30000
20000

グリーディ

15
10
5

10000
0

0
50

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

C++で実装した．

100

150

200

250

300

50

100

150

200

k (Cdad)k (Stock)(e) Cdad(f) Stock

図3

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

250

300

k の 影 響び Stock）を使用した．Cdad は，IBM Watson で収集された
ネット ワ ー ク デ ー タ で あ り，4 つ の 属 性 値（snmpInPkts，

Swap(·) 中の枝刈りから不要な計算を削減している点により，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(δ ′ knl ) であるため，k が大きい時に更新時間が長い．グリー
ディは f (·) の値が向上できる場合にのみ更新を行う点，および

図 3(e)–3(f) は f (O∗ ) の結果を示している．ここで，データセット間の f (O∗ ) のスケールの違いは，データの属性値のス
ケールによるものである．図 3(e)–3(f) から，k が大きくなると，f (O∗ ) は小さくなることが分かる．これは，k が大きくなると，mino,o′ ∈Ot∗

curdist(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∗ ) を維持していることが分かる．グリーディは通信量および更新時間の観点からもベースラインを上回る性能を示してお100001000

ベースライン

グリーディ

グリーディ

る [10]，[16]．しかし，これらは静的データのみを対象としており，動的データに対しては再計算が必要となるため，本問題へ

1000

通信量 [MB]通信量 [MB]

ベースライン

100

10

100

の効率的な解法にはなり得ない．

10

1

8. お わ り に

1
10

20

30

40

50

60

70

80

90 100

10

20

30

40

delta (Cdad)

50

60

70

80

90 100delta (Stock)(a) Cdad

分散ストリーム環境を想定したアプリケーションの増加，および多様化された結果の有用性の背景から，分散ストリーム環(b) Stock

境における k-多様集合モニタリング問題に取り組んだ．本稿で80

120

ベースライン

50
40
30
20

グリーディ
80

シュを利用する近似アルゴリズムを提案した．実分散環境での60実験から，提案アルゴリズムの有効性を示した．

40

本稿では，M AX M IN 関数のみに着目したが，提案アルゴリ

20

10
0

ズムの適用先をさらに広げるため，多くの目的関数を利用でき

0
10

20

30

40

50

60

70

80

90 100102030

delta (Cdad)

40

50

60

70

80

90 100delta (Stock)(c) Cdad(A)(26240013) および JST 国際科学技術共同研究推進事業（戦12ベースライン

35000
30000

ベースライン

グリーディ

f(O*)

25000
20000
15000

グリーディ

10

略的国際共同研究プログラム）の研究助成によるものである．

8

ここに記して謝意を表す．

6

文

4

10000

2

5000
0

0
10

20

30

40

50

60

70

80

90 1001020

delta (Cdad)

30

40

50

60

70

80

90 100delta (Stock)(e) Cdad(f) Stock

図4

るように拡張することが今後の課題として挙げられる．
謝辞．本研究の一部は，文部科学省科学研究費補助金・基盤研究(d) Stock

40000

f(O*)

は，空間計算量，時間計算量，および通信量が効率的な，キャッ

100

グリーディ

60

更新時間 [msec]

更新時間 [msec]

70

ベースラインδ の 影 響り，アルゴリズム 8 の有効性を確認できる．

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

献[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, monotone 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 ofOperational Research, Elsevier, 46(1):48–60, 1990.
[7] M. Ghashami, J. M. Phillips, and F. Li. Continuous matrix approximation 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 prediction models. ACM TODS, 39(2):16, 2014.
[9] S. Gollapudi and A. Sharma. An axiomatic approach for result diversification. In WWW, pages 381–390, 2009.
[10] M. Hasan, A. Mueen, and V. Tsotras. Distributed diversification oflarge 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 decompositions. PVLDB, 8(5):545–556, 2015.
[12] E. Minack, W. Siberski, and W. Nejdl. Incremental diversificationfor 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 distributed sliding-window data streams. The VLDB Journal, pages 1–
24, 2015.
[15] I. Sharfman, A. Schuster, and D. Keren. A geometric approach tomonitoring 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.