DEIM Forum 2019 D4-2

位置・キーワードに基づく k NN データモニタリングの分散処理のためのクエリ割り当てアルゴリズム
鶴岡

翔平†

西尾

俊哉††

天方 大地††

原隆浩††† 大阪大学工学部電子情報工学科 〒 565-0871 大阪府吹田市山田丘 1-5†† 大阪大学大学院情報科学研究科 〒 565-0871 大阪府吹田市山田丘 1-5
E-mail: †{tsuruoka.shohei,nishio.syunya,amagata.daichi,hara}@ist.osaka-u.ac.jp
あらまし 近年，パブリッシュ/サブスクライブ（Pub/Sub）モデルに基づいてデータを配信するアプリケーションが多く存在し，ユーザは自身の興味のあるデータのみを取得する．また，スマートフォンや SNS の普及により，データやクエリの数が増加しており，単一のサーバで全ての処理を行うとリアルタイム性を保持することが困難になっている．本稿では，Pub/Sub モデルにおいて，複数のサーバにクエリを分散して処理を分担することにより，各クエリに対して，クエリのキーワードを含むデータの中でクエリに最も近い k 個のデータ（kNN データ）を効率的にモニタリングする問題に取り組む．単純にクエリを分散させると，各サーバの処理量に偏りが生まれ，その結果，新たなデータが生成されたとき，処理量の大きいサーバの処理時間が長くなり，全体の処理時間も長くなる．この問題を解決するため，各サーバの処理時間が均一かつ全体の処理時間が短くなるようにクエリを分散するアルゴリズムを提案する．
実データを用いた実験により，提案手法の有効性を示す．
キーワード Pub/Sub，kNN クエリ，分散処理

1 はじめに
近年，GPS 機能付きのモバイル端末の普及により，ジオタグ付きのツイートなどの位置情報とキーワードを持つデータが大量に生成されている．それらのデータの中から，ユーザが自身の興味のあるデータを得るための手段としてパブリッシュ/サブスクライブ（Pub/Sub）モデルに基づくアプリケーションが多く存在する [7]，[9]．Pub/Sub モデルでは，ユーザは事前にサーバへクエリを登録し，サーバは登録されたクエリに基づいてユーザにデータを配信する．大量にデータが存在する環境で(a) 時刻 tは，クエリのキーワードを含むデータの中で，クエリに最も近い k 個のデータ (kNN データ) を検索する kNN クエリが有用である [5]．さらに，Pub/Sub モデルでは頻繁にデータが生成されるため，各クエリの kNN データは頻繁に変化する．
例 1．図 1 は，Pub/Sub モデルにおいて，3 人のユーザが自身の興味のあるデータをモニタリングする例を示している．各
ユーザはクエリ（位置情報およびキーワード）を登録しており，クエリに合う k 個のデータをモニタリングしている．k =2 と仮定すると，時刻 t において，ユーザ u1 の kNN データ(b) 時刻 t + 1

は，「コーヒー」を含み，かつ u1 に最も近いデータ o2 および o4

図 1: Pub/Sub モデルにおける kNN データのモニタリングの例

である．時刻 t + 1 において，o6 が生成されると，各クエリのkNN データが更新される．o6 は，「コーヒー」を含み，o4 より

タやクエリの数が増加すると，新たに生成されるデータに対す

も u1 に近いため，u1 の kNN データは，o2 および o6 に変化るサーバの処理量が増加するため，単一のサーバで全ての処理する．

を行う場合にリアルタイム性を保証することが難しくなる．そここで，スマートフォンや SNS の普及により，生成される

こで，本稿では，複数のサーバにクエリを分散して処理を分担

データやサーバに登録されるクエリの数は増加している．デー

することにより，各クエリの kNN データを効率的にモニタリ

ングする問題に取り組む．
課題． 複数のサーバにクエリを分散して各クエリの kNN デー
タを効率的にモニタリングするためには，クエリをどのようにサーバへ分散するかが重要である．単純な方法では，同じキー
ワードを持つクエリを一つのサーバで管理する方法が考えられる．しかし，あるキーワードが多くのデータやクエリに含まれる場合，そのキーワードを持つクエリを管理するサーバの処理量が大きくなってしまう．また，もう一つの方法として，クエリが存在する領域をサーバの数に等分割し，各領域に含まれるクエリを一つのサーバで管理する方法が考えられる．しかし，ある領域にデータやクエリが多く存在する場合，その領域に含る [2], [4]，[10]．文献 [4] では，位置情報およびキーワードに基づいてクエリを分散するアルゴリズムが提案されている．しかし，この研究はレンジクエリを対象としており，kNN クエリを対象とした本研究とは問題が異なる．また，文献 [2], [10] では，

Pub/Sub モデルにおいて，キーワードに基づいてクエリを分散するアルゴリズムが提案されている．例えば，文献 [2] では，
データのキーワードの出現頻度に基づいて，各サーバが担当するキーワードを決定し，担当するキーワードを持つクエリを管理する．しかし，これらの研究では，データおよびクエリの位
置情報を考慮しておらず，位置情報を考慮した場合，提案アルゴリズムは効果的ではない．

まれるクエリを管理するサーバの処理量が大きくなってしまう．

位置情報を用いたクエリの分散処理．文献 [1], [6] では，位置情

このように，単純にクエリを分散させると，各サーバの処理量報に基づいてデータを分散するアルゴリズムが提案されている．

に偏りが生まれる．その結果，新たなデータが生成されたとき，

例えば，文献 [6] では，データが含まれる領域をサーバの数に処理量の大きいサーバの処理時間が長くなり，全体の処理時間

分割し，１つの領域に含まれるデータを１つのサーバで管理すも長くなる．

る．そして，ある kNN クエリの解を計算するとき，まず，ク

提案アルゴリズムの概要． この問題を解決するため，まず，あるデータが生成されたとき，各サーバにおける処理時間を予測するため，サーバの負荷を定義する，あるサーバの負荷は，そのサーバで管理するクエリの負荷の合計と定義し，あるクエリの負荷はデータやクエリの位置情報とキーワードに基づいて計算される．そして，各サーバの負荷を均一にしつつ，全体の負荷を小さくするようにクエリを分散するアルゴリズムを提案する．具体的には，全てのクエリの集合 Q を，集合の数が一定数以上になるまで，部分集合 Qi に分割する．そして，各サーバの負荷が均一になるように，Qi に含まれるクエリを管理する
サーバを決定する．これにより，各サーバの負荷を均一にしつエリの位置を含む領域の中で kNN データを検索する．その後，クエリと k 番目のデータの距離の範囲が，他の領域に重複する
場合，その領域に含まれるデータも含めて kNN データを検索する．しかし，これらの研究では，データおよびクエリのキー
ワードを考慮していない．また，MapReduce 環境を想定しており，ストリームデータに適用できない．

3 問題定義3. 1 定義これまでに生成されたデータの集合を O，発行されたクエリの集合を Q とする．

つ，全体の負荷をより小さくするようにクエリを分散する．
貢献．以下に本研究の貢献を示す．

•

複数のサーバでクエリを分散管理して処理を分担することにより，各クエリの kNN データを効率的にモニタリングす

データモデル．あるデータ o ∈ O は位置（o.loc），およびキーワード集合 (o.key) で構成される（o = ⟨loc, key⟩）．o.loc は，
緯度と経度によって表される 2 次元平面上の点である．

る問題に取り組む．著者らの知る限り，この問題はこれまでにクエリモデル．ある kNN クエリ q ∈ Q は，位置（q.loc），

取り組まれていない．

キーワード集合 (q.key)，および何個のデータを受信するかを•

各サーバの負荷を均一にしつつ，全体の負荷を小さくするようにクエリを分散するアルゴリズムを提案する．

•

実データを用いた実験により，提案アルゴリズムの有効性を確認する．

指定する変数 (q.k) で構成される（q = ⟨loc, key, k⟩）．q.key
は，keymax 個以下のキーワードを指定する．O が与えられた
とき，q の kNN データ A は次の条件を満たす．
（i）|A| = k ，′(ii)∀o ∈ A, ∀o′ ∈ Oq − A, dist(o.loc, q.loc) <= dist(o .loc, q.loc)

ここで，Oq は O の中で q.key に含まれるキーワードを一つ以
本稿の構成．２章で関連研究について説明し，３章で本稿の問題を定義する．４章で提案アルゴリズムについて説明し，5 章

上含むデータ集合，dist(·, ·) はデータとクエリとのユークリッ
ド距離である．

で実データを用いた実験の結果を示す．最後に 6 章で本稿をまとめる．

問題定義．O および Q が与えられたとき，Q に含まれる全てのクエリの kNN データをモニタリングする．

2 関連研究本章では，クエリの分散処理の関連研究を紹介する．

Pub/Sub モ デ ル に お け る ク エ リ の 分 散 ．様々な 研 究 が ，
Pub/Sub モデルにおいて，複数のサーバでクエリを分散して管理し，クエリの解をモニタリングする問題に取り組んでい3. 2 最適なクエリの分散
本稿では，複数のサーバでクエリを分散して管理することで，各クエリの kNN データを効率的にモニタリングする．複数のサーバでクエリを管理する際，各サーバの負荷を均一にしつつ全体の負荷を小さくすることが望ましい．まず，サーバの負荷を定義する．

定義 1（サーバの負荷）．あるサーバ si の負荷 L(si ) を以下で定義する．

L(si ) =

∑

L(q)

q∈Qsi

ここで，Qsi はサーバ si で管理されているクエリの集合である．また，L(q) はクエリ q の負荷であり，データおよびクエリの位置情報とキーワードに基づいて計算される．
次に，サーバの負荷に基づいて，各サーバの負荷を均一にしつつ，全体の負荷を最小にするクエリの分散を決定するクエリ分散問題を定義する．

図 2: kNN の更新の範囲

定義 2(クエリ分散問題)．O，Q およびサーバの数 m が与えられたとき，クエリ分散問題は，Q を以下の条件を満たす m 個∑の集合 Q1 ，Q2 ，· · ·，Qm に分割する．
（i） m
i=1 L(si ) が最小（ii）∀i =| j に対して，L(si ) >= σ ．ここ= L(sj )，L(si )/L(sj ) <で，σ ≃ 1 である．

とき，あるクエリ q の kNN データとなりえるデータは，q.keyに含まれるキーワードを 1 つ以上含むデータであるため，L(q)は Pt (w) を用いて，以下のように計算される．

このとき，以下の定理が成り立つ．

L(q) =∑

Pt (w)w∈q.key定理 1．クエリ分散問題は NP 困難である．
ここから，あるクエリを管理するサーバを決定するアルゴリ

n 個の整数 a1 , a2 , · · · , an を 2 つの集合に分けるとき，ズムを紹介する．まず，全てのクエリ q ∈ Q に対して L(q) を各集合に含まれる整数の和が等しくなる集合に分ける問題を分計算する．そして，L(q) の大きいクエリから順に，クエリを管証明.

割問題と呼び，この問題は NP 完全である．文献 [8] では，分理するサーバを決定する．あるクエリ q を管理するサーバは，割問題を拡張し，n 個の整数 a1 , a2 , · · · , an を，k 個の集合にその時点でサーバの負荷が最も小さいサーバ si とする．この分けるとき，各集合に含まれる整数の和の中で，最大のものと操作を，全てのクエリに対してそれらを管理するサーバを決定最小のものの差が最小となる集合に分ける問題に取り組んでおするまで繰り返すことで，クエリの分散を決定する．

り，この問題は NP 困難である．ここで，m = k および σ = 1であるとき，クエリ分散問題は，∑
q1 ∈Q1

L(q1 ) =∑L(q2 ) = · · · =q2 ∈Q2

新たなデータ o が生成されたとき，各サーバで管理するクエ
リの kNN データを更新するアルゴリズムを紹介する．各サー∑

L(qk )

qk ∈Qkを満たすような k 個の集合 Q1 , Q2 , · · · , Qk を見つけることである．これは，文献 [8] で取り組まれている問題を解くことと同じである．よって，定理が成り立つ．

バ s は，自身の管理するクエリに対して，キーワードごとにク
エリへのポインタを管理する転置ファイル s.I を保持する．s.Iを用いて，o のキーワードを含むクエリの集合 Qc を取得し，

q ∈ Qc の kNN データを更新する．
3. 3. 2 位置情報に基づくクエリの分散
クエリが存在する領域をサーバの数に等分割し，各領域に含3. 3 ベースラインアルゴリズム

まれるクエリを１つのサーバで管理する方法のように，単純にクエリ分散問題は NP 困難であるため，貪欲法を用いてクエクエリを分散すると，各サーバの負荷に偏りが生まれる．そこ

リの分散を決定する．まず，べースラインとなるアルゴリズム

で，各領域に含まれるクエリ集合の負荷を考え，負荷の大きいを紹介する．

領域を小さい領域に分割する．そして，各サーバで複数の領域

3. 3. 1 キーワードに基づくクエリの分散に含まれるクエリ集合を管理することで，各サーバの負荷を均

同じキーワードを持つクエリを１つのサーバで管理する方法

一にする．

のように，単純にクエリを分散すると，各サーバの負荷に偏り

まず，ある領域 r に含まれるクエリ集合を Qr とし，Qr の負が生まれる．そこで，データに頻出するキーワードを持つクエ

荷 L(Qr ) を考える．L(Qr ) は，新たに生成されたデータによリから順に，サーバに分散することで，各サーバの負荷を均一

り Qr 内に含まれるクエリの kNN データが変化する可能性がにする．

ある確率と考えることができる．ここで，クエリ q の k 番目のまず，データのキーワードが時間により変化しない，かつ各

データを ok とすると，新たに生成されたデータ o が q の kNN

キーワードの出現確率が独立であると仮定すると，新たなデー

データとなるには，dist(o.loc, q.loc) < dist(ok .loc, q.loc) が必

タ o が生成されたとき，o.key にキーワード w が含まれる確率要である．つまり，q.loc から dist(ok .loc, q.loc) の範囲を Cq とPt (w) は以下の式で計算される．

すると，Cq 内に生成されたデータが q の kNN データとなりえ

Pt (w) =

|Ow |
|O|

ここで，Ow は O の中で w を含むデータの集合である．このる．したがって，Qr に含まれる全てのクエリの Cq を包含する
領域を R とすると，R 内で生成されるデータが，Qr 内に含まれるクエリの kNN データとなりえる．例えば，図 2 において，

ある領域 r 内に４つのクエリが存在している．このとき，それぞれのクエリの Cq を包含する領域が R である．また，データの位置の分布が時間により変化しないと仮定すると，R 内に新
たなデータが生成される確率 Ps (R) は以下の式で計算される．

Ps (R) =

|OR |
|O|

ここで，OR は R に含まれるデータの集合である．よって，

L(Qr ) は，Ps (R) を用いて，以下のように計算される．
L(Qr ) = Ps (R) × |Qr |

(a)

(b)
図 3: 2 種類のデータとクエリ

さらに，各サーバは，複数の領域に含まれるクエリ集合を管理するため，L(si ) は，L(Qr ) を用いて，以下のように計算さなるため，キーワードに基づいてクエリを分散したとき，全体れる．

の負荷が小さくなる．よって，図 3a の場合，位置情報に基づL(si ) =∑L(Qr )Qi ∈si .Q

ここで，si .Q は，si が管理するクエリ集合の集合である．

いたクエリの分散，図 3b の場合，キーワードに基づいたクエ
リの分散が適している．
そこで，提案アルゴリズムでは，あるクエリの集合を分割す

ここから，クエリの分散を決定するアルゴリズムを紹介するとき，クエリおよびデータの位置およびキーワードの分布にる．まず，クエリおよびデータが存在し得る領域を R2 とする．

基づき，位置に基づく分割およびキーワードに基づく分割のうR2 を 4 つの領域に等分割し，各領域 r に含まれるクエリ集合

ち，負荷の小さくなる分割を選択することで，全体の負荷がよ

Qr に対して，L(Qr ) を計算する．そして，全ての領域の中でり小さくなるようにクエリを分割する．その後，各サーバの負L(Qr ) が最も大きい領域を再帰的に分割する．この処理を，分荷が均一になるように，分割された各クエリ集合に含まれるク

割された領域の数が，サーバの数の α 倍になるまで行う．そのエリを管理するサーバを決定する．

後，L(Qr ) の大きいクエリ集合から順に，その集合を管理する
サーバを決定する．あるクエリ集合 Qr を管理するサーバは，

4. 1 位置，キーワードに基づくサーバの負荷

その時点で管理するクエリ集合の負荷の合計が最も小さいサー

はじめに，位置およびキーワードに基づく負荷を定義する．

バ si とする．この操作を，全てのクエリ集合を管理するサーバ

まず，あるクエリ集合 Qi に含まれるクエリ q の負荷を考える．

を決定するまで繰り返す．

データの位置およびキーワードの分布が，時間により変化しな

新たなデータ o が生成されたとき，各サーバで管理するクエリ

い，かつ各キーワードの出現確率が独立であると仮定すると，の kNN データを更新するアルゴリズムを紹介する．まず，サー

新たなデータ o が生成されたとき，o.loc が R 内に含まれ，かバ s が管理するクエリ集合 Qi ∈ s.Q の中で，o.loc ∈ Qi .R で

つ o.key にあるキーワード w が含まれる確率 P (R, w) は，以ある集合を Qc とする．各サーバ s は，各クエリ集合 Qi ∈ s.Q

下の式で計算される．

に対して，キーワードごとにクエリ q ∈ Qi へのポインタを管

P (R, w) =理する転置ファイル Qi .I を保持している．よって，Qi ∈ Qc

|OR,w |
|O|に対して，Qi .I を用いて，o のキーワードを含むクエリの集合

ここで，OR,w は R 内に含まれ，かつ w を含むデータの集合でQc を取得し，q ∈ Qc の kNN データを更新する．

ある．このとき，Qi に含まれるクエリ q の kNN データとなりえるデータは，R 内に含まれ，かつ q.key に含まれるキーワー

4 提案アルゴリズム
ベースラインアルゴリズムでは，位置情報またはキーワードのいずれかに基づいて，クエリ集合を分散した．しかし，クエ

ドを一つ以上含むデータであるため，L(q) は P (R, w) を用いて，以下のように計算される．
∑
L(q) =

リおよびデータの位置およびキーワードの分布によって，より良い分散の方法は異なる．図 3 に，クエリおよびデータの位置
およびキーワードの分布の一例を示す．図 3a の場合，各クエ
リの Cq は小さいため，位置情報に基づいてクエリを分散した
とき，全体の負荷が小さくなる．一方，全てのデータおよびク
エリが同じキーワードが含んでいるため，キーワードに基づい

P (R, w)w∈q.key

また，Qi の負荷 L(Qi ) は，Qi に含まれるクエリの負荷の合計と考えることができる．よって，L(Qi ) は L(q) を用いて，以下のように計算される．

L(Qi ) =

∑

L(q)

q∈Qi

てクエリを分散したとき，全体の負荷が大きくなる．また，図さらに，各サーバは複数のクエリ集合を管理するため，L(si )3b の場合，各クエリの Cq が大きく，Cq が重複しているため，は，L(Qi ) を用いて，以下のように計算される．
∑
L(si ) =L(Qi )

位置情報に基づいてクエリを分散したとき，全体の負荷が大きくなる．一方，データおよびクエリのキーワードがそれぞれ異Qi ∈si .Q

Algorithm 1 Query Set Partition

Algorithm 2 Server Decision

Input: Qi ,βInput: Q

Output: Q

1: while |Q| > 0 do

1: if |Qi | > β then2:

Pop Qi from Q
while |Qi | > 0 do

2:

Qs ← SpacePartition(Qi )3:3:Q ← Q ∪ Qs

4:

Pop q from Qi

5:s ← arg min L(s)6:s.Q ← s.Q ∪ {q}4: elses∈S

5:

Qs ← SpacePartition(Qi )6:

Qt ← TextPartition(Qi )7:

Calculate Ct and Cs

8:

if Cs < Ct then

基づいて分割した集合の組を返す関数である．Cs < Ct ならば，

9:Q ← Q ∪ Qs

位置情報に基づく分割を選択し，Cs >= Ct ならば，キーワード

10:
11:

else

に基づく分割を選択する（8–11 行）．分割された全ての集合をQ ← Q ∪ Qt

Q とすると，|Q| が αm 以上になるまで，負荷の最も大きい集合 Qi を再帰的に分割する．

4. 2 分散のアルゴリズム

4. 2. 2 クエリ集合を管理するサーバの決定

ここから，クエリの分散を決定するアルゴリズムを説明する．

集合の分割後，各クエリ集合に含まれるクエリを管理する

4. 2. 1 クエリ集合の分割

サーバを決定する．同じクエリ集合に含まれるクエリは，位置あるクエリの集合 Qi を複数の集合に分割するとき，位置情が近く，同じような出現頻度のキーワードを持つクエリが多い

報に基づく分割およびキーワードに基づく分割のうち，より負ため，同じデータによってクエリの更新を行う可能性が高い．

荷の小さくなる方法で分割を行う．位置情報に基づく分割およ

そのため，１つのクエリ集合に含まれるクエリを１つのサーバ

びキーワードに基づく分割は，それぞれ以下の方法で行う．

で管理するのではなく，複数のサーバに分散させることで，各位置情報に基づく分割．Qi がある領域 r に含まれるとき，r を

4 つの領域 ri (1 <=i<= 4) に等分割し，それぞれの領域に含まれるクエリの集合 Qri に分割する．
キーワードに基づく分割．Qi に含まれるクエリ q を L(q) に基

サーバの負荷が均一になるようにクエリを分散する．
アルゴリズム 2 は各クエリ集合に含まれるクエリを管理するサーバを決定するアルゴリズムを示している．Q は分割された全てのクエリ集合であり，負荷の降順でソートされているとし，負荷の大きい集合 Qi から順に，管理するサーバを決定す

づいて，4 つの集合 Qti (1 <=i<= 4) に分割する．具体的には，る（2 行）．Qi に含まれるクエリが負荷の降順にソートされてL(q) が大きいクエリから順に，各集合に分配する．あるクエリいるとし，負荷の大きいクエリから順に管理するサーバを決定を分配するとき，その時点で分配されたクエリの負荷の合計がする．
（4 行）．あるクエリを管理するサーバは，その時点で負最も小さい集合に，クエリを分配する．この処理を Qi に含ま荷が最も負荷が小さいサーバ s とする (5–6 行)．Qi に含まれれる全てのクエリに対して行う．

る全てのクエリを管理するサーバを決定するまで，この操作を位置情報に基づく分割およびキーワードに基づく分割のうち，負荷の小さくなる分割方法を決定するため，それぞれの分割により得られた集合の負荷の合計を比較する．具体的には，
位置情報に基づく分割によって得られた集合の負荷の合計を∑
Cs = 1<i<4 L(Qri )，キーワードに基づく分割により得られ= =∑た集合の負荷の合計を Ct = 1<i<4 L(Qti ) とする．Cs が Ct
= =より小さければ，位置情報に基づく分割を選択し，Ct が Cs より小さければ，キーワードに基づく分割を選択する．
アルゴリズム 1 は，クエリの集合 Qi を分割するアルゴリズムを示している．まず，キーワードに基づく分割は，Qi に含まれるクエリを 1 つずつチェックするため，Qi に多くのクエリが含まれるとき，分割に多大な時間がかかる．そのため，|Qi | > βである場合，常に SpacePartition(Qi ) を実行する（2–3 行）．ここで，SpacePartition(Qi ) は，Qi を位置情報に基づいて分割した集合の組を返す関数である．|Qi | <= β である場合，位置情報に基づく分割およびキーワードに基づく分割を行い，それぞれ行う．この処理を，全てのクエリ集合に対して行う．

4. 3 kNN データの更新アルゴリズム
新たなデータ o が生成されたとき，各サーバで管理するク
エリの kNN データを更新するアルゴリズムを紹介する．まず，クエリおよびデータが存在し得る領域 R2 を n × n の領域に等分割する．各サーバは，それぞれの領域 ri に対して，サーバで管理するクエリ q ∈ s.Q の Cq が ri と重複するクエリへのポ
インタをキーワードごとに管理する転置ファイル ri .I を保持する．新たなデータ o が生成されたとき，o.loc ∈ ri となる領域の ri .I を用いて，o のキーワードを含むクエリの集合 Qc を取得し，q ∈ Qc の kNN データを更新する．

5 評価実験
本章では，提案アルゴリズムの性能を評価するため，以下のアルゴリズムとの比較を行った．

によって得られた集合の負荷の合計 Cs および Ct を計算する•（5–7 行）．ここで，TextPartition(Qi ) は，Qi をキーワードに行う．

ベースライン 1：キーワードに基づいてクエリの分散を表 1: データセットの詳細ツイートの数20,000,000

キーワードの数

2,225,654

１つのツイートに含まれるキーワードの数の平均

5.51

表 2: パラメータの設定

•

パラメータ

値

サーバ数

2, 4, 8, 16

q.k の最大値，kmax

5, 10, 15, 20(a) 平均更新時間(b) 更新時間のばらつき

図 4: サーバ数の影響

ベースライン 2：位置情報に基づいてクエリの分散を行う．

5. 1 セッティング
本 実 験 は ，Windows 10 Pro，3.00GHz Intel Xeon Gold

6154，および 512GB RAM を搭載した計算機で行い，全てのアルゴリズムは C++で実装した．

(a) 平均更新時間

データセット．本実験では，生成されるデータとして Twitter [3](b) 更新時間のばらつき

図 5: kmax の影響のツイートを用いた．表 1 にデータセットの詳細を示す．各ク
エリは，1 つのツイート中に現れる単語の中から，5 個以下の単語をランダムに選び，クエリのキーワード集合とする．

る時間を見積もることができる．また，位置に基づく分割およびキーワードに基づく分割のうち，より全体の負荷が小さくな

パラメータ．表 2 に，本実験で用いたパラメータを示す．太るようにクエリ集合を分割することで，クエリの更新にかか字で表されている値はデフォルトの値である．クエリの数をる時間が短くなる．さらに，同じクエリ集合に含まれるクエリ

1,000,000 とし，さらに，k は 1 から kmax の間の一様乱数とは，位置が近く，同じような出現頻度のキーワードを持つクエした．また，α = 20 および β = 100, 000 とした．さらに，1リが多いため，同じデータによってクエリの更新を行う可能性

度に 1,000 個のデータが発生するとする．実験は，データがが高い．そのため，１つのクエリ集合に含まれるクエリを１つ

1,000,000 個発生した時点で，クエリを分散し，新たに 1,000,000のサーバで管理するのではなく，複数のサーバに分散させるこ

個のデータが発生するまで行う．

とで，各サーバの更新時間のばらつきが小さくなり，平均更新

5. 2 評 価 結 果

時間も小さくなる．
各アルゴリズムにおいて，サーバ数が増加すると，各サーバ

本節では，各アルゴリズムにおける平均更新時間 (1 度に発生で更新を行うクエリの数が小さくなるため，更新時間のばらつする全てのデータに対して，kNN データの更新が完了するまきは小さくなる．提案アルゴリズムは，各ベースラインに比べでの平均時間 [msec]) およびサーバの更新時間のばらつき (各て，更新を行うクエリの数がより小さくなり，各サーバで更新

サーバで管理しているクエリの kNN データの更新が完了するを行うクエリの数の差が小さくなるため，更新時間のばらつき

までの時間の中で最大の時間と最小の時間の差 [msec]) の結果

がより小さくなる．

を示す．
サーバ数の影響．図 4 にサーバ数を変えたときの結果を示す．
サーバ数が増加すると，各サーバで管理するクエリの数が少なくなるため，各アルゴリズムにおいて，平均更新時間は小さくなる．また，提案アルゴリズムは，サーバ数によらず，常に平均更新時間が最も小さい．ベースライン 1 では，発生したデー

kmax の影響．図 5 に kmax を変えたときの結果を示す．kmaxが増加すると，kNN データが変化するクエリの数が増加するため，各アルゴリズムにおいて，平均更新時間が大きくなる．提案アルゴリズムは，kmax によらず，常に平均更新時間が最も小さい．ベースライン 2 は，kmax が増加すると，クエリ集合の R の範囲が大きくなり，新たに発生したデータが kNN デー

タのキーワードを含む全てのクエリの kNN データの更新を行

タとなる可能性があるクエリの数が大きくなるため，平均更新

うため，平均更新時間は大きくなる．ベースライン 2 では，ク時間が大きくなる．提案アルゴリズムは，位置とキーワードに

エリ集合の R と転置ファイルに基づいて，kNN データの更新基づいた負荷がより小さくなるようにクエリ集合を分割し，１を行うクエリを決定する．これにより，ベースライン 1 に比べつのクエリ集合に含まれるクエリを複数のサーバに分散するこて，更新を行うクエリの数が小さくなるため，平均更新時間は小さくなる．提案アルゴリズムでは，位置とキーワードに基づ
く負荷を考慮することにより，ベースライン 2 よりも，より正確にクエリ集合に含まれるクエリの kNN データの更新にかかとで，各サーバの更新時間のばらつきが小さくなり，平均更新
時間も小さくなる．
提案アルゴリズムは，kmax によらず，常に更新時間のばら
つきが小さい．ベースライン 1 では，kmax によってクエリの負荷が変化することはなく，各サーバで管理されるクエリは変化しない．したがって，各サーバで更新を行うクエリの数は変化しないため，更新時間のばらつきがほぼ一定である．ベース
ライン 2 では，kmax が増加すると，各クエリ集合の R の範囲
が大きくなり，各サーバで管理されるクエリ集合の R の範囲が重複する可能性が大きくなる．したがって，あるサーバの R の範囲が重複する位置にデータが発生した場合，そのサーバで更新を行うクエリの数が大きくなるため，更新時間のばらつきが大きくなる．提案アルゴリズムでは，同じクエリ集合に含まれるクエリは，位置が近く，同じような出現頻度のキーワードを持つクエリが多いため，同じデータによってクエリの更新を行う可能性が高い．したがって，ベースライン２のように，１つのクエリ集合に含まれるクエリを１つのサーバで管理するのではなく，複数のサーバに分散するため，更新時間のばらつきが小さくなる．

6 ま と め近年，パブリッシュ/サブスクライブモデルに基づくアプリ
ケーションが多く存在する．また，スマートフォンや SNS の普及により，データやクエリの数が増加しており，単一のサーバで全ての処理を行うとリアルタイム性を保持することが困難になっている．本稿では，パブリッシュ/サブスクライブモデル
において，複数のサーバでクエリを分散管理して処理を分担することにより，各クエリの kNN データを効率的にモニタリン
グする問題に取り組んだ．データおよびクエリの位置情報およびキーワードに基づいてサーバの負荷を定義し，クエリ集合を分割する際，位置情報に基づく分割およびキーワードに基づく分割のうち，全体の負荷が小さくなる分割を選択することで，各サーバの負荷を均一にしつつ，全体の負荷を小さくするようにクエリを分散するアルゴリズムを提案した．実データを用いた実験により，提案アルゴリズムの有効性を確認した．
今後の課題．データの生成によって，クエリの kNN データが更新されると，クエリの Cq の大きさが変化し，クエリの負荷が変化する．その結果，サーバの負荷が変化し，各サーバの負荷が偏ってしまう可能性がある．データの生成によって，各サーバの負荷が均一でなくなったとき，サーバが管理するクエリ集
合を動的に変更し，各サーバの負荷を均一に保つアルゴリズムを提案することが今後の課題としてあげられる．
謝辞．本研究の一部は，文部科学省科学研究費補助金・基盤
研究 (A)(JP26240013)，(A)(JP18H04095)，および基盤研究(B)(T17KT0082a) の研究助成によるものである．ここに記して謝意を表す．

文

献[1] Aly, A.M., Mahmood, A.R., Hassan, M.S., Aref, W.G.,
Ouzzani, M., Elmeleegy, H., Qadah, T.: Aqwa: adaptive query workload aware partitioning of big spatial data.
PVLDB 8(13), 2062–2073 (2015)[2] Basık, F., Gedik, B., Ferhatosmanoğlu, H., Kalender, M.E.:s3 -tm : scalable streaming short text matching. The VLDB

Journal 24(6), 849–866 (2015)[3] Chen, L., Cong, G., Cao, X., Tan, K.L.: Temporal spatialkeyword top-k publish/subscribe. In: ICDE. pp. 255–266(2015)[4] Chen, Z., Cong, G., Zhang, Z., Fuz, T.Z., Chen, L.: Distributed publish/subscribe query processing on the spatiotextual data stream. In: ICDE. pp. 1095–1106 (2017)[5] Choi, D.W., Pei, J., Lin, X.: Finding the minimum spatial
keyword cover. In: ICDE. pp. 685–696 (2016)[6] Eldawy, A., Mokbel, M.F.: Spatialhadoop: A mapreduce
framework for spatial data. In: ICDE. pp. 1352–1363 (2015)[7] Hu, H., Liu, Y., Li, G., Feng, J., Tan, K.L.: A
location-aware publish/subscribe framework for parameterized spatio-textual subscriptions. In: ICDE. pp. 711–722(2015)[8] Korf, R.E.: Multi-way number partitioning. In: IJCAI. pp.
538–543 (2009)[9] Li, G., Wang, Y., Wang, T., Feng, J.: Location-aware publish/subscribe. In: SIGKDD. pp. 802–810 (2013)[10] Yu, A., Agarwal, P.K., Yang, J.: Subscriber assignment for
wide-area content-based publish/subscribe. TKDE 24(10),1833–1847 (2012)