DEIM Forum 2017 E4-5

スライディングウィンドウ上での位置・キーワード・ソーシャル関係に基づく
Top-k パブリッシュ/サブスクライブ
西尾 俊哉†

天方 大地†

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

Pub/Sub，ソーシャルネットワーク，Top-k クエリ，スライディングウィンドウ

1. は じ め に

𝑝1
: PoI

スマートフォンやタブレットなどの GPS を利用可能な端末

: ユーザ

𝑢2

𝑢1

の普及に伴い，位置情報やキーワードに基づく検索が多くのアプリケーションにとって必要不可欠になっている [6], [9]．これらのアプリケーションの多くは，PoI からデータが与えられたとき，事前に登録された興味に基づいてユーザにデータを配信するパブリッシュ/サブスクライブ（Pub/Sub）モデルに

𝑝2

𝑝3

𝑝4

基づいている [2], [4]．この Pub/Sub モデルでは，データの生成は頻繁に行われるため，大量のデータの中から，ユーザの趣向に応じてデータの順位を決定し，ユーザにとって有用な上位

k 個のデータを検索する Top-k 検索が実用的である [2]．また，Facebook（注 1） や Twitter に代表される SNS の急速な発展により，ソーシャル関係を考慮した検索も注目を集めている [1], [7]．
具体的には，SNS におけるソーシャル関係を用いたソーシャル
フィルタリングによりユーザの嗜好を抽出し，ユーザの要求に合う検索が実現できる [3]．例えば，Facebook における “いいね” など，ユーザは興味のある PoI（Point of Interest）に対してソーシャル関係を持つ．この関係は，図 1 におけるユーザとPoI 間の辺として表現でき，図 1 はユーザ u1 および u2 のソーシャル関係を表現している．このとき，ユーザ u2 は PoI p1 とソーシャル関係があるため，p1 が発信するデータを受信する．

図 1: ユーザと PoI とのソーシャル関係
また，ユーザ u1 と u2 は，ソーシャル関係がある PoI が類似しているため，二人の嗜好は類似しているといえる．このとき，

p1 は u1 とソーシャル関係はないが，p1 は u2 とソーシャル関係があるため，u1 の嗜好に合う可能性は高い．そこで，ソーシャル関係を考慮し，p1 が発信するデータを u1 が受信しやす
くすることにより，u1 は既知でなかった嗜好に合うデータを受信できる．つまり，ソーシャル関係を考慮することにより，あるユーザにとって既知でない嗜好に合うデータも検索可能になると同時に，PoI は広告配信などを効率化できる．
本稿では，Pub/Sub モデルで生成されたデータから，ユー
ザにとって有用な上位 k 個のデータ（Top-k データ）をモニタリングする問題に取り組む．この Top-k クエリでは，PoI の位置，ユーザが指定したキーワードとの一致度，およびデータを（注 1）：https://www.facebook.com/

生成した PoI とのソーシャル関係からデータのスコアを計算する．さらに，最新のデータをユーザに提供するため，スライ

𝑝2

𝑢0

ディングウィンドウモデル [5] を適用する．システムには多数の Top-k クエリが登録されており，Top-k データはクエリごとに異なる．そのため，クエリが多く存在している場合，ウィン

𝑝1
𝑝0

𝑢2

𝑢1

ドウがスライド（データの生成および削除）した際に，全てのクエリに対して Top-k データの更新をチェックする単純な方法

𝑝4

𝑢3

𝑢6

𝑢4

は，多大な時間がかかってしまう．その結果，ウィンドウのス
ライドに対して，各ユーザの Top-k データを高速に更新でき

: ユーザ

𝑝5

𝑝3

𝑢5

: PoI

𝑢7

ず，リアルタイム性を保証することが難しい．
この問題を解決するため，クエリを四分木 [8] により管理し，

図 2: ソーシャルグラフ

生成されたデータが Top-k データとなり得るクエリにのみアクセスするアルゴリズムを提案する．ノードに保存された情報

るデータ o のスコアを計算し，スコアの最も良い k 個のデータから，生成されたデータが Top-k データとなり得ない部分木をを Top-k データとする．このスコアは，距離スコア，キーワー

枝刈りし，アクセスするクエリの数を削減する．さらに，各ク

ドスコア，およびソーシャルスコアに基づいて計算される．

エリに対して，後に Top-k データとなり得るデータ集合を保存しておく．上位 k 個に含まれるデータが削除されたとき，そのデータ集合を用いて Top-k データを更新し，不要なデータのア
クセス数を削減する．実データを用いた実験の結果から，提案
アルゴリズムの有効性を確認した．本稿は，文献 [10] において筆者らが取り組んだ問題に対して，スライディングウィンドウモデルを適用した拡張版である．
以下では，2 章で本稿の問題を定義する．3 章で提案アルゴ
リズムについて説明し，4 章で実データを用いた実験の結果を定義 2.2 (距離スコア dist(qu , o)). dist(qu , o) は，式（1）により定義される．

dist(qu , o) = 1 −d(qu .loc, o.loc)
M AXloc(1)d(qu .loc, o.loc) は，クエリとデータとのユークリッド距離，
MAXloc はユーザと PoI が存在しうる領域の最大距離であり，これによりスコアを [0, 1] の値に正規化している．その値を 1から引くことにより，距離が近いものほどスコアが大きくなる．

示す．5 章で関連研究について述べ，最後に 6 章で本稿のまと定義 2.3 (キーワードスコア key(qu , o)). key(qu , o) は，式（2）めについて述べる．

により定義される．

2. 予 備 知 識
PoI の集合を P ，全ての PoI が生成する全てのデータの集合
を O，発行された全てのクエリの集合を Q とする．PoI から生成されたデータのうち，最新のデータをユーザに提供するため，

key(qu , o) =2|qu .key ∩ o.key||qu .key| + |o.key|(2)

このスコアは，クエリのキーワードとデータのキーワードの一致度を F 値を用いて計算したものである．

スライディングウィンドウ W を用いる．本研究ではカウント

例 2.1. qu .key = {w1 , w2 } で，o.key = {w2 , w3 , w4 } である

ベースのスライディングウィンドウを用いる．

とき，key(qu , o) = 2×1= 0.4 となる．
2+3

定義 2.1 (スライディングウィンドウ). 大きさが |W | のカウンソーシャルスコア socio(qu , p) は，クエリを発行したユーザ

トベースのスライディングウィンドウには，直近に生成されたとデータ o を生成した PoI p とのソーシャル関係により計算さ|W | 個のデータが含まれる．

れる．本稿で想定する環境では，ユーザは，Facebook におけ

データモデル．ある PoI p が生成するデータ o ∈ O は，o のid（o.id），o を生成した PoI の id（o.pid），データの位置情報（o.loc），キーワード集合（o.key ），および生成時間（o.t）を保持している．o.loc は o を生成した PoI の位置とし，PoI の
位置情報は緯度と経度によって表される 2 次元平面上の点とする．データのキーワード集合は，そのデータを表現（説明）する “いいね” のように，興味のある PoI に対してソーシャル関係を持つ．この関係は，ソーシャルグラフを用いて図 2 のように表現できる．丸がユーザ，四角が PoI を表し，ソーシャル関
係はグラフにおける辺として表現できる．ここで，ソーシャル
グラフの辺の集合を E とする．また，eu,p をユーザ u と PoI p
間の辺とする．

るキーワードの集合（メタデータの一種）であり，更新はない

定義 2.4 (ソーシャルスコア socio(qu , p)). socio(qu , p) は，式ものとする [2], [5], [6]．

（3）により定義される．
 1
socio(qu , p) = max 2|Pu ∩Pu′ |クエリモデル．あるユーザ u が発行するクエリ qu ∈ Q は，quの id（qu .id），u が指定する位置情報（qu .loc），1 つ以上の任意の数のキーワードの集合（qu .key ），および上位何個のデー
タを要求するかを指定する変数（qu .k ）を保持している．
各クエリの Top-k データを決定するため，クエリ qu に対す|Pu |+|Pu′ |(eu,p ∈ E)
(eu,p ∈/ E)

(3)

ここで，Pu = {∀p′ ∈ P |∃eu,p′ ∈ E} であり，Pu′ = {∀p′ ∈P |(∃eu′ ,p ∈ E) ∧ (∃eu′ ,p′ ∈ E)} である．

つまり，eu,p ∈/ E である場合，ソーシャルスコアは，p につ

クエリは事前にシステムに登録されているものとし [2], [6]，四′いて，eu′ ,p ∈ E であるユーザ u と u との PoI 間の辺の一致度

分木の構築およびソーシャルスコアリストの作成はオフライン

を F 値を用いて計算した値の最大値である．

で行われる．

例 2.2. 例 え ば ，図 2 に お い て p0 が o を 生 成 し た 場 合 ，

eu0 ,p0 ∈ E であるため，socio(qu0 , p0 ) = 1 である．次に，p4 が o を生成した場合の socio(qu1 , p4 ) について考える．ここで，eu1 ,p4 ∈/ E である．p4 との辺が存在するユーザは u2 ，u3 ，u4 ，および u6 であるため，それぞれのユーザとの PoI間の辺の一致度を計算する．u1 との辺が存在する PoI は p1
および p2 であり，u2 との辺が存在する PoI は p1 ，p2 ，および p4 であるため，u1 と u2 との PoI 間の辺の一致度は，
2×2= 0.8 となる．同様にして，u3 ，u4 ，および u6 について
2+3も一致度を計算すると，u1 と u3 との一致度は 0，u1 と u4 との一致度は 0.4，また，u1 と u6 との一致度は 0 となる．よって，socio(qu1 , p4 ) = max{0.8, 0, 0.4, 0} = 0.8 となる．

データが生成されると，そのデータのスコアが j 番目のデー
タのスコア以上となる可能性があるクエリにのみアクセスし，

k-スカイバンドを更新するためのチェックを行う．まず，データを生成した PoI の Lss と LN を組み合わせて，チェックする
ノードのソーシャルスコアを得るために用いるソーシャルスコ
アテーブル Tss を作成する．そして，四分木の根ノードから順に，ノードに保存された情報，データの位置情報とキーワード
集合，および Tss から，スコアの上界値を計算する．この上界値を用いて，k-スカイバンドの更新が不要なクエリへのアクセスを削減する．また，あるクエリの Top-k データに含まれるデータが削除されたとき，そのクエリの k-スカイバンドを用いて Top-k データを更新する．
まず，3.1 節において，提案アルゴリズムで適用する k-スカ

ここで，実際の環境ではソーシャル関係の更新（辺の追加おイバンドを説明する．次に，3.2 節において，クエリを管理す

よび削除）が発生することが考えられる．この更新が起きるとる四分木の構築方法を紹介し，3.3 節において，各 PoI に対応

socio(qu , p) が変化する可能性がある．しかし，本研究ではソーする Lss の作成方法を紹介する．最後に，3.4 節において，ウィシャル関係の更新は考えないものとし，更新が起きた場合におンドウのスライドに対して，各クエリの Top-k データを更新すいても既に計算済みの socio(qu , p) の値を利用するという方針

るアルゴリズムを紹介する．

をとる．

3. 1 k-スカイバンド

定義 2.5 (スコア関数). クエリ qu に対するデータ o のスコア

s(qu , o) は，式（4）により定義される．
s(qu , o) = dist(qu , o) + key(qu , o) + socio(qu , p)

ウィンドウのスライドにより，あるクエリの Top-k データに含まれるデータが削除されたとき，Top-k データを高速に更新するため k-スカイバンドを用いる．以下に，支配および k-ス(4)

スコアは大きいほど優れているものとする．
問題定義．多数のクエリおよびデータが与えられたとき，W 内

カイバンドを定義する．
定義 3.1 (支配). あるクエリ qu に対して，データ o1 がデータ

o2 に支配されるとき，s(qu , o1 ) <= s(qu , o2 ) かつ o1 .t < o2 .t を満たす．

のデータに対して，各クエリの Top-k データをリアルタイムにモニタリングする．

定義 3.2 (k-スカイバンド). あるクエリに対する k-スカイバン
ドは，W 内のデータにおいて，支配されるデータが k より少3. 提案アルゴリズム

ないデータの集合である．

データが新たに生成されたとき，位置およびキーワードに基あるクエリに対する k-スカイバンドとは，W 内のデータのづくスコアの計算は生成されたデータに依存し，異なる PoI か

うち，古いデータが削除されたとき，Top-k データとなり得る

ら生成されたデータであっても，PoI 同士の位置が近く，似たデータの集合である．また，あるクエリにおける Top-k データ

キーワード集合を持つデータであれば，位置およびキーワー

は，k-スカイバンドに含まれるデータのうちスコアの大きい上ドに関するスコアは近い値となる．また，ソーシャルスコアは位 k 個のデータである [5]．提案アルゴリズムでは，スコアがユーザと PoI の関係のみに依存し，同じ PoI から生成されたj （j >= k）番目のデータのスコアより大きくなる可能性のあるデータに対するソーシャルスコアはデータごとに変化しない．

データでのみ，k-スカイバンドの更新を行う．以降，提案アルそこで，クエリの位置情報に基づいてクエリを四分木で管理ゴリズムにおけるクエリ qu の Top-k データを qu .D ，k-スカイ

し，各ノードにはそのノードに含まれるクエリの id，キーワー

バンドを qu .S とする．また，qu .S に含まれるデータ o におい

ド集合，および j（j >= k）番目のデータのスコアを集約した情報を保存する．四分木の構築の際，分割が終了したノードに対て，o を支配するデータの数を o.dom と表す．

3. 2 四分木の構築

して，ノードの id，そのノードに含まれるクエリの id，および提案アルゴリズムでは，クエリを線形四分木を用いて管理す

根ノードからそのノードまでの経路を表す数字列をノードリス

る．四分木は，各ノードが 4 個までの子ノードを持つ木構造でト（LN ）に保存する．四分木を構築した後，各 PoI pi に対応

ある．四分木のノードの分割を図 3 のように表現する．図 3aするソーシャルスコアリスト（Liss ）を作成する．Liss は，LNに示すように，ノードを分割した際，分割されたノードをそれに含まれるノードごとに，ノード id およびそのノードに含まれぞれ，NW，NE，SW，および SE と名付ける．例えば，図 3bるクエリのソーシャルスコアの最大値を保存したものである．

のように，4 つのクエリが存在し，領域が分割されたとする．

1
𝑞0

NW
1

NW

NE

SW

SE

2

1

𝑞1

13

3

4

: クエリ

4

(a)

(b)

13

14

15

16

(c)

図 3: 四分木の表現方法
この場合，四分木の構造は，図 3c のような木構造をとる．図3c に示すように，本稿では，葉ノードと中継ノードを表現する

14

𝑞3
{𝑤2}

15

4

𝑞4 {𝑤0, 𝑤2}

16
𝑞5
{𝑤0}

𝑤0, 𝑤1, 𝑤2, 𝑤3, 𝑤4

𝑞2{𝑤1, 𝑤3}

𝑞1{𝑤1, 𝑤2}

13

𝑞3

16

(6,0)(7,0)

SE

SW

2

14
𝑞2

15

NE

0

2

𝑞0
{𝑤0, 𝑤1}

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

2

𝑞7 {𝑤0, 𝑤1}

13

16

14

(a) 図 2 に基づく四分木

ノードid クエリid

数字列

0,1

する．

2

2

1

13

3

02

14

4

12

16

5

32

4

6,7

3

かはクエリの位置情報のみに依存する．まず，全ての PoI が存

15𝑤0, 𝑤2

1介する．四分木を構築する際，クエリがどのノードに含まれる

4(3,0)(4,0)(5,0)

ために四角と丸を用い，クエリが含まれる葉ノードは黒四角とここから，提案アルゴリズムにおける四分木の構築方法を紹30

在している領域を根ノードとする．クエリは，全ての PoI が存在している領域内の任意の点を検索点とできるため，全てのク(b) LN

エリが根ノードに含まれる．次に変数 m を用意し，ノードに含図 4: 四分木の構築（m = 2）および LN

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

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

3. 4 Top-k データの更新アルゴリズム
最後に，ウィンドウのスライドに対して，各クエリの Top-k
データを更新するアルゴリズムを説明する．以下では，データの生成および削除に対する処理をそれぞれ説明する．

3. 4. 1 データの生成
新しくデータが生成されると，LN ，データを生成した PoIの Lss ，および四分木を用いて，スコアが j 番目のデータのス

Algorithm 1: NodeCheck(n, ssn , o, f irst, last, depth, Tss )Input: n：チェック中のノード，ssn ：n のソーシャルスコア，o：

ノード n におけるクエリにアクセスすべきかどうかの判断は，

n に保存された情報，データの位置情報とキーワード集合，おデータ，f irst · last：チェックに用いる Tss の範囲，

よび ssn から計算されたスコアの上界値 scoreub と scoremin

depth：チェック中のノードの深さ，Tssとの比較により行われる．ここで，scoremin は，n に含まれる

1: Calculate scoreub

クエリのうち qu .scorej が最小のものである．以下では，ある

2: if scoremin <= scoreub then

ノードにアクセスした際の具体的な処理について説明する．

3:

if f irst = last //node is a leaf-node thenfor ∀qu ∈ n do

4:Update(qu , o, Tss [f irst].ds)

5:
6:

else
for ∀nc ∈ [N W, N E, SW, SE] do

7:countnc ← 0

8:for i = f irst to last do

9:

if depth-th digit of Tss [i].ds = 0 then10:x ← NW11:

else if depth-th digit of Tss [i].ds = 1 then12:x ← NE13:else if depth-th digit of Tss [i].ds = 2 then14:x ← SW

15:

else

16:

x ← SE17:
18:

countx ← countx + 1

19:

if ssx < Tss [i].ssn thenssx ← Tss [i].ssn

20:
21:

depth ← depth + 1

22:for ∀nc ∈ [N W, N E, SW, SE]//N W ，N E ，SW ，SE の順に処理を行う do
if countnc > 0 then

23:
24:

last ← f irst + countnc − 1

25:

NodeCheck(nc , ssnc , o, f irst, last, depth, Tss )26:

f irst ← f irst + countnc

ノード n におけるデータ o のスコアの上界値 scoreub は式（5）で計算される．

scoreub = dist(n, o) + key(n, o) + ssn(5)

dist(n, o) は ，デ ー タ の 位 置 と ノ ー ド n の 間 の 最 小 距 離 を
MAXloc で割ったものを 1 から引いた値である．ただし，デー
タの位置がノード n の範囲内に含まれる場合は dist(n, o) = 1
である．key(n, o) は，key(qu , o) を計算する場合と異なり，式（6）によって計算される．

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

ここで，n.key はノード n が保持しているキーワード集合である．つまり，key(n, o) は，n が保存しているキーワードのうち，データが持つキーワードのみを n が保持していると仮定して，そのキーワードのみで一致度を計算する．
上記により計算される dist(n, o) および key(n, o) は，qu ∈n.Q で あ る 全 て の ク エ リ qu に 対 し て ，常 に dist(n, o) >=dist(qu , o) および key(n, o) >
key(q
,
o)
を満たす．また，
Topu=
k データの更新が起こるためには，クエリの k 番目のデータのスコアよりも，新しく発生したデータのスコアが大きくなければならない．ここで，以下の定理が成り立つ．

27: else29:

for ∀qu ∈ n do
< scoreub thenif qu .sp =30:

qu .sp ← scoreub

28:

ノードにアクセスすると，まず，scoreub を計算する（1 行）．

定理 1. scoremin > scoreub ならば，チェック中のノード n に含まれるクエリにおいて，Top-k データの更新は起こりえない．
証明. n に含まれるクエリ qu に対して，Top-k データの更コア以上となる可能性があるクエリ，つまり k-スカイバンドの新が起きるためには qu .scorek <= s(qu , o) とならなければい

更新が起こり得るクエリにのみアクセスするためのチェックをけない．しかし，scoremin > scoreub ならば，scoremin >行う．

Tss の作成．まず，チェックするノードのソーシャルスコアを得るために用いるソーシャルスコアテーブル Tss を作成する．

Tss はデータを生成した PoI の Lss と LN を組み合わせて作成
し，LN に保存された全てのノードに対して，ノード id，ノー

dist(n, o) + key(n, o) + ssn で あ る ．ま た ，qu .scorek >=qu .scorej >
score
，および
dist(n,o)+key(n,
o)
+
ss
min
n >
=
=
dist(qu , o) + key(qu , o) + socio(qu , p) = s(qu , o) であるため，scoremin > scoreub ならば，qu .scorek > s(qu , o) である．以
上により，定理１が証明される．

2

ドのソーシャルスコア ssn ，および経路を表す数字列を保存すscoreub が計算されると，scoreub とチェック中のノードのる．あるノードの ssn を得る際，データを生成した PoI の Lssscoremin が比較される（2 行）．scoreub の方が小さい場合は，にそのノードが含まれている場合は Lss に保存されている ssn

新しく生成されたデータにより，現在チェックしているノーを，含まれていない場合は 0 を，そのノードの ssn とする．同

ドに含まれるクエリの k-スカイバンドの更新が起こり得ない時に，Tss に保存される最大のソーシャルスコアを計算し，根ため，チェック中のノードを根とする部分木のチェックを終了

ノードの ssn とする．

し，チェックが終了していないノードのチェックに移る．そのノードのチェック．Tss が作成され，根ノードの ssn が計算されると，NodeCheck（アルゴリズム 1）を用いて，根ノードから順に，クエリにアクセスすべきかどうかを判断していく．ある際，チェック中のノードに含まれる各クエリに対して，qu .spと scoreub を比較し，scoreub の方が大きければ qu .sp を更新
する．ここで，qu .sp は枝刈りされたときの scoreup の最大値を保存したものである．qu .sp の詳細については後に説明する．

scoreub の方が大きければ，子ノードをチェックしていく．まず，Tss に含まれる葉ノードであり，チェック中のノード n を根Algorithm 2: Update(qu , oin , ds)
Input: qu ：クエリ，oin ：生成されたデータ，ds：チェック中のとする部分木に含まれる葉ノードが，n の NW，NE，SW，おノードまでの経路を表す数字列

よび SE のどのノードの経路上に存在するか計算する．ある葉

1: Calculate s(qu , oin )ノードが n′ の経路上に存在するとは，n からその葉ノードにア

2: for ∀o ∈ qu .S do

クセスする際に，n が中継ノードであることを意味している．

3:

if s(qu , oin ) >= s(qu , o) then

この計算は数字列を用いて行い，子ノードの深さ（depth）の

4:
5:

o.dom ← o.dom + 1> qu .k thenif o.dom =6:qu .S ← qu .S − {o}′桁を参照することで計算できる．同時に，n の子ノード（NW，NE，SW，および SE）のソーシャルスコアを計算する（7-18行）．それらのうち，Tss に含まれる葉ノードである，もしく

7: qu .S ← qu .S + {oin }8: if s(qu , oin ) >= qu .scorek thenは子孫に Tss に含まれる葉ノードを 1 つ以上含むノードに対9:

して，NW から順に同様のチェックを行っていく（20-24 行）．

10: N ← A set of nodes that are calculated by ds

チェックしているノードが葉ノードの場合，scoreub の方が大

11: for ∀n ∈ N do

きければ，チェック中のノードに含まれるクエリの k-スカイバ

12:Update qu .D from qu .S

Update qu .scorej

ンドを更新する．そのため，ノードに含まれる全てのクエリに対して，k-スカイバンド，Top-k データ，および四分木に保存

Algorithm 3: Topk-Reevaluation(qu , o)

されている情報の更新を行うアルゴリズム Update を実行する

Input: qu ：クエリ，o：W から削除されるデータ（3-5 行）．
（このアルゴリズムの詳細は，後に説明する．
）

1: qu .S ← qu .S − {o}例 3.1. 図 4 において，q6 .scorej = 1.8 および q7 .scorej = 2.2

2: if o ∈ qu .D then3:であるとき，図 2 における p0 がデータ o を生成したとし，

4:o.key = {w1 , w2 , w5 } とする．また，図 4 におけるノード 4

5:をチェックしたとする．ノード 4 が保存している n.key =6:{w0 , w1 , w2 , w3 , w4 } と o.key = {w1 , w2 , w5 } との共通部分は

7:

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

8:

if |qu .S| >= qu .k thenExtract qu .D from qu .Sif qu .sp >= qu .scorek thenExtract qu .D, qu .S from W
else
Extract qu .D, qu .S from W

を保持していると仮定して，それらのキーワードとデータ o の持つキーワードの一致度からノード 4 における key(·, o) を計算

算で得られたノードに対して，k-スカイバンドが更新されたク

する．この場合，key(·, o) = 2×2= 0.8 となる．また，PoI p0
2+3

エリの j 番目のデータのスコアの情報を更新する (10-12 行)．

とノード 4 の距離のスコアが dist(n, o) = 0.6，ノードのソー3. 4. 2 データの削除

シャルスコアが ssn = 0.8 であるとする．このとき，新しく生

新たに生成されたデータに対する処理が終了すると，W から成されたデータに対するノード 4 におけるスコアの上界値は，削除されるデータに対する処理を行う（アルゴリズム 3）．ま0.6 + 0.8 + 0.8 = 2.2 となる．計算されたスコアの上界値（2.2）

ず，削除されるデータを k-スカイバンドに含む全てのクエリ quとノード 4 に含まれるクエリの j 番目のデータのスコアの最小の qu .S から削除されるデータを取り除く．その中で，削除さ値（1.8）を比較すると，スコアの上界値の方が大きい．そのたれるデータを Top-k データに含むクエリに対して，Top-k デー

め，ノード 4 に含まれる全てのクエリに対して k-スカイバンド

タの更新を行う．qu .S に含まれるデータの中で，スコアの高い

および Top-k データの更新を行う．

上位 k 個のデータを Top-k データとする．この際，|qu .S| < kk-スカイバンドおよび Top-k データの更新．葉ノードにおいもしくはスコアが qu .sp 以下のデータが Top-k データとなるとて k-スカイバンドおよび Top-k データの更新が必要であると判き，W 内のデータにおいて qu .S に含まれないデータが Top-k

断されると，Update（アルゴリズム 2）を用いて，そのノード

データとなり得る．ここで qu .sp とは，自身を含むノードが枝に含まれる全てのクエリ qu に対して，k-スカイバンド，Top-k

刈りされたときの scoreub の最大値をクエリごとに保存したもデータ，および四分木に保存されている情報の更新を行う．

のである．つまり，スコアが qu .sp 以下のデータが Top-k デー

まず，データのスコアを計算し，qu .S に含まれるデータ o のタとなるとき，過去に枝刈りされたデータが Top-k データとな

o.dom を更新する (1-4 行)．o.dom が k 以上となったデータはり得る．そのため，W 内の全てのデータに対してスコアを計

qu .S から削除し，生成されたデータを qu .S に追加する．次に，算し，k-スカイバンドおよび Top-k データの更新を行う．

新たに生成されたデータのスコアがクエリの k 番目のデータの4. 評 価 実 験

スコアより大きければ，生成されたデータと k 番目のデータを置き換える（8-9 行）．提案アルゴリズムでは，k-スカイバンド

本章では，提案アルゴリズムの性能評価のために行った実験が更新されると，四分木に保存されている情報を更新する必要の結果を紹介する．提案アルゴリズムの性能を評価するため，がある．k-スカイバンドが更新されたクエリを含むノードは，以下のアルゴリズムとの比較を行った．

Tss に保存された現在の葉ノードの数字列から計算できる．計•ベースライン 1．データが生成されたとき，全てのクエ

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

表 2: パラメータの設定

Yelp

Brightkite

パラメータ

値（デフォルト）

ユーザの数

366,715

50,687|W | [×104 ]50〜300（50）PoI の数

60,785

772,631

qu .k の最大値，kmax

全チェックインの数 1,521,160

1,072,965|Q| [×104 ]5〜30（10）5〜35（5）（Yelp）
1〜5（1）（Brightkite）

30

度数[

]

25
20

1 から kmax の間の一様乱数とし，qu .key は Yelp のキーワー

15

ドセットのいずれかを用いた．

10

4. 2 評 価 結 果

5本実験では，各アルゴリズムにおける更新時間：（ウィンドウ0
1

2

3

4 5 6 7 8
キーワードの数

9 10 11

図 5: キーワードの数のヒストグラムの各スライドにおいて Top-k データの更新が完了するまでの平均時間 [sec]）の結果を示す．

kmax の影響．図 6 に kmax を変えたときの結果を示す．まず，
リに対して k-スカイバンドを更新し，Top-k データが削除され各ベースラインアルゴリズムに比べて提案アルゴリズムの方がたとき，k-スカイバンドを用いて Top-k データを更新する．

高速に Top-k データを更新している．提案アルゴリズムはベー•

ベースライン 2．データが生成されたとき，提案インデッ

スラインアルゴリズムと比較して，更新時間が少なくとも 3 分

クスによりアクセスするクエリの数を削減し，Top-k データがの 1 に抑えられている．kmax が大きくなると，よりスコアの削除されたとき，W 内の全てのデータを再評価する．

低いデータが Top-k データとなるため，各アルゴリズムにおい•ベースライン 3．データが生成されたとき，提案インデッて更新時間が長くなる．ここで，Yelp と Brightkite の 2 つのクスによりアクセスするクエリの数を削減する．Top-k データ

データセットにおいて，Brightkite におけるベースライン 2 とが削除されたとき，W 内の全てのデータを再評価する際に Lss

3 の更新時間の差よりも，Yelp における更新時間の差の方が大を利用する．具体的には，チェックするデータのソーシャルスコ

きくなる．これは，Yelp はユーザの数に比べて PoI の数が少アを計算する際に，再計算されるクエリを含む葉ノードがデー

なく，ユーザが同じ PoI にチェックインしている可能性が大きタを生成した PoI pi の Liss に含まれる場合は保存されたソーい．すると，ソーシャルスコアの計算により時間がかかるため，

シャルスコアを，含まれない場合は 0 とする．そして，計算さ全てのデータに対してソーシャルスコアを計算するベースライれたスコアと k 番目のデータのスコアを比較し，Top-k データ

ン 2 は大きく性能が低下する．

になり得るかどうかを評価する．Top-k データになり得るデー|W | の影響．図 7 に |W | を変えたときの結果を示す．まず，各タのみ正確なソーシャルスコアを計算し，Top-k データを更新

ベースラインアルゴリズムに比べて提案アルゴリズムの方が高する．

速に Top-k データを更新している．提案アルゴリズムはベース

4. 1 セッティング

ラインアルゴリズムと比較して，更新時間が少なくとも 4 分の本実験は，Windows 7，3.47GHz Intel Xeon CPU，および1 に抑えられている．また，|W | が大きくなると各ベースライ

192GB RAM を搭載した計算機で行い，全てのアルゴリズムは

ンは更新時間が一定もしくは長くなるのに対して，提案アルゴ

C++で実装した．

リズムは更新時間が短くなる．ここで，更新時間はデータの生

データセット．本実験では，2 つの実データ（Yelp （注 2） および成および削除それぞれに対する処理時間の和である．|W | が大Brightkite（注 3））を使用した．表 1 にデータセットの詳細を示

きくなると，よりスコアの大きいデータが Top-k データとなす．それぞれのデータセットにおいて，PoI は位置情報を保持

り，提案インデックスを用いると枝刈りが起きやすくなるため，しており，ユーザと PoI のソーシャル関係はチェックイン情報

ベースライン 2，3，および提案アルゴリズムではデータの生成を用いた．それぞれのデータセットはキーワードに関する情報に対する処理時間は短くなる．一方，ベースライン 1 では常にを含んでいないため，あるデータ o の o.key として，Yelp のあ

すべてのクエリをチェックするためデータの生成に対する処理

るレビューにおけるキーワードセットを用いた．このキーワー

時間はほぼ一定である．また，|W | が大きくなると，W から削

ドセットは 1〜11 個のキーワードが含まれている．キーワード

除されるデータが Top-k データに含まれる可能性が低くなり，の数のヒストグラムを図 5 に表す．

Top-k データの更新を行う頻度が小さくなる．しかし，ベース

パラメータ．本実験で用いたパラメータを表 2 に示す．m = 10

ライン 2 と 3 において，Top-k データに含まれるデータが削除

および j = 2k をデフォルトの値として用いた．ユーザは一人ひされると，W 内の全てのデータを再評価するため，|W | が大き

とつのクエリを発行するものとし，qu .loc は各データセットにくなると再評価するデータが多くなりデータの削除に対する処

おいて全ての PoI が存在する領域内の任意の点とした．qu .k は

理時間が長くなる．一方，ベースライン 1 と提案アルゴリズム
では，k-スカイバンドを用いているため，Top-k データに含ま（注 2）：http://www.yelp.com/dataset challenge/（注 3）：http://snap.stanford.edu/data/loc-brightkite.html

れるデータが削除されたときの Top-k データの更新を高速に行

Top-k データを計算する際にソーシャル関係を用いる点，およ1

更新時間[sec]

更新時間[sec]

10

1

0.1

0.01
5

10

ベースライン1
ベースライン2

ベースライン3
提案

15
20
𝑘𝑚𝑎𝑥 (Yelp)

25

びデータを生成する PoI ごとにソーシャル関係が変化し，各PoI ごとに情報を保存する必要がある点から，このアルゴリズ

0.1

ムを適用できない．同様に文献 [2] では，Top-k データを計算0.01

する際にソーシャル関係ではなく時間を用いている点，およびベースライン1
ベースライン2

0.001

30

5

(a) Yelp

10

ベースライン3
提案

15
20
25
𝑘𝑚𝑎𝑥 (Brightkite)

30(b) Brightkite

スライディングウィンドウモデルに適用していない点から，本研究の問題と異なる．

6. 終 わ り に

図 6: kmax の影響

PoI（Point of Interest）からのパブリッシュ/サブスクライ
1

更新時間[sec]

更新時間[sec]

10

1

0.1
ベースライン1
ベースライン2

0.01

50

100

ベースライン3
提案

150 200 250|𝑊| (Yelp)[× 104 ]ブモデルに基づいたデータの発信，および位置情報サービス
やソーシャルネットワークサービスの普及により，位置やキー

0.1

ワード，ソーシャル関係を用いた検索への関心が高まっている．
0.01

本稿では，パブリッシュ/サブスクライブモデルで生成されたベースライン1
ベースライン2

0.001

300

50

(a) Yelp

ベースライン3
提案

100 150 200 250 300|𝑊| (Brightkite)[× 104 ](b) Brightkite

図 7: |W | の影響

データの中から，位置，キーワード，およびソーシャル関係に基づき，ユーザにとって有用な上位 k 個のデータをスライディ
ングウィンドウ上でモニタリングする問題に取り組んだ．提案
アルゴリズムでは，クエリを四分木により管理し，さらに k-ス
カイバンドを用いることにより，リアルタイムモニタリングをうことができる．以上の理由から，提案アルゴリズムでは |W |実現している．評価実験の結果から，提案アルゴリズムの有効が大きくなると更新時間が短くなる．

性を確認した．

5. 関 連 研 究

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

本章では，複数の属性を考慮した検索に関する従来研究，ま業（戦略的国際共同研究プログラム）の研究助成によるものでた，Pub/Sub モデルにおけるデータのモニタリングに関する

究 (A)(JP26240013) および JST 国際科学技術共同研究推進事ある．ここに記して謝意を表す．

従来研究について紹介する．
文
位置，キーワード，およびソーシャル関係を考慮した検索．位
置，キーワード，およびソーシャル関係を考慮した検索についての様々な研究が行われている [1], [7]．文献 [7] では，上記の3 つの属性に基づく Top-k 検索を効率的に行うインデックスとして，SNIR 木を提案している．SNIR 木の各ノードには，自身を根とする部分木に含まれるデータの位置情報とデータに興味のあるユーザを保存し，クエリが発行されると Top-k デー
タになり得る部分を順に探索していく．しかし，本研究では，
ソーシャル関係の定義が異なり，クエリを SNIR 木で管理した
場合，各ノードでソーシャルスコアを計算できない．さらに，
このデータ構造は Top-k データのモニタリングに対応しておらず，解の更新を行うためには全てのデータを再検索する必要がある．同様に，文献 [1] では，データモニタリングではなくス
ナップショットクエリを考えており，本研究の問題とは異なる．

Pub/Sub モデルにおけるデータモニタリング．文献 [2], [5] では，Pub/Sub 環境における Top-k データモニタリング手法を提案している．文献 [5] では，位置，およびキーワードに基づいて計算された Top-k クエリの解をスライディングウィンドウ
上でモニタリングするためのアルゴリズムを提案している．具
体的には，四分木を用いてクエリを管理し，データの生成に対して Top-k データの更新を高速に行う．また，コストベースの k-スカイバンドを用いることにより，データが削除されたとき，Top-k データの再計算を高速に行う．しかし，本研究では，

献[1] R. Ahuja, N. Armenatzoglou, D. Papadias, and G. J. Fakas.
Geo-social keyword search. SSTD, pages 431–450, 2015.
[2] L. Chen, G. Cong, X. Cao, and K.-L. Tan. Temporal spatialkeyword top-k publish/subscribe. In ICDE, pages 255–266,
2015.
[3] G. Groh and C. Ehmig. Recommendations in taste related
domains: collaborative filtering vs. social filtering. In SIGGROUP, pages 127–136, 2007.
[4] H. Hu, Y. Liu, G. Li, J. Feng, and K.-L. Tan.
A
location-aware publish/subscribe framework for parameterized spatio-textual subscriptions. In ICDE, pages 711–722,
2015.
[5] X. Wang, Y. Zhang, W. Zhang, X. Lin, and Z. Huang.
Skype: top-k spatial-keyword publish/subscribe over sliding window. PVLDB, 9(7):588–599, 2016.
[6] X. Wang, Y. Zhang, W. Zhang, X. Lin, and W. Wang. Aptree: Eﬃciently support continuous spatial-keyword queries
over stream. In ICDE, pages 1107–1118, 2015.
[7] D. Wu, Y. Li, B. Choi, and J. Xu. Social-aware top-k spatial
keyword search. In MDM, pages 235–244, 2014.
[8] C. Zhang, Y. Zhang, W. Zhang, and X. Lin. Inverted linear
quadtree: Eﬃcient top k spatial keyword search. In ICDE,
pages 901–912, 2013.
[9] K. Zheng, H. Su, B. Zheng, S. Shang, J. Xu, J. Liu, and
X. Zhou. Interactive top-k spatial keyword queries. In
ICDE, pages 423–434, 2015.
[10] 西尾俊哉, 天方大地, 原 隆浩. 位置，キーワードおよびソーシャル
関係に基づく top-k パブリッシュ/サブスクライブ. 第 8 回デー
タ工学と情報マネジメントに関するフォーラム（DEIM フォー
ラム 2016）, 2016.