DEIM Forum 2019 D5-5

ユーザの移動を考慮した位置・キーワードに基づく
Top-k データモニタリング
西尾 俊哉†

天方

大地†

隆浩†

原

† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{nishio.syunya,amagata.daichi,hara}@ist.osaka-u.ac.jp
あらまし 近年，多くのアプリケーションでは，パブリッシュ/サブスクライブ（Pub/Sub）モデルに基づいてデータが配信されており，ユーザは生成されたデータの中から自身が興味を持つもののみを取得する．また，スマートフォ
ンやタブレット端末の普及により，ユーザが移動しながらアプリケーションを利用し，現在地に近いデータを受信するムービングクエリへの関心が高まっている．本研究では，Pub/Sub モデルで生成されたデータの中から，ユーザが移動しながら自身の興味に合う上位 k 個のデータ（Top-k データ）をモニタリングする問題に取り組む．データが生成/削除されるたび，すべてのクエリの Top-k データを再評価し，また，ユーザが移動するたび，そのユーザの Top-k
データを再評価する方法は非効率的であり，多くのユーザが存在する環境に対応できない．この問題を解決するため，データの生成/削除やユーザの移動より Top-k データが変化する可能性のあるクエリに対してのみ，Top-k データを再評価するアルゴリズムを提案する．実データを用いた実験により，提案アルゴリズムの有効性を示す．
キーワード Pub/Sub，Top-k クエリ，ムービングクエリ

1. は じ め に
近年，SNS や GPS を搭載した端末の普及に伴い，位置情報
やキーワードを含むデータが大量に生成されている．これらを検索するアプリケーションの多くは，ユーザが事前に興味

コーヒー

日本食

寿司，日本食

𝑒1

𝑢1

寿司，茶

ラーメン

𝑒2

𝑒3

𝑢3

𝑢2

茶

日本食，
うどん，そば

ラーメン

コーヒー

𝑒4

𝑢5

𝑢4

: eクーポンのキーワード集合: クエリのキーワード集合のある位置やキーワード（クエリ）を指定し，それらに基づ(a) tmcur

いてユーザにデータを配信するパブリッシュ/サブスクライブ（Pub/Sub）モデルに基づいている [3], [6]．また，データが頻繁に生成/削除される環境では，大量のデータの中から，ユー

寿司，日本食コーヒー

ザの趣向に応じてデータのスコアを計算し，ユーザにとって有用な上位 k 個のデータ（Top-k データ）をモニタリングする

Top-k データモニタリングが実用的である [1]．さらに，スマー

𝑢1

𝑒1

日本食

𝑢3
茶
寿司，茶

コーヒー

𝑒4

𝑢4

寿司，茶

𝑒5

𝑢2

日本食，
うどん，そば

ラーメン

𝑒2

𝑒3

ラーメン

𝑢5
: eクーポンのキーワード集合: クエリのキーワード集合

トフォンやタブレット端末の普及により，ユーザが移動しながらアプリケーションを利用することが考えられる．このような場合，指定された位置ではなく，ユーザの現在地に近いデータを検索するムービングクエリが有用である [4], [7]．

(b) tmcur + 1

図 1: Pub/Sub 環境における，ユーザの移動を考慮した Top-k
データモニタリングの一例

これまでに，文献 [1], [5] において，Pub/Sub 環境におけるの類似した e クーポン e1 であると仮定する．同様に，u3 のTop-k データモニタリングに関する研究が行われている．しかTop-1 データは e2 であるとする．時刻 tmcur + 1 において，新し，これらの研究は，ユーザの指定するクエリの位置は固定でたに e5 が生成され，各ユーザが移動すると，各ユーザの Top-1

あることを想定しており，ユーザの移動を考慮していない．本

データが更新される．具体的には，u2 の Top-1 データは，e1

稿では，Pub/Sub 環境において，ユーザの移動によりクエリ

より現在地に近くキーワードの類似した e5 に変化する．さらの位置が変化するムービングクエリに対する Top-k データをモに，u3 は西へ移動したため，u3 の Top-1 データは，現在地にニタリングする問題に取り組む．

より近い e1 に変化する．

例 1. 図 1 は，Pub/Sub 環境において，ユーザが移動しながら，

課題. 各ムービングクエリの Top-k データを効率的にモニタリ興味のある e クーポンをモニタリングする例を表している．5

ングするために 2 つの課題が存在する．1 つ目の課題は，頻繁人のユーザがクエリを登録しており，最もクエリに合う e クーに生成/削除されるデータに対して各クエリの Top-k データをポン（Top-1 データ）をモニタリングしている．時刻 tmcur に

モニタリングすることである．単純な方法では，新たにデータ

おいて，ユーザ u2 の Top-1 データは，u2 に近くキーワード

o が生成されたとき，各クエリ s に対して o のスコアを計算し，

そのスコアが s の現在の k 番目のデータのスコアより良い場′

クエリモデル．位置およびキーワードに基づくムービング Top-合，o が s の Top-k データとなる．さらに，データ o が削除さ

k クエリを定義する．以降，これを MkSK（Moving Top-k

れたとき，o′ を Top-k データに含むクエリ s′ の Top-k データ

Spatial Keyword）クエリと呼ぶ．

を再計算する．これらは，クエリが大量に存在し，データが頻

定義 1 (MkSK クエリ). ある MkSK クエリ s は，ユーザの現繁に生成/削除される環境では多大な計算コストがかかる．2 つ在地（s.p），キーワード集合（s.t），上位何個のデータを要求

目の課題は，ムービングクエリに対して Top-k データをモニタするかを指定する変数（s.k ），および位置とキーワードに対す

リングすることである．あるユーザ u が移動したとき，u が発る重みを指定する変数（s.α）で構成される（s = ⟨p, t, k, α⟩）．

行したクエリ s の位置が変化することにより，各データのスコ

s.t は，tmax 個以下のキーワードを指定する．o と s が与えらアが変化するため，Top-k データが変化する可能性がある．単れたとき，s に対する o のスコア score(s, o) は以下のように計純な方法では，クエリが移動するたびに全てのデータのスコア算される：を再計算し，Top-k データを更新する．しかし，これには非常に大きな計算コストが必要である．文献 [4] では，ムービング

score(s, o) = α·dist(s.p, o.p)+(1−α)(1−text(s.t, o.t)) (1)

クエリの Top-k データをモニタリングするために Safe Region

ここで，dist(s.p, o.p) はクエリとデータとの空間距離を表すスコという技術を提案している．Safe Region は，クエリが移動しア（距離スコア），text(s.t, o.t) はクエリとデータのキーワードても Top-k データが変化しない領域であり，Safe Region を用の類似度を表すスコア（キーワードスコア）である．また，デーいることで，クエリが移動したときに Top-k データが変化す

タ集合 O が与えられたとき，s の Top-k データ A は次の条件

る場合を把握できる. しかし，データが新たに生成されると，を満たす．
（i）|A| = k ，（ii）∀oi ∈ A, ∀oj ∈ O\A, score(s, oi ) <=Safe Region が変化する可能性があるため，本問題に単純に適用できない．さらに，クエリが Safe Region の外に出たときやTop-k データが変化したとき，Safe Region を再計算する必要がある．データが大量に存在する環境では，この再計算に多大な計算コストが必要である．

score(s, oj )．
今後，特に明記する必要がない場合，s.k ，および s.α をそれぞれ k ，α と表記する．
距 離 ス コ ア は ユ ー ク リッド 距 離 を 用 い て 計 算 さ れ ，dist(s.p, o.p) = Edist(s.p,o.p)である．ここで，Edist(s.p, o.p)
M axdist

提案アルゴリズムの概要．これらの問題を解決するため，ムーはクエリとデータとのユークリッド距離，M axdist はクエリとビングクエリを Safe Region に基づいて管理する新たな四分木

データが存在し得る領域 R2 の最大距離である．キーワードスコ（SQ-tree）を提案する．SQ-tree は，新たにデータが生成され

アは Jaccard 類似度を用いて計算され，text(s.t, o.t) = |s.t∩o.t||s.t∪o.t|

たとき，Top-k データが変化する可能性のあるクエリを効率的に限定する．また，データの削除やユーザの移動により，あるクエリの Top-k データが変化する場合，新たに Top-k データとなるデータを効率的に検索するアルゴリズムを提案する．文献 [10] において筆者らが取り組んだ問題に対して，データの削除を考慮している．さらに，Safe Region の計算コストを削減するため，近似的な Safe Region を高速に計算するアルゴリズ
ムを提案する．

である．
問題定義．クエリ集合 S およびデータ集合 O が与えられたと
き，S に含まれるすべての s の Top-k データをモニタリング
する．

2. 2 既存研究のアルゴリズム
文献 [4] において，ユーザが移動しても Top-k データが変化しない領域である Safe Region を計算するアルゴリズムが提案されている．まず，Safe Region および Dominant Region を貢献と構成. 以下に，本研究の貢献を示す．
（i）本稿では，

Pub/Sub 環境において，移動するユーザ（ムービングクエリ）に対する Top-k データをモニタリングする問題に取り組む（2.
章）．
（ii）効率的に各クエリの Top-k データをモニタリングするアルゴリズムを提案する（3. 章）．
（iii）実データを用いた実験により，提案アルゴリズムの性能を評価する（4. 章）．また，定義する．
定義 2 (Safe Region). O，s = (p, t, k, α)，および s の A が与えられたとする．このとき，s の Safe Region R は次の条件を満たす：′
R = {p′ |∀oi ∈ A, ∀oj ∈ O\A, score(s′ , oi ) <= score(s , oj )}5. 章において関連研究について議論し，6. 章で本稿をまとめる．

(2)′

2. 予 備 知 識
本章では，本稿で考えるデータモデルおよび問題を詳細に定義し，その後，提案アルゴリズムで利用する既存研究のアルゴ
リズムを紹介する．

2. 1 定義′

ここで，s = (p , t, k, α) である.
定義 3 (Donimant Region).

s = (p, t, k, α) および 2 つのデータ oi , oj が与えられたとする．このとき，oi の oj に対す
る Dominant Region Doi ,oj は以下の条件を満たす：′
Doi ,oj = {p′ |score(s′ , oi ) <= score(s , oj )}データモデル．あるデータ o は，位置（o.p），およびキーワー

ここで，s′ = (p′ , t, k, α) である.

ド集合（o.t）で構成される（o = ⟨p, t⟩）．o.p は，緯度と経度

これらの定義から，以下の定理が成り立つ [4]．

によって表される２次元平面上の点とする．

定 理 1.

(3)

O，s，お よ び A が 与 え ら れ た と き, R =∩oi ∈A (∩oj ∈O\A Doi ,oj ) である.

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

Safe Region を効率的に計算するため，文献 [4] では Safe Region の部分領域である Local Safe Region（LSR）を計算する手法を提案している．LSR の計算は 3 ステップで行われる．
ステップ 1：oi ∈ A に対して，以下の条件を満たす楕円領域 Eoiを計算し，それらの共通部分 E = ∩oi ∈A Eoi を計算する．
′

′

′

′

=

1−α
(1
α

− text(s.t, oi .t))，お よ び γ

定理 2 より，ASR は，Safe Region を計算する際に，Domi-nant Region を計算する必要がない．つまり，楕円領域およびるため，Safe Region の計算コストを削減できる．今後，Safe

Region は ASR を指すとする．つまり，R = E である．
=

max{dist(s.p, oi .p) + roi |oi ∈ A} + ∆ であり，∆ は近似率を決めるパラメータである．また，Eoi は s.p と oi .p を焦点とする楕円領域を表す．次に，s.p を中心とし，半径 rs 内の領域
を Cs ，および半径 γ 内の領域を Csγ とする．また，各データ

oj に対して，oj .p を中心とし，半径 roj 内の領域を Coj とする．ここで，ある 2 つの領域 C1 ，C2 が与えられたとき，C1 がC2 に包含されているとき，C1 は C2 内に含まれると定義し，
γ
C1 ⊂=C2 と表記する．さらに，Co が Cs に含まれ，Cs に含まれないデータの集合を OCsγ \Cs とする．つまり，γ
OCsγ \Cs = {o|Co ⊂=Cs , Co ⊈ Cs }.

本稿では，スペースの都合上，すべての証明を省略する．

それらの共通部分を計算するだけで Safe Region を計算でき′

Eoi = {p |dist(s .p , oi .p) + dist(s.p, s .p ) <= γ − roi }, (4)
こ こ で ，roi

定理 2. OCsγ \Cs = ∅時 間 計 算 量 ．ASR の 計 算 は ，k 個 の 楕 円 領 域 お よ び そ れ
ら の 共 通 部 分 を 計 算 す る の み で あ る た め ，時 間 計 算 量 はO(k2 ) ≪ O(ck|OCsγ \Cs |) である．
3. 2 データの生成に対する処理
新たなデータ o が生成されたとき，各クエリの Top-k データ
を高速に更新するため，o により Top-k データが変化する可能性のあるクエリ集合 Sg を限定する必要がある．これを実現する方法として，R-tree や Quad-tree のような空間インデック
スでクエリを管理することが考えられる．しかし，ムービング
クエリはクエリの位置が常に変化するため，これらのインデッ(5)

クスで単純に管理できない．この問題を解決するため，ムービ
ングクエリを Safe Region に基づいて管理する新たな四分木である．

（SQ-tree）を提案する．そして，新たにデータが生成されたとステップ 2：各データ oj ∈ OCsγ \Cs に対して，Doi ,oj を計算し，き，SQ-tree を用いて Top-k データが変化する可能性のあるク

それらの共通部分 D = ∩oi (∩oj ∈Csγ \Cs Doi ,oj ) を計算する．

エリを効率的に限定する．

ステップ 3：E と D の共通部分を計算する．

SQ-tree の構造．あるクエリ s の R の重心を g とする．SQ-

時間計算量．ステップ 1 は，k 個の楕円領域およびそれらの共通

tree の各ノードは，g がノードの示す領域に含まれるクエリを部分を計算するため，時間計算量は O(k 2 ) である．次に，頂点管理する．また，SQ-tree は，既存の空間インデックスとは異なの数が v1 および v2 個である 2 つの多角形が与えられたとき，そり，葉ノードだけでなく，中継ノードでもクエリを管理し，あれらの共通部分の計算の時間計算量は O((v +l) log2 (v +l)) であるノード n で管理するクエリの集合を Sn ，n を根とする部分木る [8]．ここで，v = v1 + v2 および l は多角形の辺同士の交点ので管理されるクエリ集合を Snr とする．n は，Snr に含まれるク数である．よって，ステップ 2 の時間計算量は O(ck|OCsγ \Cs |)エリのキーワード集合 Tnr = ∪s∈Snr s.t，および新たに発生したである．ここで，c = (v + l) log2 (v + l) である．ステップ 3 の

データ o により Snr に含まれるすべてのクエリの Top-k データ

時間計算量は O(c) である．したがって，Local Safe Region のが変化することのない距離スコアの閾値 Λrn [i] (0 <=i<= tmax )計算の時間計算量は O(ck|OCsγ \Cs |) である．

3. 提案アルゴリズムを保存する．さらに，Sn =| ∅ であるとき，n は，Sn に含まれるクエリのキーワード集合の転置ファイル In ，および Sn に含まれるクエリに対する距離スコアの閾値 Λn [i] を保存する．

各クエリの Top-k データは，ユーザの移動およびデータの生成/削除により変化する可能性がある．ここから，ユーザの移動，データの生成，およびデータの削除に対する処理の詳細を紹介する．

3. 1 ユーザの移動に対する処理
提案アルゴリズムでは，Safe Region を用いて，各クエリ s のTop-k データをモニタリングする．2. 2 節で紹介した LSR の計算には，∀oi ∈ s.A および ∀oj ∈ OCsγ \Cs に対して Doi ,oj を計算する必要がある．多くのデータが存在している環境では，OCsγ \Csに多くのデータが含まれるため，LSR の計算コストは非常に大きくなる．この問題を解決するため，データの分布によらず近Λrn [i] および Λn [i] の詳細は後述する．
例 2. 図 2 に示すようにクエリが存在し，三角形が Safe Regionの重心を示すと仮定すると，図 3 の左図に示す SQ-tree が構築される．例えば，Snr 2 = {s1 , s2 , s3 , s4 , s5 } であるため，n2はそれらのキーワード集合および Λrn [·] を保存する．さらに，

Sn = {s1 , s3 } であるため，n2 はそれらのキーワード集合の転置ファイルおよび Λn [·] を保存する．
まず，SQ-tree を用いて Top-k データが変化しないクエリを枝刈りするフィルタリング技術を紹介し，その後，SQ-tree の構築方法およびメンテナンス方法について紹介する．

似的な Safe Region（ASR）を計算する手法を提案する．まず，フィルタリング技術．あるクエリ s の k 番目のデータのスコアをs に対する k + 1 番目のデータを ok+1 とする．そして，oi ∈ Ascorek (s) とする．このとき，新たに発生したデータ o により，sに対して Eoi を計算するとき，γ = dist(s.p, ok+1 .p) + rok+1 との Top-k データが更新されるためには，scorek (s) > score(s, o)

𝑛2

𝑠7

𝑠1

𝑑𝑖𝑠𝑡 𝑛2 , 𝑜1 . 𝑝 = 0.6

クエリ

キーワード

𝑠1

𝑤1 , 𝑤2

𝑠2

𝑜1

𝑠6

𝑠3

𝑠4

𝑠8

𝑤3 , 𝑤4 , 𝑤5 , 𝑤6

𝑤2 , 𝑤5

…

…

データ

キーワード

𝑜1

𝑤2 , 𝑤7 , 𝑤8𝑜2

𝑤1 , 𝑤2 , 𝑤3 , 𝑤5

𝑜2

𝑠10

𝑠13

: クエリ
: データ

𝑠9

𝑤2 , 𝑤4

𝑠4

𝑑𝑖𝑠𝑡 𝑛2 , 𝑜2 . 𝑝 = 0.4

𝑠12

𝑤3

𝑠3
𝑠5

𝑠5

𝑠11

𝑠2

𝑠6 , 𝑠7 , 𝑠8

𝑠1 , 𝑠3𝑛5𝑛6𝑠2

式（7）より，以下の定理が成り立つ．
定理 4. λ(s, i) < dist(s.R, o.p) ならば，o は s の Top-k データになり得ない．ここで，dist(s.R, o.p) は，o.p と s.R 内の任意の点との距離スコアの最小値である．
さらに，定理 4 から，以下の系が成り立つ

定理 4 および系 1 より，λ(s, i) < dist(s.R, o.p) ならば，正確性
𝑇𝑟 =
… 𝑛2

𝑠12

𝑛2

(7)

ない．

𝑛0

𝑛1

scoreub (s)1−α−(1 − textub (s.t, i)).
αα

系 1. λ(s, i) < dist(s.R, o.p) ならば，o により s.R は変化し

図 2: クエリおよびデータの位置とキーワード: 葉ノード: 中継ノードλ(s, i) =𝑛3𝑛4𝑠11 , 𝑠13

𝑠9 , 𝑠10Λ𝑟𝑛2 [0] Λ𝑟𝑛2 [1] Λ𝑟𝑛2 [2]…

Λ𝑟𝑛2 [𝑡𝑚𝑎𝑥 ]

0.3

…

1.0

0.5

0.8

𝑠5

𝐼𝑛2

𝑤1
𝑠1

𝑤2
𝑠1 , 𝑠3

ここから，SQ-tree の各ノードで管理されているクエリを枝刈りする方法について紹介する．この枝刈りは，ノードフィル

𝑆𝑛2 = 𝑠1 , 𝑠3𝑛7𝑠4を失うことなく s を枝刈りでき，s.R の更新も考えなくてよい．

𝑤1 , 𝑤2 , 𝑤30.3, 𝑤4 , 𝑤5 , 𝑤6

タリングおよびクエリフィルタリングの 2 段階の枝刈りを行う．

𝑤4
𝑠3

新たにデータ o が生成され，ノード n をチェックしたと仮定し，

Λ𝑛2 [0]Λ𝑛2 [1]Λ𝑛2 [2]…

Λ𝑛2 [𝑡𝑚𝑎𝑥 ]

0.1

0.3

0.5

…

0.9

それぞれの枝刈りについて説明する．まず，o.p と n との距離
スコアの最小値を dist(n, o.p) とし，o.p が n の領域内に含ま

図 3: SQ-tree の例

れる（o.p ∈ n）ならば，dist(n, o.p) = 0 とする．また，R がが必要である．ここで，位置，およびキーワードを考慮した検n に包含される場合，R は n に含まれる（R⊂=n），包含され索において，キーワードを優先したフィルタリングは，高速化ない場合，R は n に含まれない（R ⊈ n）と定義する．R ⊈ nに大きく貢献することが知られている [2]．そこで，提案アルゴであるとき，dist(n, o.p) <= dist(R, o.p) が常に成り立つとは

リズムでは，クエリとデータの間で一致するキーワードの数に限らない．この問題を解決するため，R が n からどれだけは基づいたフィルタリング技術を提案する．

み出ているかを表す追加の距離スコア distadd (R, n) を考える．

まず，s.p が既知であると仮定し，s.t と o.t の間で一致するキーワードの個数が i であるとき，text(s.t, o.t) の上界値

textub (s.t, i) は以下で与えられる．

補助定理 1 および式（1）より，Top-k データが更新されるための距離スコアの閾値 λd (s, i) が以下のように計算できる：

scorek (s)1−α−(1 − textub (s.t, i)).
ααdistadd (R, n) = max(0, distmax (g, R̂)−distmin (g, n̂)). (8)
ここで，distmax (g, R̂) は g と R の境界 R̂ との距離スコアの最i
補助定理 1. textub (s.t, i) = |s.t|.

λd (s, i) =distadd (R, n) は以下の式で与えられる．

(6)

式（6）より，以下の定理が成り立つ．

大値，distmin (g, n̂) は g と n の境界 n̂ との距離スコアの最小値である．このとき，以下の不等式が成り立つ．

dist(n, o.p) <= dist(R, o.p) + distadd (R, n)

式（9）より，Λrn [i] および Λn [i] をそれぞれ以下で定義する．

定理 3. λd (s, i) < dist(s.p, o.p) ならば，o は s の Top-k デー

Λrn [i] = max{λ(s, i) + distadd (s.R, n)|s ∈ Snr },タになり得ない．

Λn [i] = max{λ(s, i) + distadd (s.R, n)|s ∈ Sn }.

定理 3 より，λd (s, i) < dist(s.p, o.p) ならば，正確性を失うことなく s を枝刈りできる．
本研究では，ユーザは常に移動しているため，s.p は常に変化する．このとき，s.p により scorek (s) が変化し，λd (s, i) が変化するため，正確に枝刈りできない．この問題を解決するた(9)

ここで，|s.t| < i ならば，λ(s, i) = λ(s, |s.t|) である．
クエリフィルタリング．ノード n で管理されているクエリを枝刈りする方法を紹介する．まず，Λn [i] >= dist(n, o.p) を満たす
最小の i を imin とすると，以下の定理が成り立つ．

め，s.p が R 内の任意の位置であるとき，正確に枝刈りが可能

定理 5. o，imin ，および s ∈ Sn が与えられたとき，|s.t ∩ o.t| <なフィルタリング技術を提案する．まず，s.p が R 内の任意のimin ならば，o は s の Top-k データになり得ない．

位置であるとき，scorek (s) の上界値 scoreub (s) は以下で与え

定理 5 より，正確性を失うことなく，|s.t ∩ o.t| < imin を満られる．

たすクエリを枝刈りでき，それらの Top-k データおよび Safe

γ·α+scorek (s)補助定理 2. score(s, oi ) <= scoreub (s)=2

式（6）および補助定理 2 より，s.p が R 内の任意の位置であるとき，Top-k データが更新されるための距離スコアの閾値λ(s, i) は以下のように計算できる：

Region を更新する必要がない．
アルゴリズム 1 は，クエリフィルタリングを行うアルゴリズ
ムを示している．まず，imin を計算する（2 行）．ここで，Tnrと o.t の間で一致するキーワードの数を ic とし，ic >= tmax な
らば，ic = tmax とする．ic < imin ならば，s ∈ Sn に対して，

Algorithm 1: QueryFiltering(o,dist(n, o.p),ic )Algorithm 2: NodeFiltering(o, n)
Input: n and oInput: o, dist(n, o.p), and ic
1

Sg ← ∅ //Sg is a set of queries whose top-k results maychange.

imin ← min{i|Λn [i] >= dist(n, o.p)}<
3 if imin = ic then

2

4
5

6

for ∀s ∈ Sn where |s.t ∩ o.t| >= imin do
Sg ← Sg ∪ {s}return Sg

1

Sg ← ∅

ic ← min(|Tnr ∩ o.t|, tmax )r
3 if Λn [ic ] >= dist(n, o.p) then2

4

if n is not a leaf node then5for ∀n′ ∈ N //N is n’s children do

6

Sg ← Sg ∪ NodeFiltering(n′ , o)78

if Sn =
| ∅ thenSg ← Sg ∪ SubscriptionFiltering(o, dist(n, o.p), ic )|s.t ∩ o.t| < imin が成り立つため，imin <= ic である場合のみ，> imin を満たす s を Sg に加える（3–5 行）．
|s.t ∩ o.t| =9

例 3. 図 2 および図 3 において，o2 が生成され，n2 に対して，に，必ずしも o が ok+1 であるとは限らないため，ok+1 を検索

QueryFiltering(o2 , dist(n2 , o2 .p), ic ) を実行したと仮定する．こする必要がある．ok+1 を検索する方法については，3. 3 節におこで，ic = |Tnr2 ∩ o2 .t| = 4 である．dist(n2 , o2 .p) = 0.4 でいて紹介する．ok+1 を検索した後，s の新たな Safe Region をあるため，imin = 2 である．また，|s1 .t ∩ o2 .t| = 2 および再計算する．

|s3 .t ∩ o2 .t| = 1 である．よって，s1 のみ Sg に加える．

SQ-tree の構築．スコアは，位置，およびキーワードに基づい

ノードフィルタリング．ここから，n を根とする部分木を枝刈て計算されるため，両者を考慮して，クエリを分散するのが望りする方法を紹介する．Tnr は，Snr に含まれるクエリのキー

ましい．しかし，R-tree や Quad-tree といった空間インデック

ワード集合であるため，ic = min{|Tnr ∩ o.t|, tmax } が与えられ

スは，位置に基づいて領域を分割していく木構造であるため，たとき，以下の定理が成り立つ．

キーワードの特徴に基づいてクエリを分散できない．この問題

定理 6.

Λrn [ic ] < dist(n, o.p) ならば，o は Snr に含まれるすべてのクエリの Top-k データになり得ない．
定理 6 より，Λrn [ic ] < dist(n, o.p) ならば，正確性を失うことなく，n を枝刈りでき，Snr に含まれるすべてのクエリの Top-k
データおよび Safe Region を更新する必要がない．
アルゴリズム 2 は，ノードフィルタリングを行うアルゴリ
ズムを示している．まず，ic を計算する（2 行）．n が枝刈りされずかつ葉ノードでないとき，n の子ノード n′ に対して

Nodefiltering(n′ , o) を再帰的に実行する．さらに，Sn =| ∅ならば，SubscriptionFiltering(o, dist(n, o.p), ic ) を実行する（4–8 行）．
例 4. 図 2 および図 3 において，o1 が生成され，n2 に対して，

Nodefiltering(n2 , o1 ) を実行したと仮定する．Tnr2 と o1 .t の間

return Sgを解決するため，SQ-tree は，すべてのクエリを葉ノードで管理するのではなく，各クエリのキーワードに関する特徴を考慮
し，中継ノードでもクエリを管理する．ある中継ノード n でクエリを管理した場合，n の子ノード n′ に対して，Snr ′ に含まれるクエリの数が減少し，n′ の距離スコアの閾値 Λrn [·] がタイトになる．その結果，ノードフィルタリングにより n′ を枝刈りできる可能性が大きくなる．
ここから，あるクエリ s をノード n で管理すべきか，子ノードに分配すべきかを決定するアルゴリズムについて紹介する．
まず，あるデータ o が生成されたとき，n に対して計算される

dist(n, o.p) の期待値を E[dist(n, o.p)]（注 1） とする．このとき，
式（1）および補助定理 2 から，s の Top-k データが更新されるために必要なキーワードスコアの期待値 E[text(s.t, o.t)] は
以下のように計算される：で一致するキーワードは w2 のみであるため，ic = 1 である．

dist(n2 , o1 .p) = 0.6 であるため，Λrn2 [ic ] < dist(n2 , o1 .p) であscoreub (s) − α · E[dist(n, o.p)]
.
1−α
(10)

E[text(s.t, o.t)] = 1 −る．よって，n2 は枝刈りされる．つまり，Snr 2 に含まれるすべてのクエリの Top-k データおよび Safe Region を更新しない．

SQ-tree の根ノードからノードフィルタリングを実行することにより，Sg を効率的に得ることができる．
解の更新．フィルタリングによって得られた Sg に含まれる各
クエリ s に対して Top-k データおよび Safe Region を更新する．まず，s を発行したユーザに現在地を要求した後，各 Top-k
データに対するスコアを更新し，さらに，score(s, o) を計算する．score(s, o) < scorek (s) ならば，s の Top-k データを更新し，更新前に k 番目であったデータを ok+1 とする．一方，score(s, o) >= scorek (s) ならば，s の Top-k データは変化しな
い．しかし，s の Safe Region を再計算する必要があり，さらまた，s の Top-k データが更新されるために必要な |s.t ∩ o.t|の期待値 E[|s.t ∩ o.t|] は以下のように計算される．

E[|s.t ∩ o.t|] = ⌊E[text(s.t, o.t)] · |s.t|⌋.

(11)

ここで，データのキーワードの分布が時間により変化しないと仮定すると，Tnr と o.t の間で一致するキーワードの数の期待値

E[|Tnr ∩ o.t|] は，以下の式で与えられる．
E[|Tnr ∩ o.t|] = min(tmax ,∑ |Ow |i)|O|
w ∈T ri(12)nここで，Owi は wi を含むデータの集合である．新たにデータ1（注 1）：E[dist(n, o.p)] = S∫∫
R2

dist(n, o.p)dxdy （S ：領域 R2 の面積）

o が生成されたとき，E[|Tnr ∩ o.t|] < E[|s.t ∩ o.t|] ならば，s が転置ファイル 𝐼𝑂

Kd-tree 𝐾

枝刈りされる可能性が大きい．よって，s がこの条件を満たす

頻出キーワード𝑜4場合，子ノードへ分配せず n で管理する．

SQ-tree のメンテナンス．クエリ s の Top-k データおよび Safe

𝑜2

𝑤2

𝑤3

𝑤4

…

𝑜1 , 𝑜2 , …

𝑜2 , 𝑜4𝑜3…

𝑜6

四分木 𝑄𝑤1

Region が更新されたとき，s を管理するノードの情報が変化する可能性があるため，SQ-tree を更新する必要がある．更新後

𝑤1

𝑜2 , 𝑜3 , …

𝑜1

𝑜3

𝑜5

・・・

𝑜7
𝑜2

の Safe Region の重心を gnew とする．s を管理する n に対して，gnew ∈ n ならば，単純にノードに保存された情報を更新す

𝑜5

𝑜3 , 𝑜4

る．一方，gnew ∈/ n ならば，s を一旦 SQ-tree から取り除き，𝑜6

𝑜7: 葉ノード: 中継ノード

図 4: データのインデックスの例

更新後の Safe Region に基づいて SQ-tree に再度挿入する．

3. 3 データの削除に対する処理

定理 7 より，scorelb (s, i, onn ) >= score(s, obest ) ならば，正確あるデータ o′ が削除されたとき，o′ を Top-k データに含むク

性を失うことなく，|s.t ∩ o.t| < i を満たすデータを枝刈りでエリ集合 Se に対して，Top-k データおよび Safe Region を更きる．

新する必要がある．s ∈ Se の Top-k データおよび Safe Region

アルゴリズム 3 は，ok+1 を検索するアルゴリズムを示していを更新するため，s に対するスコアが k 番目および k + 1 番目でる．まず，Kd-tree を用いて，O\s.A の中で s.p に最も近いデー

あるデータ ok および ok+1 を検索する必要がある．ここで，あタを返す FindNearestObject(s.p, s.A) を実行し，onn を検索するデータ o が s の Top-k データであるとき，o は次の条件のいる．そして，暫定的に onn を ok+1 とする（1–2 行）．|s.t∩o.t| = i

ずれかを満たす：(1) o ∈ OkN N ，(2) o ∈ Os.t ．ここで，OkN Nの大きいデータが ok+1 となる可能性が大きいため，Os.t に含まは，s.p から近い k 個のデータ集合，Os.t は，s.t ∩ o.t =| ∅をれるデータを i の降順でチェックする．i > 1 のとき，|s.t∩o.t| = i

満たすデータ集合である．

を満たすデータ o ∈ Os.t に対して，CheckObject(s, o, ok+1 ) を実これらの条件を満たすデータを効率的に検索するため，提案

行する（7–9 行）．ここで，CheckObject(s, o, ok+1 ) は，o ∈/ s.A

アルゴリズムにおけるデータのインデックスでは，データの位

かつ score(s, o) < score(s, ok+1 ) ならば，o を ok+1 とする．一

置情報を管理する Kd-tree とデータのキーワード集合を管理す

方，i = 1 のとき，各クエリキーワード wi ∈ s.t に対して，

る転置ファイルを用いる．Kd-tree を用いて OkN N を効率的にwi が頻出キーワードである場合，CheckQtree(Qwi , s, ok+1 )検索でき，転置ファイルを用いて Os.t を効率的に検索できる．

を実行し，頻出キーワードでない場合，IO [wi ] に含まれる

しかし，あるキーワード wi ∈ s.t が多くのデータに含まれる場

すべてのデータに対して CheckObject(s, o, ok+1 ) を実行する

合，wi のポスティングリスト IO [wi ] に含まれるすべてのデー（10–16 行）．CheckQtree(Qwi , s, ok+1 ) は，四分木 Qwi に含タをチェックするのは多大な時間がかかる．この問題を解決す

ま れ る デ ー タ を s.p に 近 い 順 に チェック し ，o ∈/ s.A か つるため，文献 [9] と同様に，データのキーワードごとに位置情score(s, o) < score(s, ok+1 ) ならば，o を ok+1 とする．チェッ

報を管理する四分木を作成する．しかし，すべてのキーワード

ク済みでないデータのスコアが score(s, ok+1 ) を下回ることがに対して四分木を作成すると膨大なメモリコストが必要である．

なくなった場合，検索を終了する．

そのため，すべてのキーワードのうち，出現頻度が上位 x% 以
上のキーワードを頻出キーワードとし，頻出キーワード wi に

4. 評 価 実 験

対して四分木 Qwi を作成する．図 4 は，データのインデック

本章では，提案アルゴリズムの性能評価のために行った実スの一例を示しており，w1 および w2 が頻出キーワードである

験の結果を紹介する．本実験は，Windows 10 Pro，3.20GHz

ため，Qw1 および Qw2 を作成する．

Intel Core i7，および 64GB RAM を搭載した計算機で行い，

ここから，ok+1 を検索する方法を紹介する．
（ok を検索する必すべてのアルゴリズムは C++で実装した．

要がある場合，同様の方法で検索すればよい．
）まず，Top-k デー

4. 1 セッティング

タに含まれない各データ o ∈ O\s.A に対して，|s.t ∩ o.t| = i

本実験では，提案アルゴリズムのいくつかの機能を用いたならば，score(s, o) の下界値 scorelb (s, i, onn ) は以下の式で計手法：A-KIF，A-SQ-KI，および A-SQ-IQ との比較を行った．
ここで，A および SQ は，提案アルゴリズムにおける近似的な算される．

scorelb (s, i, onn ) = α · dist(s.p, onn .p) + (1 − α)(1 −

i
)
|s.t|
(13)

（Approximate）Safe Region および SQ-tree を示し，KIF は，
提案アルゴリズムにおけるデータのインデックス（Kd-tree ＋転置（Inverted）ファイル＋頻出（Frequent）キーワードに対

ここで，onn は，O\s.A に含まれるデータの中で s.p に最も近する四分木）を示す．さらに，KI は，Kd-tree および転置ファいデータである．また，これまでにチェックされたデータの中イルのみを用いたデータのインデックス，IQ は，IR-tree のよで，最もスコアの良いデータを暫定の ok+1 とすると，以下のうに四分木と転置ファイルを組み合わせた木構造である IQ-tree

定理が成り立つ．

を示す．つまり，A-KIF は，近似的な Safe Region および KIF

定理 7. scorelb (s, i, onn ) >== score(s, ok+1 ) ならば，|s.t ∩ o.t| <i を満たすデータ o ∈ Os.t \s.A は ok+1 になり得ない．

のみを用いた手法であり，新たにデータが生成されたとき，すべてのクエリの Top-k データの更新をチェックする．A-SQ-KI

表 1: データセットの詳細

Algorithm 3: RetrieveObject(s)Input: s, O

Twitter1

onn ← FindNearestObject(s.p, s.A)2

ok+1 ← onn

3

for ∀o ∈ Os.t do
Compute |s.t ∩ o.t| by using Inverted file IO

5i ← |s.t|6

while i > 0 ∧ scorelb (s, i, onn ) < score(s, ok+1 ) do

7
8

10
11

for ∀o ∈ Os.t such that |s.t ∩ o.t| = i do
CheckObject(s, o, ok+1 )29.6

パラメータの設定

値

s.k の最大値，kmax

5, 10, 15, 20

クエリの数，|S| [×106 ]0.25, 0.5, 0.75, 1

データの生成頻度，fg (/tm)

1, 5, 10, 20

データの削除頻度，fe (/tm)

1, 5, 10, 20

else
for ∀wi ∈ s.t do

12

if wi is a frequent keyword then13

CheckQtree(Qwi , s, ok+1 )

14

4.6

表 2: パラメータの設定

if i > 1 then

9

Yelp

292,193 836,680

1 つのデータに含まれるキーワードの数の平均

else
for ∀o ∈ IO [wi ] do

15

CheckObject(s, o, ok+1 )16LSR (Twitter)
LSR (Yelp)

102
更新時間 [ms]4キーワードの数

ASR (Twitter)
ASR (Yelp)

101
100
10-1
10-2
10-3

5

10

15

20

kmax

18

i←i−1

図 5: LSR と ASR の計算時間の比較

return ok+1

は，頻出キーワードに対して四分木を作成しないため，アルゴを実行する．A-SQ-IQ は，IQ-tree を用いて ok+1 を検索する．
データセット．本実験では，生成されるデータとして Twitter [1]のツイートおよび Yelp（注 2）のレビューを用いた．表 1 に，デー
タセットの詳細を示す．各クエリは，1 つのツイートまたはレ
ビュー中に現れる単語の中から，tmax 個以下の単語をランダムに選び，クエリのキーワード集合とする．また，ユーザのトラ
ジェクトリとして，ATC（注 3） および OSM（注 4）を用いた．各ト
ラジェクトリは，1 秒を 1 タイムスタンプ（tm）として，100

更新時間 [ms]リズム 3 において CheckQtree を実行せず，常に CheckObject

104

Proposed (Twitter)

A-KIF (Twitter)
105

Proposed (Yelp)

更新時間 [ms]

17

103
102
101

0.25

0.5
0.75
|S| [×106]

1

A-KIF (Yelp)

104
103
102
101
0.25

(a) ATC

0.5
0.75|S| [×106]

1(b) OSM

図 6: |S| の影響
りの各クエリの Top-k データの更新が完了するまでの平均時間[msec]）の結果を示す．

個の連続する点を含むトラジェクトリを抽出し，ユーザのトラ|S| の影響．図 6 に |S| を変えたときの結果を示す．提案アルジェクトリとした．

ゴリズムは A-KIF と比較して，高速に Top-k データを更新でパラメータ．表 2 に，本実験で用いたパラメータを示す．太字で表されている値はデフォルトの値である．また，tmax = 5 および x = 1 とし，Twitter（Yelp）を用いたとき m = 1000(100)とした．さらに，k は 1 から kmax の間の一様乱数とし，α は0 から 1 の間の一様乱数とした．実験は，データが 1,000,000個発生した時点から開始する．

4. 2 評 価 結 果
LSR と ASR の計算時間の比較．図 5 に LSR および ASR のきることが分かる．また，|S| の増加に伴い，両手法の更新時間の差が大きくなることが分かる．新たにデータが生成された
とき，A-KIF は常にすべてのクエリの Top-k データの更新をチェックするのに対し，提案アルゴリズムは，Top-k データが変化する可能性のあるクエリを限定し，それらのみ Top-k デー
タの更新をチェックする．その結果，|S| の増加に伴い Top-k
データの更新をチェックするクエリの数の差が大きくなるため，
更新時間の差が大きくなる．

平均計算時間の結果を示す．ASR は，LSR と比較して，非常にfg の影響．図 7 にデータの生成頻度 fg を変えたときの結果を高速に Safe Region を計算できることが分かる．これは，ASR示す．fg の増加に伴い，両手法において更新時間が大きくなる

は，Dominant Region およびそれらの共通部分を計算するこことが分かる．また，提案アルゴリズムは A-KIF と比較して，となく，Safe Region を計算できるためである．

高速に Top-k データを更新できることが分かる．両手法は新た

ここから，各アルゴリズムにおける平均更新時間（tm あたに発生するデータに対して 1 つずつ処理を行うため，データの生成に対する更新時間は，線形に増加する．また，fg が増加す
ると，ユーザが自身の Safe Region の外に出る可能性が大きく（注 2）：http://www.yelp.com/dataset_challenge（注 3）：http://www.irc.atr.jp/crest2010\_HRI/ATC\_dataset/（注 4）：https://planet.openstreetmap.org/gps/

なり，Top-k データおよび Safe Region の再計算の頻度が増加
する．以上の理由から，fg が増加すると，更新時間が増加する．

Proposed (Twitter)

A-KIF (Twitter)
104

Proposed (Yelp)

更新時間 [ms]更新時間 [ms]

104
103
102
101

0

5

10
fg

15

では，新たに発生したデータが Safe Region に影響を与える可103

能性のある領域である Impact Region を用いて，クエリの解102をモニタリングする手法を提案している．しかし，これらの研

101

20

をモニタリングする問題に取り組んでいる．例えば，文献 [3]A-KIF (Yelp)

究はレンジクエリを対象としており，Top-k クエリを対象とし0(a) ATC

5

10
fg

15

20

た本研究とは問題が異なる．

6. ま と め(b) OSM

図 7: fg の影響

近年，Pub/Sub モデルに基づくアプリケーションやムービ
Proposed (Twitter)

A-SQ-KI (Twitter)

Proposed (Yelp)

A-SQ-KI (Yelp)

A-SQ-IQ (Yelp)

更新時間 [ms]更新時間 [ms]

104
103
102
101

0

5

10
fe

15

20

ングクエリへの関心が高まっている．本稿では，Pub/Sub 環

A-SQ-IQ (Twitter)104

境において，移動するユーザ（ムービングクエリ）に対する

103

Top-k データをモニタリングする問題に取り組んだ．各クエリの Top-k データを効率的にモニタリングするため，クエリを

102
101

Safe Regin に基づいて管理し，新たに生成されたデータによ0(a) ATC

5

10
fe

15

20

(b) OSM

図 8: fe の影響

り，Top-k データが変化する可能性のあるクエリを効率的に限定する新たな四分木（SQ-tree）を提案した．また，データが削除されたとき，または，ユーザが Safe Region の外に出たときに，新たに Top-k データとなるデータを効率的に検索するアfe の影響．図 8 にデータの削除頻度 fe を変えたときの結果

ルゴリズムを提案した．さらに，近似的な Safe Region を高速を示す．提案アルゴリズムはその他の手法と比較して，高速にに計算する手法を提案した．評価実験の結果から，提案アルゴTop-k データを更新できることが分かる．また，fe の増加に伴

リズムの有効性を確認した．

い，各手法において更新時間が大きくなることが分かる．fe が増加すると，よりスコアの大きいデータが Top-k データとなるため，新たに生成されたデータが Top-k データとなる可能性
が大きくなり，また，データの削除による Top-k データおよびSafe Region の更新の頻度が増加する．その結果，更新時間が大きくなる．

5. 関 連 研 究
本章では，Pub/Sub 環境における Top-k データモニタリン
グに関する従来研究，およびムービングクエリに関する従来研究について説明する．

Pub/Sub 環境における Top-k データモニタリング．文献[1], [5] において，Pub/Sub 環境における Top-k データモニタ
リング手法が提案されている．これらの研究では，四分木を用いてクエリを管理し，データの生成に対して Top-k データの更新を高速に行う．しかし，これらの研究では，クエリの位置は固定であることを想定しており，ユーザの移動に対応できない．
ムービングクエリ．これまでに多くの研究がムービングクエリの解をモニタリングする問題に取り組んでいる．文献 [4], [7] では，ムービング Top-k クエリの解を効率的にモニタリングするアルゴリズムが提案されている．具体的には，クエリが移動しても，Top-k データが変化することのない領域である Safe

Region を計算することで，クエリが Safe Region の外に出た
場合のみ Top-k データの更新を行う．しかし，これらの研究はストリームデータを対象としておらず，新たにデータが生成された場合，Top-k データおよび Safe Region を再計算する必要がある．これは，非常に大きな計算コストが必要である．文献 [3], [6] では，Pub/Sub 環境においてムービングクエリの解謝辞．本研究の一部は，文部科学省科学研究費補助金・基盤研究 (A)(JP26240013)，(A)(18H04095)，および基盤研究(B)(T17KT0082a) の研究助成によるものである．ここに記して謝意を表す．
文

献[1] Chen, L., Cong, G., Cao, X., Tan, K.L.: Temporal spatialkeyword top-k publish/subscribe. In: ICDE. pp. 255–266(2015)[2] Chen, L., Cong, G., Jensen, C.S., Wu, D.: Spatial keyword
query processing: an experimental evaluation. PVLDB 6(3),217–228 (2013)[3] Guo, L., Zhang, D., Li, G., Tan, K.L., Bao, Z.: Locationaware pub/sub system: When continuous moving queries
meet dynamic event streams. In: SIGMOD. pp. 843–857(2015)[4] Huang, W., Li, G., Tan, K.L., Feng, J.: Eﬃcient safe-region
construction for moving top-k spatial keyword queries. In:
CIKM. pp. 932–941 (2012)[5] Wang, X., Zhang, W., Zhang, Y., Lin, X., Huang, Z.: Top-k
spatial-keyword publish/subscribe over sliding window. The
VLDB Journal 26(3), 301–326 (2017)[6] Wang, X., Zhang, Y., Zhang, W., Lin, X., Wang, W.: Aptree: eﬃciently support location-aware publish/subscribe.
The VLDB Journal 24(6), 823–848 (2015)[7] Wu, D., Yiu, M.L., Jensen, C.S., Cong, G.: Eﬃcient continuously moving top-k spatial keyword query processing. In:
ICDE. pp. 541–552 (2011)[8] Žalik, B.: Two eﬃcient algorithms for determining intersection points between simple polygons. Computers & Geosciences 26(2), 137–151 (2000)[9] Zhang, C., Zhang, Y., Zhang, W., Lin, X.: Inverted linear quadtree: Eﬃcient top k spatial keyword search. TKDE
28(7), 1706–1721 (2016)[10] 西尾俊哉, 天方大地, 原 隆浩: 位置・キーワードに基づくムー
ビング top-k パブリッシュ/サブスクライブ. 第 10 回データ工学と情報マネジメントに関するフォーラム（DEIM フォーラム2018）(2018)