DEIM Forum 2016 D3-3

位置，キーワードおよびソーシャル関係に基づく
Top-k パブリッシュ/サブスクライブ
西尾

俊哉†

天方

大地††

原

隆浩††

西尾章治郎††† 大阪大学工学部電子情報工学科 〒 565–0871 大阪府吹田市山田丘 1-5†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{nishio.syunya,amagata.daichi,hara,nishio}@ist.osaka-u.ac.jp
あらまし 近年，多くのアプリケーションでは，PoI(Point of Interest) がパブリッシュ/サブスクライブモデルに基づいてデータを発信しており，ユーザは生成されたデータの中から自身が興味を持つもののみを取得する．また，位置情報サービスやソーシャルネットワークサービスの普及により，位置やキーワード，ソーシャル関係を用いた検索への関心が高まっている．本研究では，パブリッシュ/サブスクライブモデルで生成されたデータから，ユーザにとって有用な上位 k 個のデータをモニタリングする問題に取り組む．この上位 k 個のデータを収集する際，PoI の位置，指定したキーワードとの一致度，およびデータを生成した PoI とのソーシャル関係からデータのスコアを計算する．データが発生した際に，上位 k 個に含まれるデータであるかどうかを全てのユーザ (Top-k クエリ) に対して計算する単純な方法は，多数のクエリが存在する環境に対応できない．この問題を解決するため，クエリを四分木により管理し，発生したデータが上位 k 個となり得るクエリにのみアクセスするアルゴリズムを提案する．実データを用いた実験により，提案アルゴリズムの有効性を示す．
キーワード

パブリッシュ/サブスクライブ，Top-k クエリ

1. は じ め に

𝑝1

スマートフォンやタブレットなどの GPS を利用可能な端末の普及に伴い，位置情報を考慮した検索が多くのアプリケー

𝑢1

ションにとって必要不可欠になっている [4] [9]．その一例とし

𝑢2て，位置依存ソーシャルサービスである Yelp や Foursquare な
どが挙げられる．これらのサービスでは，位置やキーワードに基づく検索をユーザに提供している．また，Twitter に代表され

𝑝2

る SNS の急速な発展により，ソーシャル関係を考慮した検索も

: PoI

𝑝3

𝑝4

: ユーザ

注目を集めている [7] [11]．例えば，Facebook [2] における “い図 1: ユーザと PoI とのソーシャル関係

いね” など，ユーザは興味のある PoI（Point of Interest）に対してソーシャル関係を持つ．この関係は，図 1 におけるユーザとPoI 間の辺として表現でき，図 1 はユーザ u1 および u2 のソーシャル関係のみを表現している．このとき，ユーザ u2 は PoI p1とソーシャル関係があるため，p1 が発信するデータを受信す

𝑝0
𝑝1

1
2

𝑤55

𝑤130

𝑢51

100

: PoI

…

データを受信できる．つまり，ソーシャル関係を考慮すること100…

信しやすくすることにより，u1 は既知でなかった興味に合う

𝑝50

𝑢50

50

…

で，ソーシャル関係を考慮し，p1 が発信するデータを u1 が受2…

のとき，p1 は u1 とソーシャル関係はないが，p1 は u2 とソー

𝑢0

1

…

似しており，二人のユーザの興味は類似しているといえる．こシャル関係があるため，u1 の興味に合う可能性は高い．そこ

𝑤0

データ

…

る．また，ユーザ u1 と u2 は，ソーシャル関係がある PoI が類

キーワード

: ユーザ

図 2: パブリッシュ/サブスクライブモデル

によって，あるユーザにとって既知でない興味に合うデータも検索可能になると同時に，PoI は広告配信などを効率化できる．
ここで，多くのアプリケーションでは，PoI は任意のユーザに向けてデータを提供し，ユーザは自身が興味を持つデータのみを受信するパブリッシュ/サブスクライブモデルに基づいている [5] [8] [10]．例えば，図 2 のように，PoI は受信者を指定せずにデータを送信する．送信されたデータはキーワードごとに分類され，キーワード w0 に興味があるユーザ u0 には，データ 1

および 2 が送信され，キーワード w55 に興味があるユーザ u50
および u51 には，データ 50 が送信される．このパブリッシュ/

𝑝2

𝑢0

サブスクライブモデルにおいて，ユーザの興味に合うデータを全て配信すると，あるユーザは膨大な量のデータを受信し，またあるユーザはデータをほとんど受信しないという状況が生じ

𝑝1
𝑝0

𝑢2

𝑢1

る可能性がある．そのため，ユーザにとって有用な上位 k 個のデータを検索する Top-k 検索が有用である [6]．また，このよう

𝑝4

𝑢3

𝑢6

𝑢4

な環境ではデータの生成は頻繁に行われるため，あるユーザに

: ユーザ

𝑝5

𝑝3

対する上位 k 個のデータは頻繁に変化する．

𝑢5

: PoI

𝑢7

本研究では，パブリッシュ/サブスクライブモデルで生成されたデータから，ユーザにとって有用な上位 k 個のデータをモ

図 3: ソーシャルグラフ

ニタリングする問題に取り組む．この Top-k クエリでは，PoIの位置，指定したキーワードとの一致度，およびデータを生成した PoI とのソーシャル関係からデータのスコアを計算する．
この Top-k クエリの解はユーザごとに異なるため，全てのユー
ザに対して評価を行う必要がある．しかし，ユーザが多く存在している場合，新しく生成されたデータが上位 k 個に含まれるドの集合 (qu .key)，および上位何個のデータを要求するかを指定する変数 (qu .k) を保持している．クエリ qu におけるデータ

o のスコア s(qu , o) は，式 (1) に従って計算され，スコアが小さいほど優れているものとする．

データであるかどうかを全てのユーザ (Top-k クエリ) に対して計算する単純な方法は，多大な時間がかかってしまう．これは，各ユーザに対する上位 k 個のデータを高速に更新できず，リア
ルタイム性を保証することが難しい．
この問題を解決するため，クエリを四分木 [12] により管理
し，生成されたデータが上位 k 個となり得るクエリにのみアクセスするアルゴリズムを提案する．四分木の各ノードには，そのノードで管理されているクエリを集約した情報を保存する．

s(qu , o) = dist(qu , o) + key(qu , o) + socio(qu , o)(1)

以下，dist(qu , o)，key(qu , o)，および socio(qu , o) を説明する．

dist(qu , o) は，式 (2) により，クエリとデータとのユークリッ
ド距離に基づいて計算される．

√
dist(qu , o) =そして，ノードに保存された情報から，生成されたデータが上(qu .locx − o.locx )2 + (qu .locy − o.locy )2
M AXloc(2)

位 k 個のデータとなり得ない部分木を枝狩りし，アクセスする

MAXloc はユーザと PoI が存在しうる領域の最大距離であり，こクエリの数を削減する．これにより，データが生成されたとき，れによりスコアを [0, 1] の値に正規化している．

各ユーザに対する上位 k 個のデータを高速に更新できる．そのkey(qu , o) は，式 (3) により，クエリのキーワードとデータ

結果，単純なアルゴリズムよりもアクセスするクエリの数を削のキーワードの一致度を F 値を用いて計算し，その一致度を 1減しつつ，正しい解に更新できる．実データを用いた実験の結から減算することにより計算される．

果から，提案アルゴリズムの有効性を確認した．

key(qu , o) = 1 −以下では，2 章で本稿の問題を定義する．3 章で提案アルゴ
リズムについて説明し，4 章で実データを用いた実験の結果を示す．そして，5 章で関連研究について述べ，最後に 6 章で本稿をまとめる．

2|qu .key ∩ o.key||qu .key| + |o.key|(3)

例えば，qu .key = {w1 ，w2 } で，o.key = {w2 , w3 , w4 } である
とき，key(qu , o) = 1 − 2×1= 0.6 となる．
2+3

socio(qu , o) はクエリを発行したユーザとデータを生成した

2. 問 題 定 義
PoI の集合を P ，全ての PoI が生成する全てのデータの集合
を O，発行された全てのクエリの集合を Q とする．

2. 1 データモデル
ある PoI が生成するデータ o ∈ O は，o の id(o.id)，o を生成した PoI の id (o.pid)，データの位置情報 (o.loc)，およびキーワード集合 (o.key) を保持している．o.loc は o を生成した PoIの位置とし，PoI の位置情報は緯度と経度によって表される 2次元平面上の点とする．本研究では，データのキーワード集合の更新はないものとする．

PoI とのソーシャル関係のスコアを 1 から減算することにより計算される．今回想定する環境として，ユーザは PoI に Facebook
における “いいね” のように，興味のある PoI に対してソーシャル関係を持つ．この関係は，ソーシャルグラフを用いて，図 3のように表現できる．丸がユーザ，四角が PoI を表し，ソーシャ
ル関係はグラフにおける辺として表現できる．ここで，ソーシャルグラフの辺の集合を E とする．また，eu,pi をユーザ uと PoI pi 間の辺とする．本研究では，ユーザと PoI の関係を値化し，ソーシャルスコアを計算する．これは，式 (4) により計算される．

2. 2 Top-k モニタリング
あるユーザ u が発行するクエリ qu ∈ Q は，qu の id(qu .id)，

u が指定する位置情報 (qu .loc)，1 つ以上の任意の数のキーワー

socio(qu , o) = 0(∃eu,p ∈ E)

 1 − max 2|Pu ∩Pu′ ||Pu |+|Pu′ |(∄eu,p ∈ E)

(4)

ここで，p は o を生成した PoI である．また，Pu = {∀p′ ∈P |∃eu,p′ ∈ E} で あ り，Pu′ = {∀p′ ∈ P |(∃eu′ ,p ∈ E) ∧𝑞0(∃eu′ ,p′ ∈ E)} である．つまり，∄eu,p ∈ E である場合，1から減算されている値は，p について，∃eu′ ,p ∈ E であるユー
ザ u′ と u との PoI 間の辺の一致度の最大値である．
例として，図 3 における u0 と p0 および u1 と p4 のソーシャ
ルスコアを考える．u0 と p0 は ∃eu,p ∈ E であるため，ソーシャルスコアは 0 である．次に，u1 と p4 は ∄eu,p ∈ E である．p4 と ∃eu,p ∈ E であるユーザは u2 ，u3 ，u4 および u6 で

1

NW

NE

SW

SE

NW

2
𝑞1

13

NE

SE

SW

3

2

4

14
𝑞3

𝑞2

15

1

16

: クエリ

4

(a)

(b)

13

14

15

16

(c)

図 4: 四分木の表現方法あるため，それぞれのユーザとの PoI 間の辺の一致度を計算する．u1 と ∃eu,p ∈ E である PoI は p1 および p2 であり，u2 と∃eu,p ∈ E である PoI は p1 ，p2 ，および p4 であるため，u1 とu2 との PoI 間の辺の一致度は， 2×2= 0.8 となる．同様にし
2+3て，u3 ，u4 ，および u6 についても一致度を計算すると，u1 とu3 との一致度は 0，u1 と u4 との一致度は 0.4，また，u1 と u6との一致度は 0 となる．よって，u1 と p4 のソーシャルスコア
は 1 − max{0.8, 0, 0.4, 0} = 0.2 となる．
ここで，実際の環境ではソーシャル関係の更新が考えられる．
この更新が起きると socio(qu , o) が変化する可能性がある．しかし，本研究ではソーシャル関係の更新は考えないものとし，更新が起きた場合においても既に計算済みの socio(qu , o) はその値を利用するといった方針をとる．

2. 3 ベースラインアルゴリズム
ベースラインとなるアルゴリズムは，データが生成された際，全てのクエリにアクセスし，データのスコアを計算する．また，クエリが管理している k 番目のデータのスコアと比較し，新たに生成されたデータが，そのクエリにおいて Top-k データになるかを計算する．クエリが管理している k 番目のデータのスコアよりも新たに生成されたデータのスコアの方が小さければ，生成されたデータと k 番目のデータを置き換える．
このアルゴリズムでは，Top-k データが更新されないクエリにもアクセスし，データのスコアを計算する．そのため，クエリが大量に存在している場合，解の更新に多大な時間がかかってしまう．これは，各クエリの上位 k 個のデータを高速に更新できず，リアルタイム性を保証することが難しい．そこで，アクセスするクエリの数を削減しつつ，かつ，正確に解を更新するアルゴリズムを提案する．

3. 提案アルゴリズム
ベースラインアルゴリズムでは，データが生成された際，全てのクエリにアクセスするため，解の更新に多大な時間がかかる．しかし，データが新たに生成されたとき，位置およびキー
ワードのスコアの計算は生成されたデータに依存し，異なる PoIから生成されたデータであっても，PoI 同士の位置が近く，似たキーワード集合を持つデータであれば，位置およびキーワー
ドのスコアは近い値となる．また，ソーシャルスコアはユーザと PoI の関係のみに依存し，同じ PoI から生成されたデータに対するソーシャルスコアはデータごとに変化しない．
そこで，クエリの位置情報に基づいて，クエリを四分木で管理し，各ノードにはそのノードに含まれるクエリの id，キー

ワード集合，および k 番目のデータのスコアを集約した情報を保存する．四分木の構築の際，分割が終了したノードに対して，ノードの id，そのノードに含まれるクエリの id，および根ノードからそのノードまでの経路を表す数字列をノードリスト (LN )に保存する．また，四分木が構築されると，各 PoI pi に対応するソーシャルスコアリスト (Liss ) を作成する．Liss は，LN に含まれるノードごとに，ノード id およびそのノードに含まれるクエリのソーシャルスコアの最小値を保存したものである．
データが生成されると，データを生成した PoI の Lss と LN を組み合わせて，どのクエリにアクセスすべきかをチェックするために用いるテーブル T を作成する．そして，四分木の根ノー
ドから順に，ノードに保存された情報とデータの位置情報およびキーワード集合から，生成されたデータが上位 k 個となり得るためのソーシャルスコアの閾値を計算する．T から求められるノードのソーシャルスコアをこの閾値と比較することにより，生成されたデータが上位 k 個となり得ない部分木を枝狩りする．
これにより，アクセスするクエリの数を削減できる．
まず，3.1 節において，クエリを管理する四分木の構築方法を紹介する．次に，3.2 節において，各 PoI に対応する Lss の作成方法を紹介する．最後に，3.3 節において，データが生成された時，クエリが管理している上位 k 個のデータを更新する
アルゴリズムを紹介する．

3. 1 四分木の構築
本研究の目的は，新たなデータが生成された際，クエリが管理している上位 k 個のデータが更新されることの無いクエリにアクセスする数を削減することにより，解の更新の高速化をはかることである．そこで，クエリを四分木を用いて管理する．
四分木は，各内部ノードが 4 個までの子ノードを持つ木構造である．さらに，線形四分木を用いることにより，各ノードに対し，根ノードから自身のノードまでの経路を計算できる．2 次
元平面で四分木のノードの分割を表現するため，図 4 のように表現する．図 4a に示すように，ノードを分割した際，分割されたノードはそれぞれ，NW，NE，SW，および SE と名付けられるとする．例えば，図 4b のように，4 つのクエリが存在し，領域が分割されたとする．この場合，四分木の構造は，図 4cのような木構造をとっている．図 4c に示すように，本稿では，
葉ノードと中継ノードを表現するために四角と丸を用い，クエリが含まれる葉ノードは黒四角とする．
ここから，提案アルゴリズムにおける四分木の構築方法を紹

1𝑞0{𝑤0 , 𝑤1 }

13

14

15

4

𝑞4 {𝑤0 , 𝑤2 }

16

𝑞5
{𝑤0 }

𝑞6
{𝑤2 , 𝑤3 , 𝑤4 }ノードid(6,3)(7,3)
𝑤0 , 𝑤1 , 𝑤2 , 𝑤3 , 𝑤4

𝑞2
{𝑤1 , 𝑤3 }𝑞1
{𝑤1 , 𝑤2 }
𝑞3
{𝑤2 }

0

2

1

3

2

4

(3,3)(4,3)(5,3)
𝑤0 , 𝑤2

𝑞7 {𝑤0 , 𝑤1 }

13

14

15

16

ソーシャル
スコア

ノードid

ソーシャル
スコア

1

0

1

0.6

2

0.33

14

0.67

13

0.5

16

0

14

0

4

0

16

0

4

0.2

(a) p0 の L0ss(b) p3 の L3ss

図 6: ソーシャルスコアリストの例(a) 図 3 に基づく四分木

数字列

エリの id，および根ノードからそのノードまでの経路を表す数

1

0,1

0

字列 (ds) をノードリスト (LN ) に保存する．根ノードからその

2

2

1

13

3

02

14

4

12

16

5

32

1 を引いたものを 4 で除算した商が親ノードのノード id とな

4

6,7

3

り，余りが 0 ならば自身は親ノードの NW というように，余り

ノードid クエリid(b) LN

図 5: 四分木の構築 (m = 2) および LN

ノードまでの経路を表す数字列は，ノード id を用いて計算し，その結果を保存する．線形四分木では，自身のノード id からによって自身は親ノードの NW，NE，SW，および SE のいずれかであることが分かる．この計算を繰り返し行うことにより順に求められた余りを 4 進数の数字列として保存する．例えば，
ノード 14 では余りが 1，2 という順に求まるため，12 という数介する．四分木を構築する際，クエリがどのノードに含まれるかはクエリの位置情報のみに依存する．まず，全ての PoI が存在している領域を根ノードとする．本研究におけるクエリは，全ての PoI が存在している領域内の任意の点を検索点として用いるため，全てのクエリが根ノードに含まれる．次に変数 m を用意し，ノードに含まれるクエリの数が m 個を超える場合は，そのノードを分割し，クエリの位置情報に基づいて各ノードにクエリを振り分ける．分割されたノード内のクエリの数が m 個を超えていれば同じ操作を繰り返し行い，あるノードに含まれるクエリの数が m 個以下になるようにする．図 3 におけるユー
ザが，自身の現在地を検索点とし，何らかのキーワードを指定したクエリ q を発行したと仮定する．m = 2 の場合，図 5 に示す四分木が構築される．
各ノードには，そのノードに含まれるクエリの id，キーワー
ドの集合，およびクエリが管理している k 番目のデータのスコアを保存する．ここで，クエリ q が管理する k 番目のデータのスコアを q.scorek と表し，その初期値は 3 とする．データの生成によりクエリが管理している k 番目のデータが更新されると，そのクエリの情報を持つ全てのノードの情報が更新される．図 5 では，クエリの id およびそのクエリの q.scorek を（id，q.scorek ）と表している．ノード 4 には，クエリ q6 および q7 が含まれているため，それらの id，k 番目のデータのスコア，およびキーワードの集合が保存されている．ノード 3 には，自身の子ノードであるノード 13，14，15，および 16 に含まれるクエリ q3 ，q4 ，および q5 の id，k 番目のデータのスコア，およびキーワードの集合が保存されている．
四分木が構築される際，ノードに含まれるクエリの数が m 個以下となったノードは，ノードの id，そのノードに含まれるク字列を保存する．四分木の構築が完了すると，LN には，クエリが含まれる全ての葉ノード (図 4(c) における黒四角) のノー
ド id，そのノードに含まれるクエリの id，および経路を表す数
字列が保存されている．図 5 において，ノード 15 にはクエリが含まれていないため，LN を作成する際，ノード 15 は存在していないものとして扱う．

3. 2 ソーシャルスコアリスト
次に，各 PoI pi に対応するソーシャルスコアリスト Liss を作成する．これは，LN に保存された各ノードに対して，ノード id およびそのノードに含まれるクエリのソーシャルスコア
の中の最小値を保存したものである．具体的には，ノードに含まれている全てのクエリに対して，各 PoI とのソーシャルスコ
アを計算する．そして，計算したソーシャルスコアの中で最小のものを，そのノードのソーシャルスコアとして Liss に保存する．また，ソーシャルスコアは PoI ごとに異なるため PoI ごとに Lss を作成する．しかし，各 Lss に全てのノードのソーシャ
ルスコアを保持させる場合，管理コストが膨大になってしまう
ため，ソーシャルスコアが 1 となるノードのノード id およびソーシャルスコアは保存しない．
図 3 および図 5 をもとに p0 および p3 に対応する Liss を作成すると，図 6 のようになる．例えば，ノード 1 にはクエリ

q0 および q1 が含まれており，p0 のそれぞれのクエリに対するソーシャルスコアは 0 および 0.5 であるため，L0ss のノード 1のソーシャルスコアは 0 となる．また，p3 の q2 および q3 に対するソーシャルスコアは 1 であるため，L3ss はノード 2 およびノード 13 のノード id およびソーシャルスコアを保存しない．

3. 3 Top-k データの更新アルゴリズム
最後に，データが生成された時，クエリが管理している上位

Algorithm 1: Creating T

Algorithm 2: NodeCheck(T ,ss,node,depth,o,f irst,last)

Input: O ′ //A set of newly generated data

Input: T, ss, node, depth, o, f irst, last1for ∀o ∈ O ′ do

1

2

T ←ϕ

2

3

last ← the size of LN

34

ssr ← 1

4

5

j←1

5

6

for i = 1 to last do

789

ss ← 1
if LN [i].nid = Lo.pid[j].nid thenSS
ss ← Lo.pid[j].ssSS10

j ←j+1

11

if ssr > ss thenssr ← ss

12

13
14

T ← T ∪ < LN [i].nid, ss, LN [i].ds >NodeCheck(T ,ssr ,root-node,1,o,1,last)

6
7
8

たデータがどのクエリにアクセスすべきかをチェックするため

LN に保存された全てのノードに対して，ノード id，ノードのfor j = f irst to last do
if depth-th digit of T [j].ds = 0 then11

ssN W ← T [j].ss

12

if depth-th digit of T [j].ds = 1 then13

countN E ← countN E + 1

14

if ssN E > T [j].ss thenssN E ← T [j].ss
if depth-th digit of T [j].ds = 2 then17

countSW ← countSW + 1

18

if ssSW > T [j].ss thenssSW ← T [j].ss

20

if depth-th digit of T [j].ds = 3 then21

countSE ← countSE + 1

22

if ssSE > T [j].ss then23に用いるテーブル T を作成するアルゴリズムを示している．Tはデータを生成した PoI の Lss と LN を組み合わせて作成し，

else

countN W ← countN W + 1

19

セスするためのチェックを行う．アルゴリズム 1 は，生成されResultUpdate(q,o,T ,f irst)

if ssN W > T [j].ss then

た PoI の Lss ，および四分木を用いて，クエリが管理している
上位 k 個のデータが更新される可能性があるクエリのみにアクfor ∀q ∈ node.Q do

1016

T の作成．新しくデータが生成されると，LN ，データを生成し

if f irst = last //node is leaf-node then

9

15

k 個のデータを更新するアルゴリズムを説明する．

Calculate threshold
if threshold >= ss thenssSE ← T [j].ss

24depth ← depth + 1

25

if countN W > 0 then26

NodeCheck(T ,ssN W ,NW,depth,o,f irst,f irst + countN W − 1)

ノードのソーシャルスコアを得る際，データを生成した PoI の27

f irst ← f irst + countN W

Lss にそのノードが含まれている場合は Lss に保存されている

28

ソーシャルスコア，および経路を表す数字列を保存する．ある
if countN E > 0 then29

NodeCheck(T ,ssN E ,NE,depth,o,f irst,f irst + countN E − 1)のソーシャルスコアとする．(7-10 行)．同時に，T に保存され

30

f irst ← f irst + countN E

る最小のソーシャルスコアを計算し，根ノードのソーシャルス

31

コアとする．

32

NodeCheck(T ,ssSW ,SW,depth,o,f irst,f irst + countSW − 1)

ノードのチェック．T が作成され，根ノードのソーシャルスコ

33

f irst ← f irst + countSW

アが計算されると，NodeCheck(アルゴリズム 2) を用いて，根34ノードから順に，クエリにアクセスすべきかどうかを判断して35

ソーシャルスコアを，含まれていない場合は 1 を，そのノード

if countSW > 0 thenif countSE > 0 then
NodeCheck(T ,ssSE ,SE,depth,o,f irst,f irst + countSE − 1)いく．アクセスすべきかどうかの判断は，ノードに保存された情報とデータの位置情報およびキーワード集合から計算された，
生成されたデータが上位 k 個となり得るためのソーシャルスコ
アの閾値とノードのソーシャルスコアとの比較により行われる．

threshold = scoremax − dist(n, o) − key(n, o)(5)ノードのソーシャルスコアが閾値よりも大きい場合，チェック中のノードに含まれるクエリに対して新しく生成されたデータ

こ こ で ，scoremax は ，ノ ー ド n に 含 ま れ る ク エ リ の う ちが上位 k 個のデータとなる可能性が無いため，チェックを終了

q.scorek が最大のものである．dist(n, o) は，データの位置

しクエリにアクセスしない．四分木が構築される段階では，各とノード n の間の最小距離を MAXloc で割ったものである．

ノードのソーシャルスコアの閾値は −1 に初期化しておく．以

ただし，データの位置がノード n の範囲内に含まれる場合は

下では，あるノードにアクセスした際の具体的な処理について

dist(n, o) = 0 である．key(n, o) は，key(qu , o) を計算する場説明する．

合と異なり，式 (6) によって計算される．

まず，初めてアクセスしたノードは閾値が −1 であるため，閾値を計算する (1 行)．あるデータ o に対するノード n の閾値

threshold は式 (5) で計算される．

key(n, o) = 1 −2|n.key ∩ o.key||n.key ∩ o.key| + |o.key|(6)

ここで，n.key はノード n が保持しているキーワード集合である．つまり，key(n, o) は，n が保存しているキーワードのうち，

データが持つキーワードのみを n が保持していると仮定して，Algorithm 3: ResultUpdate(q,o,T ,f irst)

そのキーワードのみで一致度を計算する．

Input: q, o, T, f irst

上記により計算される dist(n, o) および key(n, o) は，チェッ1Calculate s(q, o)

ク中のノードに含まれる全てのクエリ qu における dist(qu , o)2

if s(q, o) < q.scorek thenおよび key(qu , o) が取り得る最小値となるため，あるクエリ qu′3

Update top-k data of q

4

N ← A set of nodes that are calculated by T [f irst].ds

5for ∀n ∈ N doの dist(qu′ , o) および key(qu′ , o) が dist(n, o) および key(n, o)より小さくなることはない．また，解の更新が起こるためには

6

Update q.scorek

クエリの k 番目のデータのスコアより，新しく発生したデータのスコアが小さくなければならない．そのため，ノードに保存
表 1: データセット

された q.scorek の最大値から dist(n, o) および key(n, o) を引Yelp

くことにより得られた閾値は，チェック中のノードに含まれる
クエリにおいて，解の更新が起きるためのソーシャルスコアの上界値であり，そのノードのソーシャルスコアが閾値よりも大きい場合，解の更新は起こりえない．

Brightkite

ユーザの数

366,715

50,687

PoI の数

60,785

772,631

チェックイン 1,521,160

1,072,965

例えば，図 5 において，q6 .scorek = 1.2 および q7 .scorek =0.8 であるとき，図 3 における p0 がデータ o を生成したとし，更新を行う．

o.key = {w1 ，w2 ，w5 } とする．この場合，図 5 におけるノード

解の更新．葉ノードにおいて解の更新が必要であると判断され4 をチェックしたとする．ノード 4 が保存している n.key = {w0

ると，ResultUpdate(アルゴリズム 3) を用いて，そのノードに，w1 ，w2 ，w3 ，w4 } と o.key = {w1 ，w2 ，w5 } との共通部分は w1

含まれる全てのクエリに対して，解の更新を行う．

および w2 である．このとき，ノード 4 が w1 および w2 のみ

まず，データのスコアを計算し，クエリの k 番目のデータのを保持していると仮定して，それらのキーワードとデータ o のスコアと比較する．新たに生成されたデータのスコアの方が小持つキーワードの一致度からノード 4 における key(·, o) を計さければ，生成されたデータと k 番目のデータを置き換える．

算する．この場合，key(·, o) = 1 − 2×2
2+3= 0.2 となる．また，提案アルゴリズムでは，Top-k データの置き換えが実行される

PoI p0 とノード 4 の距離のスコアが dist(n, o) = 0.4 であるとと，四分木に保存されている情報を更新する必要がある．置きする．このとき，新しく生成されたデータに対するノード 4 の換えが実行されたクエリを含むノードは，T に保存された現在

閾値は，max{1.2，0.8} − 0.4 − 0.2 = 0.6 となる．

の葉ノードの数字列から計算できる．計算で得られたノードに閾値が計算されると，その閾値とチェック中のノードのソー

対して Top-k データの置き換えが実行されたクエリの k 番目

シャルスコアが比較される (2 行)．閾値の方が小さい場合は，現のデータのスコアの情報を更新する (5-6 行)．アクセスが必要

在チェックしているノードに含まれるクエリにおいて，新しくな全てのクエリに対して解の更新が終了すると，一つのデータ生成されたデータが上位 k 個のデータとなる可能性が無いため，に対する処理が終了し，四分木の各ノードの閾値は初期値にリ自身を根とする部分木のチェックを終了し，チェックが終了しセットされる．これを新しく生成された全てのデータに対してていないノードのチェックに移る．閾値の方が大きければ，子実行する．

ノードをチェックしていく．まず，T に含まれる葉ノードであ提案アルゴリズムでは，与えられたデータが，あるクエリにり，チェック中のノード n を根とする部分木に含まれる葉ノー

おける上位 k 個のものになるかを，スコアの上界値を用いて計ドが，n の NW，NE，SW，および SE のどのノードの経路上に算している．四分木によりクエリを管理することにより，アク′存在するか計算する．ある葉ノードが n の経路上に存在する′とは，n からその葉ノードにアクセスする際に，n が中継ノードであることを意味している．この計算は数字列を用いて行い，子ノードの深さ (depth) の桁を参照することで計算できる．同時に，n の子ノード (NW，NE，SW，および SE) のソーシャル

セスするクエリの数を削減でき，高速に解の更新を行える．

4. 評 価 実 験
本章では，ベースラインアルゴリズムおよび提案アルゴリズ
ムの性能評価のために行った実験の結果を紹介する．

スコアを計算する (7-23 行)．そして，それらのうち，T に含ま

4. 1 セッティング

れる葉ノードである，もしくは子孫に T に含まれる葉ノードを本 実 験 は ，Windows 7，3.47GHz Intel Xeon CPU，お よ び

1 つ以上含むノードに対して，NW から順に同様のチェックを

192GB RAM を搭載した計算機で行い，全てのアルゴリズムは行っていく (25-35 行)．チェックしているノードが葉ノードの場

C++で実装した．

合，閾値の方が大きければ，新しいデータがクエリの上位 k 個

データセット．本実験では，2 つの実データ（Yelp [3] およびのデータとなる可能性があるため，解の更新を行う (3-5 行)．

Brightkite [1]）を使用した．表 1 にデータセットの詳細を示す．

先ほどの例の場合，ノード 4 は葉ノードであり，図 6 よりそれぞれのデータセットにおいて，PoI は位置情報を保持してノード 4 は L0ss に含まれるため，計算された閾値 (0.6) とノー

おり，ユーザと PoI のソーシャル関係はチェックイン情報を用い

ド 4 のソーシャルスコア (0.2) を比較すると，閾値の方が大きた．それぞれのデータセットはキーワードに関する情報を含んい．そのため，ノード 4 に含まれる全てのクエリに対して解の

表 2: パラメータの設定

5〜30

クエリの数の最大値，mTop-k の最大値，kmax

5〜30（10）

一度に発生するデータの数，d100〜1,000（100）

1.5

15

ベースライン

10

提案

5
0

1

ベースライン
提案

0.5

0
5

10

15

20

25

30

5

𝑘𝑚𝑎𝑥 (Yelp)

50,000〜350,000（50,000）(Yelp)

クエリの数，e

更新時間[sec]

値（デフォルト）

各ノードに含まれる

更新時間[sec]

パラメータ

20

5,000〜50,000（10,000）(Brightkite)

10

15

20

25

30

𝑘𝑚𝑎𝑥 (Brightkite)(a) Yelp(b) Brightkite

図 8: kmax の影響
0.35

2.6

2.4

提案
150

0.3

0.25
5

10

15

20

25

30

5

m(Yelp)

10

15

20

25

30

m(Brightkite)

提案

100

50

0

ベースライン
提案

10

5

0
100

(a) Yelp

15

ベースライン
更新時間[sec]

2.8

更新時間[sec]

提案

更新時間[sec]

更新時間[sec]

3

300

500

700

900

100

d(Yelp)(b) Brightkite

図 7: m の影響

300

500

700

900

d(Brightkite)(a) Yelp(b) Brightkite

図 9: d の影響でいないため，あるデータ o の o.key として，Yelp のレビュー

トのうち，いずれかを各データのキーワードとして用いた．
パラメータ．本実験で用いたパラメータを表 2 に示す．m のデフォルトの値は，各データセットにおいて最初に最適な値を求め，その値を使用した．ユーザは一人ひとつのクエリを発行するものとし，qu .loc は各データセットにおいて全ての PoI が存在する領域内の任意の点とした．qu .k は 1 から kmax の間でランダムな値を選び，qu .key はキーワードセットのいずれかを用

120

ベースライン
提案90

更新時間[sec]

トとした．このようにして作成した 60,634 個のキーワードセッ

更新時間[sec]から得られた 1〜5 個程度のキーワードを一つのキーワードセッ

60

30
0

ベースライン

6

提案

4
2
0

50

100 150 200 250 300 350

5 10 15 20 25 30 35 40 45 50e(Yelp)[K]e(Brightkite)[K](a) Yelp(b) Brightkite

千図 10: e の影響いた．

4. 2 評 価 結 果

りスコアの高いデータが Top-k データとなるため，提案アルゴ

本実験では，各アルゴリズムにおける更新時間：(1 度に発生

リズムではノードで計算される閾値が大きくなる．そのため，する全てのデータに対して解の更新が完了するまでの平均時間

枝狩りが起きにくくなり，更新時間が長くなる．

[sec]) の結果を示す．

d の影響．図 9 に d を変えたときの結果を示す．ベースライン

m の影響．図 7 に m を変えたときの結果を示す．m が小さい

アルゴリズムに比べて提案アルゴリズムの方が高速に解を更新と，1 つのノードに含まれるクエリの数が少なくなり四分木のしている．また，提案アルゴリズムでは，解の更新が起こり得

高さが高くなる．四分木の高さが高くなると，閾値を計算してないクエリにはアクセスしないため，ベースラインアルゴリズ比較を行う回数が多くなるため，更新時間が長くなる．m が大ムに比べて１つのデータに対する更新時間が短い．そのため，きくなると四分木の高さが低くなり更新時間は短くなるが，1一度に発生するデータの数が多くなると，どちらのアルゴリズ

つのノードに含まれるクエリの数が多くなり，ノードで計算さムでも更新時間が増加するが，一度に発生するデータの数が多れる閾値が大きくなる．閾値が大きくなると枝狩りが起きにく

いほど，提案アルゴリズムとベースラインアルゴリズムの更新

くなり，アクセスするクエリの数を削減できないため，m があ

時間の差が大きくなる．

る値よりも大きくなると再び更新時間が長くなる．以降，Yelp，e の影響．図 10 に e を変えたときの結果を示す．ベースライン

Brightkite ともに m = 10 とした．

アルゴリズムに比べて提案アルゴリズムの方が高速に解を更新

kmax の影響．図 8 に kmax を変えたときの結果を示す．まず，している．また，クエリの数が多くなると解の更新が起こりえベースラインアルゴリズムに比べて提案アルゴリズムの方が高ないクエリも多くなり，提案アルゴリズムでは，アクセスしな

速に解を更新している．また，ベースラインアルゴリズムは，いクエリが多くなる．そのため，クエリの数が多くなると，ど全てのクエリに対してスコアを計算するため，kmax によらずちらのアルゴリズムでも更新時間が増加するが，提案アルゴリ

一定時間で解を更新している．一方，kmax が大きくなると，よ

ズムはベースラインアルゴリズムよりも増加率が小さくなる．

これらの結果から，提案したアルゴリズムが効果的であること

ユーザにとって有用な上位 k 個のデータをモニタリングする問が示される．

題に取り組んだ．提案アルゴリズムでは，クエリを四分木によ5. 関 連 研 究

り管理し，発生したデータが上位 k 個となり得るクエリにのみアクセスすることにより，リアルタイムモニタリングを実現しパブリッシュ/サブスクライブ．これまでに様々な研究が位置情ている．評価実験の結果から，提案アルゴリズムの有効性を確報およびキーワードを考慮したパブリッシュ/サブスクライブの認した．

問題に取り組んでいる [5] [8] [10]．文献 [10] では，位置情報お本稿では，データの発生にのみ着目したが，データの削除がよびキーワードを考慮し，位置情報がクエリの指定する範囲に起きるアプリケーションも存在する．そのため，データの削除含まれ，キーワードがマッチするデータをモニタリングするクおよび 2. 2 節で述べたソーシャル関係の更新への対応が今後のエリの効率的な処理手法として，AP 木という新たなデータ構

課題としてあげられる．

造を提案している．AP 木は，コストモデルに基づき，位置情報

謝辞．本研究の一部は，文部科学省科学研究費補助金・基盤研究

およびキーワードによるノードの分割を効果的に行う木構造で(A)(26240013) および JST 国際科学技術共同研究推進事業（戦ある．しかし，この文献では Top-k 検索を考えておらず Top-k

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

パブリッシュ/サブスクライブの問題には適応できない．一方，

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

文献 [6] は，パブリッシュ/サブスクライブモデルで生成されたデータの中で，位置，キーワード，および時間に基づいて計算された Top-k クエリの解をモニタリングするためのアルゴリズ
ムを提案している．四分木の各セルにクエリごとのデータの更新が起こりうる範囲を保存し，各クエリの発行時間など，位置に依存しない情報を四分木とは別に保存している．データが発生すると，保存された情報からキーワードのスコアの閾値を計算し，条件を満たすクエリのみ解の更新を行う．しかし，本研
究では，Top-k を計算する際に時間ではなくソーシャル関係を用いる点，およびデータを生成する PoI ごとにソーシャル関係が変化し，各 PoI ごとに情報を保存する必要がある点から，このアルゴリズムを適用できない．
ソーシャル関係を考慮した検索．位置，キーワード，およびソーシャル関係を考慮した検索についての研究も行われている [7] [11]．文献 [11] では，上記の 3 つの属性に基づく Top-k 検索を効率的に行うインデックスとして，SNIR 木を提案している．SNIR 木の各ノードには，自身を根とする部分木に含まれるデータの位置情報とデータに興味のあるユーザを保存し，クエリが発行されると Top-k データになり得る部分を順に探索していく．しかし，本研究では，ソーシャル関係の定義が異なり，クエリを SNIR 木で管理した場合，各ノードでソーシャルスコ
アを計算できない．さらに，このデータ構造は Top-k データの更新に対応しておらず，更新を行うためには全てのデータを再検索する必要がある．同様に，文献 [7] では，データモニタリ
ングではなくスナップショットクエリを考えており，本稿の問題とは異なる．そのため，これらの文献で提案されているアルゴリズムを適用することはできない．

6. 終 わ り に
PoI(Point of Interest) からのパブリッシュ/サブスクライブモ
デルに基づいたデータの発信，および位置情報サービスやソー
シャルネットワークサービスの普及により，位置やキーワード，
ソーシャル関係を用いた検索への関心が高まっている．本稿では，パブリッシュ/サブスクライブモデルで生成されたデータの中から，位置，キーワード，およびソーシャル関係に基づき，

文

献[1] Brightkite dataset.
http://snap.stanford.edu/data/
loc-brightkite.html.
[2] Facebook. https://www.facebook.com/.
[3] Yelp academic dataset. http://www.yelp.com/dataset_challenge/.
[4] N. Armenatzoglou, S. Papadopoulos, and D. Papadias. A generalframework for geo-social query processing. PVLDB, 6(10):913–924,
2013.
[5] L. Chen, G. Cong, and X. Cao. An efficient query indexing mechanism for filtering geo-textual data. In SIGMOD, pages 749–760,
2013.
[6] L. Chen, G. Cong, X. Cao, and K.-L. Tan. Temporal spatial-keyword
top-k publish/subscribe. In ICDE, pages 255–266, 2015.
[7] G. J. Fakas. Geo-social keyword search. In SSTD, pages 431–449,
2015.
[8] G. Li, Y. Wang, T. Wang, and J. Feng. Location-aware publish/subscribe. In SIGKDD, pages 802–810, 2013.
[9] Z. Li, K. C. Lee, B. Zheng, W.-C. Lee, D. Lee, and X. Wang. Ir-tree:
An efficient index for geographic document search. IEEE TKDE,
pages 585–599, 2011.
[10] X. Wang, Y. Zhang, W. Zhang, X. Lin, and W. Wang. Ap-tree: Efficiently support continuous spatial-keyword queries over stream. In
ICDE, pages 1107–1118, 2015.
[11] D. Wu, Y. Li, B. Choi, and J. Xu. Social-aware top-k spatial keyword
search. In MDM, pages 235–244, 2014.
[12] C. Zhang, Y. Zhang, W. Zhang, and X. Lin. Inverted linear quadtree:
Efficient top k spatial keyword search. In ICDE, pages 901–912,
2013.