DEIM Forum 2016 D7-6

距離・キーワード・ソーシャル関係に基づくスカイライン検索
直弥†

田口

天方

大地††

原

隆浩††

西尾章治郎††† 大阪大学工学部電子情報工学科 〒 565-0871 大阪府吹田市山田丘 2-1†† 大阪大学大学院情報科学研究科 〒 565-0871 大阪府吹田市山田丘 1-5
E-mail: †{taguchi.naoya,amagata.daichi,hara,nishio}@ist.osaka-u.ac.jp
あらましソーシャル型位置情報サービスの出現により，地理的距離，キーワード，およびソーシャル関係を利用した情報検索に多くの注目が集まっている．本稿では，これら 3 つの指標に基づくスカイライン検索問題に初めて取り組む．スカイライン検索は，あるデータ集合の中から，どのデータにも支配されていないデータのみを検索するものであり，多くのアプリケーションを持つ．本稿では，SKR 木と呼ぶインデックスを用いたスカイライン計算アルゴリ
ズムを提案し，高速なスカイライン検索を実現する．また，Gowalla および Brightkite の実データを用いた実験により，提案手法の有効性を示す．
キーワード

スカイライン, ソーシャルネットワーク, 位置情報サービス

1. は じ め にめ，容易に POI を選出できる．また，スカイラインクエリに

近年，スマートフォンやタブレットなどのモバイル端末の普及により，位置情報サービスやソーシャルネットワーキングサービスが多くの人に利用されている [7], [12]．位置情報サービ

はスケール普遍性があり，スコアリング関数の入力を必要としないといった利点がある．
以下に地理的距離，キーワード，およびソーシャル関係に基では，ユーザが指定する位置

づくスカイライン検索の実用例を示す．以降，このスカイライ

およびキーワードに基づいて，距離が近く，検索キーワードにン検索を GSK (Geo Social Keyword) スカイライン検索と呼関連する POI (Point Of Interest) を検索できる．これに伴い，び，GSK スカイライン検索の解を GSK スカイラインと呼ぶ．

位置情報サービス上でソーシャル関係を考慮する，ソーシャル

例 1．あるユーザがレストランを選出することを考える．ユー

型位置情報サービスが現れ，多くの注目を集めている [6]．ソー

ザは，検索点を自身の現在位置，検索キーワードを “中華” とシャル型位置情報サービスの一例である Yelp（注 2） では，位置おする GSK スカイライン検索により候補となるレストランを選

よびキーワードに基づいたサービスに加え，チェックインした出する (図 1) ．また，POI の各属性値として，検索点からのPOI を友人と共有するなど，ソーシャル関係を考慮した様々な距離，検索キーワードとその POI が保持するキーワードの一サービスを受けることができる．このようなサービス上で，距致数，およびその POI にチェックインした検索者の友人の数を離が近く，キーワードの関連度が高く，さらにソーシャル関係

用いる．ここで， 図 2 は，図 1 の検索者に関するソーシャルが深い POI を選出することは，多くのアプリケーションにとっグラフを表しており，グラフの辺は，ユーザ間の友人関係またて有用である [1]．この選出を効率的に行うための既存研究としはユーザの POI へのチェックイン履歴である．図 1 および図 2て，これら 3 つの指標を数値化し，その重み付き和によってスより，レストラン B は，検索点からの距離，キーワードの一致

コア付けしたときの上位 k 個の POI を検索する Top-k 検索が数，およびチェックインした検索者の友人の数全てにおいて C

提案されている [1]．しかし，この Top-k クエリでは，スケーのものに劣るため，C に支配されており，GSK スカイライン

ル普遍性がなく（注 3），重みの組合せも無限にあるため，ユーザに含まれない．同様に D，E，F，G，H，I，および J も C ににとって困難な入力を求めている．

支配されているため，GSK スカイラインに含まれない．A は（注 1）

スの一例である Google Maps

そこで本稿では，これら 3 つの指標に基づくスカイライン検検索点からの距離およびキーワードの一致数においては C に劣索 [3] を提案する．あるデータ集合におけるスカイラインとは，るが，チェックインした検索者の友人の数は C のものよりも多その要素のうち，どのデータにも支配されていないものの集合

いため，C に支配されない．よって A および C が GSK スカ

であり，あるデータ o が別のデータ o′ に支配されるとは，o がイラインとなり，ユーザはこの 2 つのレストランのみを選出候

その全ての属性値について o′ のものに劣ることをいう．ユーザ

補とできる．

にとって，ある POI に支配される POI は選出候補外とみなすことができるため，スカイライン検索により選出候補を絞り込

本稿では，この GSK スカイライン検索問題に初めて取り組んだ．この問題の最も単純な解決法は，全ての POI について各属性値を算出し，それらそれぞれについて，他の全ての POI（注 1）：https://www.google.co.jp/mapsとの支配関係を評価するというものである．しかし，この方法（注 2）：http://www.yelp.com/

では POI 数が多い場合に，高速に検索結果を得ることができ（注 3）：各指標の値を正規化する必要がある．

2. 2 問 題 定 義DFあるユーザ u が GSK スカイライン検索を実行するとき，u“和食”, “高級”

“中華”, “安い”

B

I
“中華”

“フレンチ”, “駅近”G

“インド料理“CA“中華”, “安い”

与えられたとき，ある pi ∈ P には，地理的距離，キーワード，
よび pi .S(qu ) が与えられる．pi .G(qu ) は pi .loc と qu .loc との“ファストフード““イタリアン“

クエリ qu を発行する．つまり，qu = ⟨loc, key⟩ である．qu がおよびソーシャル関係に関する属性値 pi .G(qu )，pi .K(qu )，おJ“タイ料理“は位置およびキーワードの集合を指定した GSK スカイライン

ユークリッド距離であり，E
POI (レストラン)“カフェ”, “駅近”ユーザ

pi .G(qu ) = dist(pi .loc, qu .loc)

図 1 GSK スカイライン検索の実用例
IHで求められる．pi .K(qu ) は，pi .key の要素と qu .key の要素の一致数であり，GJ

pi .K(qu ) =| pi .key ∩ qu .key |Fである．また，pi .S(qu ) はユーザ u の友人のうち，pi にチェッAEしているユーザの集合，u.f riend を u と友人関係にあるユー

検索者

B

D
C

クインしている人の数であり，pi .checkin を pi にチェックイン

POI

チェックインユーザ

友人関係

図 2 検索者に関するソーシャルグラフ

ザの集合とすると，

pi .S(qu ) =| pi .checkin ∩ u.f riend |である．ただし，u 自身のチェックインは考慮しない．例えば図2 において，A.S(qu ) は 4 であり，C.S(qu ) は 3，また F.S(qu )および I.S(qu ) は 0 となる．検索点からの距離は近い方が良ない [3]．また地理的距離，キーワード，およびソーシャル関係

いため，pi .G(qu ) は小さい方が優れており，キーワードの一致

に関する属性値は，それぞれ検索位置，検索キーワード，およ

数およびチェックインしている友人の数は多い方が良いため，

び検索者に依存するため，検索結果を再利用することも困難で

pi .K(qu ) および pi .S(qu ) は大きい方が優れている．ここで，本ある．そこで本稿では，SKR 木という階層型インデックスを稿における支配という概念を定義する．

事前に構築することにより，任意の検索点，検索キーワード，
および検索者に対して高速に GSK スカイライン検索を行うことを試みた．SKR 木は POI の位置情報，保持するキーワード，
およびソーシャル関係に関する属性値の上界値を基に構築する

定 義 1 (支 配)．GSK ス カ イ ラ イ ン ク エ リ qu が 与 え ら れ ，pi , pj ∈ P について，(pi .G(qu ) >= pj .G(qu )) ∧ (pi .K(qu ) <=pj .K(qu )) ∧ (pi .S(qu ) <
p
.S(q
))
が満たされる場合，これをju=pi ⪯ pjaR 木 [8] であり，GSK スカイラインに含まれない POI に対応するノードの枝刈りを効率的に行うことができる．また，SKR
木において探索するノード数を最適化し，ソーシャル関係に関する属性値の性質を考慮したアルゴリズムを提案することにより，高速な GSK スカイライン検索を実現した．

と表す．また，(pi ⪯ pj )∧[(pi .G(qu ) > pj .G(qu ))∨(pi .K(qu ) <pj .K(qu )) ∨ (pi .S(qu ) < pj .S(qu ))] が満たされる場合，pi は
pj に支配されるとし，これをソ ー シャル 型 位 置 情 報 サ ー ビ ス で あ る ，Gowalla お よ びpi ≺ pj

Brightkite の実データを用いた実験から，提案手法は単純手法よりも高速に GSK スカイライン検索を行えることを確認した．
以降，2. で本稿の問題を定義し，3. で提案手法について説明する．4. で評価実験の結果を示し，5. で関連研究を紹介する．
最後に，6. で本稿をまとめる．

と表す．
また，GSK スカイラインを次のように定義する．
定義 2 (GSK スカイライン)．POI の集合 P および GSK ス
カイラインクエリ qu = ⟨loc, key⟩ が与えられたとする．P の

2. 事 前 準 備′
部分集合 P ′ ⊂=P が ∀pi ∈ P に対して

2. 1 データモデル

pi ⊀ ∃pj ∈ P

本稿で検索対象となるデータは POI であり，POI の集合をP とする．ある pi ∈ P は，pi = ⟨loc, key⟩ で表される．i は
POI の識別子，loc は pi の位置，key は pi が保持するキーワー
ドの集合である．

を満たすとき，P ′ を P の GSK スカイラインとする．
本稿では，GSK スカイライン検索を高速に行うことを目的とする．

Algorithm 1: Baseline algorithm
1for ∀pi ∈ P do
Calculate each attribute value of pi

23for ∀pi ∈ P do

𝑟𝑜𝑜𝑡

B
{𝒌𝟏 , 𝒌𝟐 , 𝒌𝟑 } : 10for ∀pj ∈ P do

4

A {𝑘1 } : 1 C{𝒌𝟏 , 𝒌𝟐 } : 3

D{𝒌𝟏 , 𝒌𝟐 } : 35if pi ≻ pj then6

P ← P \{pj }

A

B

7

if pi ≺ pj then

𝑝𝐴

𝑝𝐵

8

P ← P \{pi }

9

break

{𝑘2 } : 3{𝑘1 } : 10

C{𝑘3 } : 2

{𝒌𝟏 , 𝒌𝟐 , 𝒌𝟑 } : 10
D{キーワード} : ソーシャル関係に関する属性値の上界値

𝑟𝑜𝑜𝑡
葉ノード

図 3 SKR 木の構造
10

return P– その全ての子ノードが保持するキーワードの和集合
2. 3 単 純 手 法
ベースラインとなる単純な GSK スカイライン検索アルゴリ– その全ての子ノードのソーシャル関係に関する属性値の上界値の最大値

ズムをアルゴリズム 1 に示す．アルゴリズム 1 では，まず全て

図 3 は SKR 木の例を示しており，葉ノード A(B) は対応の POI の各属性値を算出し (1-2 行)，その後，各 POI についする POI の ID pA (pB )，位置，保持するキーワードの集合て，他の全ての POI との支配関係を評価することにより (3-9{k1 }({k2 })，そしてソーシャル関係に関する属性値の上界値行)，GSK スカイラインを求める (10 行)．しかし，アルゴリ

1(3) を持つ．ソーシャル関係に関する属性値の上界値について

ズム 1 では 2 つの理由により計算時間が増加してしまう．1 つは 3. 2 節で詳しく説明する．また内部ノード C はその子ノード

目は，全ての POI について各属性値を算出しなければならなであるノード A および B から構成される最小外接矩形 (MBR)

いことである．特に，ソーシャル関係に関する属性値の算出にであり，A および B が持つキーワードの和集合 {k1 , k2 } を持は，検索者の全ての友人に対して各 POI にチェックインしていち，A および B が持つソーシャル関係に関する属性値の上界るか否かを判定するため，計算時間が増加してしまう．2 つ目

値の最大値である 3 を持つ．同様に内部ノード D もその全ては，支配関係の評価回数が多いことである．アルゴリズム 1 での子ノードから構成される MBR であり，キーワードの集合

は各 POI について，他の全ての POI と支配関係の評価を行う{k1 , k2 , k3 } およびソーシャル関係に関する属性値 10 を持つ．

ため，計算時間が増加してしまう．そこで，これらの問題を解

SKR 木のノード ni は GSK スカイラインクエリ qu に対決するアルゴリズムを提案し，GSK スカイライン検索の効率

し，POI と同様に地理的距離，キーワード，およびソーシャル化を図る．

関係に関する属性値を計算でき，これらをそれぞれ ni .G(qu )，3. 提 案 手 法

ni .K(qu )，および ni .S とする．ni が葉ノードの場合，ni .G(qu )は，それに対応する POI と qu .loc のユークリッド距離である．

提案手法では，階層型インデックスである SKR 木を事前にni が内部ノードの場合，ni .G(qu ) は，MBR の持つ領域内の構築する．このインデックスを用いることにより，各属性値を点のうち，最も qu .loc に近い点と qu .loc とのユークリッド距算出する POI 数および支配関係の評価回数を共に削減できる．

離である．また，ni .K(qu ) は qu .key の要素と ni が保持する

また SKR 木において，探索するノード数を最適化し，ソーシャ

キーワードの一致数であり，ni .S は ni が保持するソーシャルル関係に関する属性値の性質を考慮することにより，効率的な関係に関する属性値である．これらの属性値を用いることによ

GSK スカイライン検索アルゴリズムを設計した．

り，ni と pj ∈ P の支配関係の評価が可能となる．ノードがあ

3. 1 SKR木る POI に支配される場合，そのノードの全ての子孫ノードにSKR 木は POI の位置，保持するキーワード，およびソーシャ

対応する POI は GSK スカイラインに含まれず，枝刈りが可能

ル関係に関する属性値の上界値を基に構築する aR 木である．

である．枝刈りにより，各属性値を算出する POI 数が減り，さSKR 木の葉ノードは POI と 1 対 1 対応している．また，SKRらに支配関係の評価回数も削減されるため，高速に GSK スカ

木の葉ノードおよび内部ノードは，それぞれ以下の要素を保持

イライン検索を行うことができる．

している．

•

葉ノード

3. 2 ソーシャル関係に関する属性値の上界値
前節より，SKR 木を構築するには，各 POI のソーシャル関– 対応する POI の ID係に関する属性値の上界値を求める必要がある．本稿では各– 対応する POI の位置

POI について，ソーシャルグラフ上の全てのユーザに対する– 対応する POI が保持するキーワードの集合

ソーシャル関係に関する属性値を求め，それらの中の最大値を– 対応する POI のソーシャル関係に関する属性値の上界値

それぞれの POI のソーシャル関係に関する属性値の上界値と•した．例えば，図 4 はある POI に関するソーシャルグラフを

内部ノード (MBR)cdAlgorithm 2: Proposed algorithm
b

e
a

1

QF .push(nroot )2

while | QF |=| 0 do3

ntemp = QF .top

4

QF .pop5

temp
for ∀pi ∈ Psky
do

6

f

POI

チェックインユーザ

友人関係

図 4 POI に関するソーシャルグラフ
J

A

I

a

H

G

b

B

ntemp .children = ∅

8

break

9

if ntemp .children are not leaf then10for ∀ni ∈ ntemp .children do

11

Calculate each attribute value of ni

12ni .score = F (ni , qu )13

QF .push(ni )

14
15

F

E

C

D

POI

チェックインユーザ

友人関係

図 5 ユーザ a とユーザ b が新たに友人になった場合示しており，ユーザ a に対するこの POI のソーシャル関係に関する属性値は 3 であり，同様に b の場合も 3，c および d は

1，e は 4，そして f は 2 である．よってこの POI のソーシャル関係に関する属性値の上界値は，これらの中の最大値である 4となる．上界値の求め方には他にも様々な方法があり，例えばPOI への総チェックイン数を用いる方法などが挙げられるが，その求め方により上界値は異なったものとなる．
一方，ソーシャル関係に関する属性値の上界値が小さければ枝刈りできる POI 数が多くなり，高速に GSK スカイライン検索を行うことができる．本稿の方法で求まる上界値は，事前に求められる上界値として最小となる反面，算出にかかる計算時
間は長くなる．しかし，一度この方法で上界値を算出すると，友人関係，またはチェックインに変化があった場合においても上界値を容易に更新できる．
例えば図 5 は，元々友人関係になかったユーザ a とユーザ bが新たに友人になった場合を示している．この友人関係の更新によりソーシャル関係に関する属性値の上界値が変わる可能性がある POI は，友人関係の更新を行ったユーザがチェックイン
している POI のみであり，ユーザ a および b 自身がチェックイ
ンしている C，F，および I のみとなる．友人関係の更新の場
合，これらの POI のソーシャル関係に関する属性値を新たに友人になった 2 人のユーザに対して算出し，これが元の上界値よりも大きくなれば上界値を更新すれば良い．この例の場合，

F の上界値は変わらず 1 であり，C および I の上界値は 1 から2 になる．
3. 3 提案アルゴリズム
提案手法では，SKR 木を用いて GSK スカイライン検索を行

if ntemp ≺ pi then7else
for ∀ni ∈ ntemp .children do

16

Calculate each attribute value of ni .p

17

temp
temp
temp
Psky
← Psky\{∀pj ∈ Psky
|pj ≺ ni .p}

18

temp
if ni .p ⊀ ∃pj ∈ Psky
then

19

temp
temp
Psky
← Psky∪ {ni .p}20

temp
return Psky

う．本節では，これを実現する提案アルゴリズム (アルゴリズ
ム 2) について述べる．
アルゴリズム 2 では，アクセスした各ノードをスコアリング
関数 F によりスコア付けし，優先度付きキュー QF に格納する (スコアが大きいほど優先度は高い)．また，QF は SKR 木の根ノード nroot で初期化されている (1 行)．QF に格納されたノードは先頭から順にポップされていき，GSK スカイライ
ンの途中結果に含まれる POI (以降このような POI の集合を
temp
Psky
と表す) に支配されるか否かを調べられる (3-8 行)．ポッ
temp
プされたノードが Pskyの要素に支配される場合，QF の次のtemp
ノードをポップする．ポップされたノードが Pskyのどの要素にも支配されない場合，その子ノードが内部ノードならば，その全ての子ノードの各属性値を算出し，F によりスコアを付与
して，QF に格納する (9-13 行)．一方，その子ノードが葉ノー
ドならば，それらの葉ノードに対応する POI である ni .p につ
temp
いて各属性値を算出し，Pskyの全ての要素との支配関係を調
temp
べる．ni .p に支配される pj ∈ Pskyが存在する場合，pj を
temp
temp
Psky
から除く．ni .p が Pskyのどの要素にも支配されない
temp
場合，それを Pskyに加える．(14-19 行)．この操作を QF がtemp
空になるまで続け，QF が空になったときの Psky
が GSK スカイラインとなる (20 行)．

3. 4 スコアリング関数の設計
アルゴリズム 2 により効率的な GSK スカイライン検索を行うためには，検索終了時までに探索するノード数をできる限り少なくする必要がある．ここで，枝刈りされるノードは，ノードの探索順 (F ) により変化する．図 6 では，葉ノード A に対応する POI である pA の地理的距離，キーワード，およびソー一定 (Nconst ) となる．
また，任意の関数 F ′ を用いて検索を行う場合，n ∈ Nconst が枝刈りされない枝刈りされる

探索されなかったとする．このとき，n のある祖先ノード nanstempの全ての子孫ノードが枝刈りされており，nans ≺ ∃py ∈ Psky

B : {2,0,0}

B : {2,0,0}が成り立つ．ところが，nans ≺ py となるとき，F ′ が式 (1) を満たす場合にも n は探索されない．これは Nconst が一定のノーA

A

𝑝𝐴 : {1,1,1}-- Aを先に探索{} 各属性値
𝑝𝐴 : {1,1,1}
葉ノード-- Bを先に探索ドの集合であることに反する．従って，いかなる関数を用いた
場合にも n は探索されることになり，| Nconst | はアルゴリズ
ム 2 で探索するノード数のうち，最小 (最適) なものとなる． □以上の議論より，アルゴリズム 2 を用いた GSK スカイライ

図 6 探索順により枝刈りされるノードが変化する例

ン検索を高速化するためには，式 (1) を満たすスコアリング関
シャル関係に関する属性値が全て 1 であり，内部ノード B の

数 F を設計すれば良い．また，GSK スカイラインの中でも支各属性値が 2，0，および 0 であるため，pA が B を支配する．

配するデータ空間が大きい POI を優先的に検索することによ

よって，A を B より先に探索すると，B の全ての子孫ノードがり，支配関係の評価回数を削減できる．これは，ノードや POI

枝刈りされる．ところが，B が A より先に探索された場合，Atemp
が Pskyに含まれる POI に支配されやすくなるためである．

によって B の全ての子孫ノードが枝刈りされることはない．そよって，データ空間が大きい POI に対応する葉ノードを子孫

こで本稿では，アルゴリズム 2 において成り立つ定理により，に持つノードへと優先的にアクセスするため，このようなノー探索するノード数を最適化する F を設計する．以下に，その定ドのスコアを大きくする F を設計する．ここで，ノードをス

理を示す．

コアリングするために，ノードが持つ地理的距離，キーワード，

定理．GSK スカイラインクエリ qu が与えられ，アルゴリズム

2 により GSK スカイラインを計算するとき，SKR 木中の 2 つる fG ，fK ，および fS を設計する．F ではスコアの大きい方が優れるため，地理的距離に関する属性値のスコアリング関数のノード ni および nj に対し，F がni ≺ nj ⇒ F (ni , qu ) < F (nj , qu )およびソーシャル関係に関する属性値のスコアリング関数であは次のように設計できる．

(1)

fG (ni , qu ) = distmax − ni .G(qu )(2)を満たすならば，探索するノード数は最適である．
証明．NA および NB をそれぞれ，式 (1) を満たす関数 FA お
よび FB を用いた場合に，アルゴリズム 2 において，検索終了時までに探索される SKR 木中のノードの集合とする．このとき，NA =| NB と仮定すると，(i) ∃nA ∈ NA , nA ̸∈ NB または(ii) ∃nB ∈ NB , nB ̸∈ NA のいずれかが満たされるはずである．
また，場合 (i) および場合 (ii) それぞれについて以下のことが成り立つ．
場合 (i)． nA ̸∈ NB より，FB を用いた場合，nA のいずれかの祖先ノード nansの全ての子孫ノードが枝刈りされており，
A
temp
nans
≺ ∃px ∈ Pskyが成り立つ．ここで，px に対応する葉
Aノードを nx とすると，SKR 木の構造上，nx の親ノード nparxについて px ⪯ npar
であるため，nans≺ nparである．一方，関xxA
数 FA を用いた場合，FA が式 (1) を満たすため，nans≺ nparx
A
parans
より FA (nansが探索されたA , qu ) < FA (nx , qu ) となり，nA
際，nparあるいは nparを支配する px′ に対応する葉ノードでxxある nx′ がすでに探索済みである．よってこのとき，px あるい
temp
は px′ が Pskyに含まれており，nans≺ px または nans
≺ px′
A
A

より，nansの全ての子孫ノードは枝刈りされ，検索終了時まA
でに探索されることはない．これは nA ∈ NA に矛盾するため，
場合 (i) は起こり得ない．
場合 (ii)． NA , NB の対称性により，場合 (i) と同様に起こり得ない．
以上により，NA = NB となる．よって，関数 F が，式 (1)を満たすならば，アルゴリズム 2 で探索されるノードの集合は，

ただし，distmax は qu .loc と，nroot の MBR の四隅との距離のうち，最大のものとする．また，大きい方が優れるキーワー
ドおよびソーシャル関係に関する属性値のスコアリング関数はそれぞれ，fK (ni , qu ) = ni .K(qu ) および fS (ni ) = ni .S である．これらの設計により，fG ，fK ，および fS を軸とする 3 次
元空間において，支配する空間が大きいほど多くのノードおよ
び POI を支配することが期待できるため，スコアリング関数

F を次のように設計できる．
F (ni , qu ) = fG (ni , qu ) · fK (ni , qu ) · fS (ni )(3)

ここで，式 (3) の F は fG ，fK ，および fS のうちどれか 1 つでも0 となった場合，それ自身も 0 となってしまうため式 (1) を満たす
F とならない．例えば GSK スカイラインクエリ qu が与えられ，SKR 木のノード ni および nj の fG ，fK ，および fS をそれぞれ ni .(fG , fK , fS ) = ni .(1, 0, 0)，nj .(fG , fK , fS ) = nj .(1, 1, 0)とすると ni ≺ nj であるが，F (ni , qu ) = F (nj , qu ) = 0 とな
り，F は式 (1) を満たさない．そこで fK および fS をそれぞれ以下のように設計し直す．

ni .K(qu )fK (ni , qu ) =αni .SfS (ni ) =α(ni .K(qu ) =
| 0)

(4)

(ni .K(qu ) = 0)
(ni .S =| 0)(ni .S = 0)

(5)

ただし，α は 0 < α < 1 を満たす実数とする．これにより，fK

4. 1 設および fS が 0 となる場合に対応できる．また，fG が 0 となる

本実験は，表 1 に示される Gowalla（注 4）および Brightkite（注 5）場合に対応するため，F を次のように設計し直す．

F (ni , qu ) =fG (ni , qu ) · fK (ni , qu ) · fS (ni )−1fK (ni ,qu )·fS (ni )定の 2 つの実データを用いて行った．これらのデータセットは，
どちらもソーシャル型位置情報サービスのものであり，ID およ(fG (ni , qu ) =| 0)

び位置情報を保持する POI データ，ユーザの POI へのチェッ(6)(fG (ni , qu ) = 0)

クインデータ，そしてユーザ間の友人関係のデータにより構成
される．また，各 POI に 10,000 種類の人工キーワードを 5 個

式 (6) の F は，fG (ni , qu ) = 0 となる場合のスコアを負の値にずつ付与した．これらの 5 個の人工キーワードに相関性 (例えすることにより，式 (1) を満たす．また，fG (ni , qu ) = 0 の場

ば，“レストラン” と “ランチ” というキーワードは同じ POI に合にスコアを負の値にすると，fG ，fK ，および fS を軸とする付与されている可能性が高い) を持たせるため，ランダムで 1

3 次元空間において，支配する空間が大きい POI に対応する葉つの自然数 n を選び n，n + 1，n + 2，n + 3，n + 4 をそれぞ

ノードを子孫に持つことが期待できるノードほどスコアが小さ

れ 10,000 で割った余りを用いた．

くなるため，逆数をとっている．
さらに本稿では，位置情報とソーシャルグラフに関するヒュー
リスティックを F に取り入れる．あるユーザが自身の生活区域
で GSK スカイライン検索を行うとする．このとき，ユーザと表 1 各データセットの詳細
データセット ユーザ数

POI 数

総友人関係数 総チェックイン数

Gowalla196,591

1,280,969

1,900,655

3,981,334

Brightkite

58,228772,965

428,157

1,072,965

その友人は，同じ生活区域で生活していることが多いため，検索者の友人は，検索点の周辺の POI にチェックインしていることが多いと考えられる．よって，検索者の周辺の POI はソーシャル関係に関する属性値が高くなりやすい．一方，SKR 木の各ノードは，各 POI のソーシャル関係に関する属性値の上界値を保持しており，上界値は検索位置に関係していない．よって F によりノードをスコアリングする際，ソーシャル関係に関する属性値が大きい POI に対応するノードを優先的に探索するためには，ソーシャル関係に関する属性値のスコアリング関数において検索位置を考慮する必要がある．従って，ソーシャル関係に関する属性値のスコアリング関数 fS′ は，式 (5) の fS

実験は，ランダムに選ばれたユーザがある検索点で，1 から5 個のキーワードを用いて GSK スカイライン検索を行う，というシナリオで行った．検索点には，検索ユーザ自身がチェッ
クインしている POI により構成される MBR をその検索ユー
ザの生活区域とみなし，その MBR 内のランダムな地点を用いた．また，検索キーワードには，POI に付与したものと同様の方法で選んだ人工キーワードを用いた．

4. 2 実 験 結 果
本節では，評価実験の結果を示す．なお，式 (4) および (5)と，fS′ の検索位置依存度を表す実数 d(> 0) を用いて次のようにおける α は，準備実験の結果に基づいて α = 0.001 とした．

に設計される．

インデックスの構築時間．表 2 に各データセットにおけるソー
シャル関係に関する属性値の上界値の計算時間を示す．本稿にfS′ (ni , qu ) =fS (ni ) · fG d (ni , qu )f (n )
Si

おけるソーシャル関係に関する属性値の上界値の計算は，上(ni .G(qu ) =
| 0)

(7)

(ni .G(qu ) = 0)

界値として最小となる反面，算出にかかる計算時間は長くなるが，Gowalla で 67.7[sec]，Brightkite で 35.2[sec] で計算で以上の議論に基づいて，本稿で用いるスコアリング関数を以きている．ソーシャル関係に関する属性値の上界値の計算時

下のように設計する．各属性値に関するスコアリング関数は，間は，データセットのユーザ数と，その平均友人数および平均式 (2)，(4)，および (5) を用いる．最終的に，スコアリング関

チェックイン数に依存する．表 1 のように，Brightkite に比べ数は式 (6) の fS を式 (7) の fS′ に置き換えたものとなり，次のて，ユーザ数，平均友人数，および平均チェックイン数が全てように表される．

多い Gowalla の方が，表 2 のようにソーシャル関係に関する属
性値の上界値の計算に多く時間がかかる．また，表 3 に各デー

F (ni , qu ) =fG d+1 (ni , qu ) · fK (ni , qu ) · fS (ni )−1fK (ni ,qu )·fS (ni )タセットにおける SKR 木の構築時間を示す．SKR 木の大きさ(fG (ni , qu ) =| 0)

は各データセットにおける POI 数に依存する．表 1 のように，(fG (ni , qu ) = 0)

Brightkite に比べて，POI 数が多い Gowalla の方が，表 3 のように SKR 木の構築に時間がかかる．

4. 評 価 実 験

d の影響．図 7 に，検索キーワード数 1 から 5 について，式 (7)の検索位置依存度 d を変えたときの提案手法の平均検索時間を本章では，提案手法の性能評価のために行った実験の結果を示す．横軸は d の値，縦軸はランダムに選んだ 100 人のユー紹介する．比較手法として，2. 3 節で紹介したアルゴリズム (単ザが GSK スカイライン検索を行った際の平均検索時間を表す．

純手法と称する) を用いた．全てのアルゴリズムは C++で実装されており，実験は 3.47GHz Intel(R)Xeon(R)CPU および（注 4）：http://snap.stanford.edu/data/loc-gowalla.html

192GB RAM で構成される PC 上で行った．

（注 5）：http://snap.stanford.edu/data/loc-brightkite.html

ソーシャル関係に関する属性値の上界値の計算時間
データセット 計算時間 [sec]Gowalla67.7

Brightkite

35.2

3000

平均検索時間[msec]

表2

表 3 SKR 木の構築時間

1500

1000
500
0

Brightkite

2,376

1

3

4

5

検索キーワード数(a) Gowalla

1

2

3

4

5

1250
1200
1150
1100
1050
1000

平均検索時間[msec]

検索キーワード数

1300

提案手法

2500

単純手法

2000

1500
1000
500
0

950
1

21

41

61

81

1

101 121 141 161 181

2

3

4

5

検索キーワード数

スコアリング関数の検索位置依存度 d(b) Brightkite(a) Gowalla

図 8 検索キーワード数の影響
検索キーワード数

1

500

2

3

4

5

450
400
350
300
250
1

21

41

61

81

101 121 141 161 181

スコアリング関数の検索位置依存度 d

枝刈りされたPOIの割合

550

平均検索時間[msec]

2

3000

1350

平均検索時間[msec]

4,376

単純手法

2000

データセット 構築時間 [sec]Gowalla

提案手法

2500

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

Gowalla1(b) Brightkite

図72Brightkite

3

4

5

検索キーワード数

d の 影 響図 9 枝刈りされた POI の割合

また，それぞれのデータセットについて，各検索キーワード数

つ平均検索時間が増加している．検索キーワード数が増加する

毎に最も平均検索時間が短くなった d の値を表 4 に示す．どちことで，キーワードの一致数のみが多い POI や，キーワードのらのデータセットでも，各検索キーワード数について，ある一一致数がある程度多くて他の属性値も良い POI など，様々な定のところまでは平均検索時間が短くなり続け，その後は急激

POI が現れる．よって，各 POI が支配する POI 数が少なくなに長くなっている．また，最適な d の値が 2 つのデータセット

り，支配関係の計算回数が増加してしまう．しかし，提案手法間で類似しているのは，この 2 つのデータセットの POI の位は単純手法に対し，Gowalla では 43%から 49%の時間で，そ置の分布が類似しているためである．

して Brightkite では 12%から 16%の時間で GSK スカイライ

表 4 検索キーワード数毎の最適な d
データセットンを検索している．
ここで，図 9 に，各データセットにおける，全 POI のうち枝検索キーワード数5

刈りされた POI の割合を示す．図 8 および図 9 から，枝刈り

Gowalla101 116 122 122 122により検索時間が削減されたことが分かる．また，2 つのデー

Brightkite

119 119 119 120 120

タセット間で平均検索時間や枝刈りされた POI の割合に大き

1

2

3

4

な差があるのは，表 1 のように，POI 数の差に対して，ユーザ
検索キーワード数の影響．図 8 に，検索キーワードの数を変え数，総友人関係数，および総チェックイン数に大きな差があり，たときの提案手法および単純手法の平均検索時間の結果を示

ソーシャル関係に関する属性値に差があるためである．

す．横軸は検索キーワード数，縦軸はランダムに選んだ 100 人

5. 関 連 研 究のユーザが GSK スカイラインを行った際の平均検索時間を表す．提案手法では，各データセットについて，各検索キーワー

位置情報サービスの普及により，地理的距離およびキーワー

ド数毎に表 4 に示される d を用いた．検索キーワード数の増加

ドに基づく検索についての研究が多く行われている [4] [9]．文に伴い，どちらのデータセットでも，それぞれの手法で少しず

献 [11] では，Top-k 検索によく用いられている IR(Inverted R)

木 [5] をスカイライン検索に用いており，地理的距離とキーワー

る検索では検索時間がかかりすぎるため，本稿では SKR 木とドに基づくスカイライン検索に R 木に基づくインデックスを用いうインデックスを用いたアルゴリズムを提案した．本稿で提いることの有効性が示されている．IR 木では，各ノードがその案したアルゴリズムは，SKR 木において探索するノード数を

子ノードの持つ全てのキーワードを転置インデックスにより管最適化でき，またソーシャル関係に関する属性値の性質を考慮理しているが，SKR 木では，各ノードの管理するキーワードがすることにより，高速に GSK スカイラインを検索できる．まどの子ノードに由来するものであるかを特定する必要がないた

た，実データを用いた実験から，提案手法は単純手法に比べてめ，転置インデックスを使用していない．また，文献 [9] では

検索時間を削減できることを確認した．

S2I(Spatial Inverted Index) というインデックスを用いること

本稿では，検索点を静的なものと想定したが，移動しながらにより，地理的距離およびキーワードに基づく Top-k 検索を効

スカイラインとなる POI をモニタリングすることも考えられ率的に行っている．S2I は転置インデックスによりキーワード

る．今後は，検索点が移動する場合でも効率的にスカイラインを管理しており，同時に，aR 木を用いてデータの管理を行っを更新する問題に取り組む予定である．

ている．この文献から，地理的距離，キーワードに加え，ある謝辞．本研究の一部は，文部科学省科学研究費補助金 · 基盤研

値を保持するデータを扱う場合，転置インデックスによりキー

究 (A)(26240013) および JST 国際科学技術共同研究推進事業

ワードを管理し，同時に aR 木を用いることが有効であると分(戦略的国際共同研究プログラム) の研究助成によるものである．

かる．本稿で用いた SKR 木が aR 木であるのは，この文献にここに記して謝意を表す．

着想を得ている．
地理的距離およびソーシャル関係に基づく検索についての研究も多く行われている [2] [13]．ソーシャル関係の定義には様々なものがあり，これらの文献ではその定義に基づく様々なインデックスが用いられている．文献 [6] では，地理的距離およびソーシャル関係に基づくスカイライン検索を提案しており，地理的距離についてのみ考慮するインデックスを用いた手法を提案している．しかし，これらの文献で扱われている方法では，地理的距離，キーワード，およびソーシャル関係の全ては考慮していない．
一方，地理的距離，キーワード，およびソーシャル関係全てに基づく検索についての研究も行われ始めている．文献 [1] はその一例であり，地理的距離，キーワード，およびソーシャル
関係に基づく Top-k 検索のフレームワークを示し，階層型インデックス GSKI(Geo-Social Keyword Index) を用いて効率的な検索を行っている．GSKI はグリッドに基づく木構造であり，各ノードは転置インデックスによりキーワードを管理している．また，GSKI の各ノードは，対応するグリッド内の POI
へチェックインしたユーザを，ブルームフィルタにより管理している．しかし，実世界において，POI の存在位置には偏りが存在する (例えば，郊外における POI 数よりも都市部におけるPOI 数の方が多いなど)．よって存在位置を考慮しないグリッドを用いると，グリッドの粒度が細かい場合，POI が存在しない領域に対応するノードが多くできてしまい，計算効率およびメモリの利用効率が悪くなる．また，グリッドの粒度が粗い場
合，POI が多く存在する領域に対応するノードの各属性値が良いものとなりやすく，枝刈りができないため，計算効率が悪くなる．そこで本稿では，R 木に基づく SKR 木を用いた．その他にも地理的距離，キーワード，およびソーシャル関係全てに基づく検索についての文献は存在する [10] が，スカイライン検索を扱っているものは，筆者らの知る限り存在しない．

6. お わ り に
本稿では，地理的距離，キーワード，およびソーシャル関係に基づくスカイライン検索問題に取り組んだ．単純な手法によ文

献[1] R. Ahuja, N. Armenatzoglou, D. Papadias, and G. J. Fakas.
Geo-social keyword search. In SSTD, pages 431–450. 2015.
[2] N. Armenatzoglou, S. Papadopoulos, and D. Papadias. A
general framework for geo-social query processing. PVLDB,
6(10):913–924, 2013.
[3] S. Borzsony, D. Kossmann, and K. Stocker. The skyline
operator. In ICDE, pages 421–430, 2001.
[4] X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi. Collective spatial keyword querying. In SIGMOD, pages 373–384,
2011.
[5] G. Cong, C. S. Jensen, and D. Wu. Eﬃcient retrieval of the
top-k most relevant spatial web objects. PVLDB, 2(1):337–
348, 2009.
[6] T. Emrich, M. Franzke, N. Mamoulis, M. Renz, andA. Züfle. Geo-social skyline queries. In DASFAA, pages
77–91, 2014.
[7] K. Mouratidis, J. Li, Y. Tang, and N. Mamoulis. Joint
search by social and spatial proximity. IEEE TKDE,
27(3):781–793, 2015.
[8] D. Papadias, P. Kalnis, J. Zhang, and Y. Tao. Eﬃcientolap operations in spatial data warehouses. In SSTD, pages
443–459. 2001.
[9] J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, andK. Nørvåg. Eﬃcient processing of top-k spatial keyword
queries. In SSTD, pages 205–222. 2011.
[10] P. Shankar, Y.-W. Huang, P. Castro, B. Nath, and L. Iftode.
Crowds replace experts: Building better location-based services using mobile social network interactions. In PerCom,
pages 20–29, 2012.
[11] J. Shi, D. Wu, and N. Mamoulis. Textually relevant spatial
skylines. IEEE TKDE, 28(1):224–237, 2016.
[12] Y. Tao and C. Sheng. Fast nearest neighbor search withkeywords. IEEE TKDE, 26(4):878–888, 2014.
[13] D.-N. Yang, C.-Y. Shen, W.-C. Lee, and M.-S. Chen. On
socio-spatial group query for location-based social networks.
In SIGKDD, pages 949–957, 2012.