DEIM Forum 2016 A2-2

多階層のカテゴリ分類を用いた SkySR 問合せの効率化について
佐々木勇和†,††佳治†

石川† 名古屋大学大学院情報科学研究科†† 名古屋大学未来社会創造機構
E-mail: †yuya@db.ss.is.nagoya-u.ac.jp, ††ishikawa@is.nagoya-u.ac.jp
あらまし

ビッグデータの特徴の一つは，多種多様なデータであり，レストランなどの地図上の PoI (Point of Interest)

も様々な属性値を保持するのが一般的になっている．近年では，PoI に多階層のカテゴリが付与されており，単純に目的のカテゴリの PoI までの経路を探索する場合においても，ネットワーク距離と意味的な距離の 2 つのスコアを考慮する必要がある．筆者らはこれまでに，スカイライン検索の考えを取り入れた SkySR(Skyline Sequenced Route) 問合せを提案し，効率的なアルゴリズムである BSSR 法を提案した．この検索では，ユーザは始点と順序付けされた複数の PoI カテゴリを指定し，ネットワーク距離と意味的な距離の両方の観点において支配されない経路を検索する．
本稿では，BSSR 法のコスト解析と最適化を目的とする．また，実データを用いたシミュレーション実験において，

BSSR 法が計算時間を大きく削減できることを確認する．
キーワード

経路探索，スカイライン検索，道路ネットワーク

1. は じ め に

R3AIntersection

H

p5

p2

p7
p10A

道路ネットワークにおける経路探索は広く普及しており，ス
マートフォンやカーナビゲーションシステムによる問合せは一般的になっている．本研究では，目的地となる終点を指定する問合せではなく，レストランなどの地図上の PoI (Point ofp1
I

q User-location
Food

p12
G

R2

q
G

p13

H

I

I

p3 p4 p6 p9 p8A

Asian Restaurant

I

Italian Restaurant

Shop & Service
G Gift Shop

p11

G

H Hobby Shop
Arts & Entertainment

Interest) のカテゴリを指定する問合せに着目する．ユーザは始R1

図 1: 道路ネットワークと PoI の例

点から指定したカテゴリに属する PoI までの経路を検索する．
今日では，多くの PoI 情報が Foursquare（注 1） などで公開されShop & Service

Foodている．PoI のカテゴリを指定する問合せのうち，最も基本的なものは最近傍問合せである．最近傍問合せでは，指定したカ
テゴリに属する PoI のうち，最も始点から近いものを検索結果

Asianとする．最近傍問合せの拡張として，シーケンスド経路問合せ

Japaneseがある．シーケンスド経路問合せでは，順序付けしたカテゴリ

Sushi

集合を指定し，そのカテゴリの PoI を順序通りに通過する経路

ItalianBakery

Gift
shop

Hobby
shop

Clothing
store

Men's
store

図 2: 木構造のカテゴリ分類

を対象とし，最もネットワーク距離が短いものを問合せ結果とする．
例 1 図 1 は，道路と PoI からなるグラフであり，q がユーザの現在地，p が PoI（丸が food，四角が shop&service (s&s)，
菱形が arts&entertainment (a&e)）を示している．正方形の 1
辺は長さ 1 とする．現在地を始点として，⟨food, a&e, s&s⟩ を順に訪問したいという要求に対して，シーケンスド経路問合せ
では R1 を出力する．

restaurant”, “bakery” をもっている．シーケンスド経路問合せにおいても，より詳細なカテゴリを指定することは可能である．先ほどの例 1 において，food を Asian restaurant などと指定することにより，それに適合した最短路を求めることができる．しかし，詳細なカテゴリを指定すると，ネットワーク距離が非常に長くなってしまう可能性があり，問合せ結果がユー
ザにとって好ましいとは限らない．また，ユーザは，どの PoIの影響により，ネットワーク距離が長くなったかを問合せ結果

既存のシーケンスド経路問合せでは，カテゴリの分類は一階から判断できないため，ユーザ自身がカテゴリの指定条件を変層と想定している．しかし，PoI のカテゴリは多様化しており，更しても，ネットワーク距離を効率的に短くすることは難しい．

Foursquare のように木構造のような多階層であることが一般的である（図 2 参照）．例えば，Foursquare のカテゴリ木では，そこで，筆者らは，指定したカテゴリと経路上の PoI の意“food” はサブカテゴリとして，“Asian restaurant”, “Italian

味的な距離と経路のネットワーク距離を指標とした Skyline

Sequenced Route (SkySR) 問合せを提案した [7]．SkySR（注 1）：https://developer.foursquare.com/categorytree問合せでは，意味的な距離とネットワーク距離を経路の指標と論文 [2], [6] では，終点を指定することを想定しているため，本して，他の問合せ結果の経路より意味的な距離およびネット

稿のシーケンスド経路問合せとは若干異なる．本研究では，オ

ワーク距離のどちらかが小さければ（スカイライン検索におけ

ンライン検索により実現するため，これらのインデックスは用る支配されていなければ），ユーザにとって有益であると考え，いない．

その経路は SkySR 問合せの問合せ結果に含まれる．これによ

グラフ上のスカイライン経路検索に関する研究も盛んに行わ

り，様々なカテゴリの組合せのシーケンスド経路問合せを実行れている [1], [4], [5], [10], [11], [13]．スカイライン経路検索のア

せずに，一度にユーザにとって有益な全ての経路を出力可能でルゴリズムは，Hansen [3] が二基準最短経路問題として初めてある．

提案した．この種のスカイライン経路検索では，グラフの枝に

筆者らはこれまでに効率的に SkySR 問合せを実現する Bulk

様々なコスト（移動距離，移動時間，信号機の数など）が割り

Skyline Sequenced Route Algorithm (BSSR 法) を提当てられており，経路は複数のコストをもつ．本研究において案した．BSSR 法では，まず，SkySR 問合せのネットワーク距も，ネットワーク距離と意味的距離という 2 つのコストを用い

離の上限値を最近傍問合せを基とした方法で求める．その後，るスカイライン経路検索である．しかし，これらの研究では，その上限値よりネットワーク距離が短い経路のみを探索する．

指定した始点と終点間の経路検索を想定している．複数の PoI

このとき，上限値を更新していくことで，計算範囲を削減する．

を指定する問合せを対象とするスカイライン経路検索は，著者

本稿の大きな目的は，BSSR 法のコスト解析とそれに基づく最らの知る限り我々の先行研究以外存在せず，単純に解決するこ適化である．最適化として，まず優先度付きキューの最適化をとはできない．

行なう．ダイクストラ法のように始点から最も近い節点から探索範囲を拡張すると，上限値が更新されづらく，探索範囲が広3. 予 備 知 識がってしまう．そこで，ネットワーク距離だけではなく，意味

本稿では，連結グラフ G = (V, E) を想定する．V および的な距離と経路内の PoI 数を考慮して，経路の優先度を決める．

E ⊂= V × V は，それぞれ節点集合および枝集合を表す．このさらに，BSSR 法では，既に探索済みの経路を重複して探索すグラフは，道路ネットワークや PoI 情報から作成されると想定る可能性がある．そこで，一時的に結果をキャッシュしておく

する．節点 v ∈ V のうち，いくつかの節点はカテゴリ c をもことで，無駄な探索を省くことを可能とする．

つものとし，カテゴリをもつ節点を PoI とする．v.c は節点 v

提案手法の評価として，実際の道路図と PoI を用いたシミュのカテゴリを表す．カテゴリはカテゴリ木に属しており，カテ

レーション実験を行なう．提案手法は，単純な手法に比べて，ゴリ木は C 個あるとする．ct(ci ) = ⟨c1 , c2 , . . . , ci ⟩ は，カテゴ

実行時間を大きく削減できることを確認する．

リ木において，カテゴリ ci から根までの経路を表す．PoI がカ

論文の構成は以下の通りである．まず，2. にて関連研究，3.

テゴリ ci に属している場合，ct(ci ) の内の全てのカテゴリに属にて問題定義についてそれぞれ述べる．その後，4. にて提案手しているとする．例えば，ct(sushi restaurant) = ⟨food, Asian

法について説明し，5. にて提案手法の性能評価を行う．最後に，restaurant, Japanese restaurant, sushi restaurant⟩ となるた

6. にて本稿をまとめる．

め，カテゴリが寿司店である PoI はレストラン，アジアンレス

2. 関 連 研 究
本章では，まずシーケンスド経路問合せとグラフ上のスカイライン経路検索について説明する．

トラン，日本食レストランにも同時に属している．c ∈ ct(ci )と記述した場合は，c は ci の経路上のカテゴリを表し，d(c) はカテゴリ c の深さを表す．カテゴリ c の祖先節点をスーパーカ
テゴリとよぶ．また，vi から vj 間の枝を e(vi , vj ) ∈ E と表し，

OSR (optimal sequenced route) 検索 [8] は，順序付けした

e(vi , vj ) は，重み e(vi , vj ).w (>= 0)（節点間の距離や移動時間

カテゴリ集合を指定し，そのカテゴリの PoI を順序通りに通など）をもつものとする．本稿では，無向グラフとして説明す

過する経路を対象とし，最もネットワーク距離が短いものを問るが，有向グラフへの拡張も容易である．

合せ結果とする．OSR 検索は，最初に提案されたシーケンス

3. 1 問 題 定 義

ド経路問合せである．論文 [8] では，道路ネットワークを対象

本稿で使用する単語と SkySR 問合せについて定義する．表として OSR 検索法として，ダイクストラベース法と PNE 法

1 は本稿で使用する記号を示す．

を提案している．SkySR 問合せを実現する最も単純な手法は，

OSR 検索を繰り返し実行する方法である．また，OSR 検索の

定義 1 (経路) 経路 R = ⟨v1 , . . . , vr ⟩ は，v1 から vr までのグ

インデックスとして様々な方法が提案されている [2], [6], [9]. 論

ラフにおける経路を表し，vi は PoI である．R[i] は R におけ

文 [9] では，ネットワークボロノイ図を事前に構築することで，る i 番目の PoI（つまり, vi ）を表す．さらに，R.c は R のカ

節点にそれぞれのカテゴリに対して最も近い PoI を計算なしでテゴリを表す（つまり，⟨v1 .c, . . . , vr .c⟩）．

求めることができる．論文 [6] では，ユークリッド距離を用い

R = ⟨v1 , . . . , vr ⟩ と v が与えられたとき，R⊕v = ⟨v1 , . . . , vr , v⟩て不必要な PoI の探索を防ぐ．このとき，それぞれの PoI 間のとする．

ユークリッド距離を計算するのはコストが大きいため，R 木を構築し，計算の効率化を行なっている．論文 [2] では，PoI 間の定義 2 (カ テ ゴ リ シ ー ケ ン ス) カ テ ゴ リ シ ー ケ ン ス S =最短路を事前に計算しておくことで，処理を効率化している．

⟨c1 , c2 , . . . , cs ⟩ は，順序付きのカテゴリ集合を表し，s はそシーケンス非類似度 dssim(S1 , S2 ) = 1 − ssim(S1 , S2 ) と定

表 1: 記号の要約

義する．

記号

意味

c

カテゴリ

C

カテゴリ木の個数

ct(c)カテゴリ木における c の経路

d(c)カテゴリ木における c の深さR

経路 ⟨v1 , . . . , vr ⟩r

R の PoI の数

（1 <
=i<
= s）を満たす場合，R = ⟨v1 , . . . , vr ⟩ はシーケンスドR[i]R の i 番目の PoI

経路 SR である．

R.c

R のカテゴリシーケンス

S

カテゴリシーケンス ⟨c1 , . . . , cs ⟩定義 6 (経路のスコア) カテゴリシーケンス S と始点 q が与s

S のサイズえられたとき，経路 R のスコアとしてネットワーク距離を表す

S[i]S の i 番目のカテゴリ

経路長 l(R) と意味的な距離を表す非類似度スコア ds(R) を定

Ssup

S のスーパーカテゴリシーケンス

義する．l(R) は以下の式で計算される．

次に，シーケンスド経路を上記の定義を用いて定義する．
定義 5 (シーケンスド経路) カテゴリシーケンス S が与えられたとき，2 つの条件 (1) r = s と (2) S[i] は vi .c に適合

SUP(S) S のスーパーカテゴリシーケンスの集合
ld(R)R の経路長sd(R)R の非類似度スコア

SR

シーケンスド経路

D(vi , vj ) は vi から vj への最短ネットワーク距離を表す．一方，SKY

スカイラインシーケンスド経路の集合

ds(R) は以下の式で計算される．

Sq

ユーザに指定されたカテゴリシーケンスq

ユーザに指定された始点

l(R) = D(q, R[1]) + Σr−1
i=1 D(R[i], R[i + 1]).

ds(R) = dssim(S, R.c).

(2)

(3)

どちらのスコアも小さい値の方がよりよい経路となる．
のサイズである．S[i] は S における i 番目のカテゴリ（つまり，ci ）を表す. Ssup = ⟨Ssup [1], . . . , Ssup [s]⟩（Ssup [i] は S[i]SkySR 問合せはユーザの要求に適合する全ての好ましい経もしくは S[i] のスーパーカテゴリ） (1 <=i<= s) を S における路を求める．つまり，SkySR 問合せの結果は，他の経路に支配

スーパーカテゴリシーケンスとよぶ．SU P(S) は S におけるされていない経路集合となる．支配と SkySR 問合せについて

スーパーカテゴリシーケンスの集合を示す．

定義する．

例 え ば ，S が ⟨Asian restaurant, a&e, gift shop⟩ の 場 合 ，

定義 7 (支配) 始点 q とカテゴリシーケンス S が与えられた

SUP(S) は ⟨Asian restaurant, a&e, gift shop⟩，⟨food, a&e,

とき，全てのシーケンスド経路を R とする．2 つのシーケンス

gift shop⟩，⟨Asian restaurant, a&e, s&s⟩， および ⟨food, a&e,

ド経路 SRi , SRj ∈ R が与えられたとき，ds(SRi ) < ds(SRj )s&s⟩ を含む．

か つ l(SRi ) <= l(SRj )，も し く は l(SRi ) < l(SRj ) か つds(SRi ) <ds(SRj ) の場合，SRi は SRj に支配されている．
=

定義 3 (カテゴリ類似度) 2 つのカテゴリ ca と cb が与えられたとき，カテゴリ間の類似度 sim(ca , cb ) ∈ [0, 1] は任意の関定義 8 (意味的な階層を用いた SkySR 問合せ) 始点 q とカ数で計算される．以下に 2 つカテゴリの関係を定義する．

テゴリシーケンス Sq が与えられたとき，スカイラインシーケ•

ca と cb が異なる木に属するカテゴリである場合，ca は

cb と無関係である．sim(ca , cb ) = 0．

ある．SkySR 問合せは，全てのスカイラインシーケンスド経路•

ca と cb が同じ木に属するカテゴリでる場合，ca は cb に適合する．0 < sim(ca , cb ) <= 1．
•

ンスド経路は他のシーケンスド経路に支配されていない経路でca と cb が同じカテゴリの場合，ca と cb は完全適合すを含む集合 SKY を問合せ結果とする．
ここで，スコアが全く同じ経路が出力される可能性があるが，る．sim(ca , cb ) = 1．

その場合そのうちの一つの経路を問合せ結果とする．

定義 4 (シーケンス類似度) 2 つのシーケンス S1 = ⟨S1 [1],

補題 1 SkySR 問合せは NP-hard である．

. . ., S1 [s1 ]⟩ と S2 = ⟨S2 [1], . . ., S2 [s2 ]⟩ が与えられたとき，

証明: 二基準最短経路問題は NP-hard として知られている [3]．

シーケンス類似度 ssim(S1 , S2 ) は集約関数 f で求められる．

二基準最短経路問題では，スカイライン経路の数がホップ数毎

ssim(S1 , S2 ) = f (h1 , h2 , . . . , hmin(s1 ,s2 ) ).

(1)に指数的に増加する可能性がある．一方，SkySR 問合せでは，経路のサイズ r が増加する度にスカイラインシーケンスド経路

hi (1 <=i<= min(s1 , s2 )) は，sim(S1 [i], S2 [i]) を表す．集約関数が指数的に増加する可能性がある．そのため，SkySR 問合せ

数 f は単調な関数で，全ての hi が 1 の場合, ssim(S1 , S2 ) = 1

は NP-hard である．□となる．また，f (h1 , h2 , . . . , hi−1 ) >= f (h1 , h2 , . . . , hi−1 , hi ) と想定する．

3. 2 単純なアプローチ行目）．Sq [s] に適合（完全でなくてもよい）する節点を発見し

SkySR 問合せを最も簡単に実行する方法は，カテゴリシーケ

た場合，そのシーケンスド経路を SKY に挿入する（12–14 行

ンス Sq の全てのスーパーカテゴリシーケンスに対して，OSR目）. この方法では，最大で d(Sq [s]) 個のシーケンスド経路を検索を実行する方法である．スーパーカテゴリシーケンス数は，∏si=1 d(Sq [i]) となり，全ての OSR 検索を実行するまで大きな一度に発見することができる．

時間がかかる．

Algorithm 1: シーケンスド経路の初期探索（最近傍ベース探索手法）

4. 提案アプローチ
本章では，まず提案したアプローチについて説明する [7]．そ1

procedure NNmethod(q, Sq )2

SKY ← ϕ, R ← ϕ;の後，コスト解析と最適化について議論する．提案アプローチ

3priority queue P Q ← {q};では，まず枝刈りのためにシーケンスド経路をみつけ，その後

4

for i : 1 to s do

5//execute s times Dijkstra algorithms

6

dist[u] = inf for all vertices u ∈ V ;7

dist[P Q.top] = 0;

SkySR 問合せの検索範囲は非常に広い．そのため，枝刈りを

8while P Q is not empty do

効率的に行なうことが重要である. 以下の 2 つの性質が定義よ9v ← P Q.dequeue;

BSSR 法を実行する．
4. 1 枝刈り条件と初期検索り明らかである．

10
11

if v is already visited thencontinue;

性質 1 非類似度スコアが 0 のシーケンスド経路より経路長が12大きいシーケンスド経路はスカイラインシーケンスド経路にな

13

SR ← R ⊕ v;

らない．

14

SKY.update(SR);15

性質 2 シーケンスド経路 SRi ∈ SKY と経路 Rj において，もし ds(SRi ) >= ds(Rj ) かつ l(SRi ) >= l(Rj ) の場合，Rj は不必要である．
まず，性質 1 は，非類似度スコアが 0 の経路の経路長が上限値となることを表す．そのため，探索中の経路が上限値より長くなる場合，すぐに枝刈りすることができる．性質 2 はさらに枝刈りできることを示唆している．経路長と非類似度スコアが既に発見しているシーケンスド経路より，どちらも大きくなる

16
17

if i = s and v matches Sq [i] thenif v perfectly matches Sq [i] thenbreak;
for each u for e(v, u) ∈ E do

18

if dist[v] + e(v, u).w < dist[u] then19

dist[u] = dist[v] + e(v, u).w;

20

P Q.enqueue(u);21R ← R ⊕ v;

22

P Q ← {v};23

return SKY;24

end procedure

場合，スカイラインシーケンスド経路にはならない．一方で，性質 2 は非類似度スコアが探索中の経路より小さいシーケンス
ド経路を発見できていない場合，枝刈りができないことも示している．そのため，初期検索では，少なくとも 1 つの非類似度
スコアが 0 のシーケンスド経路と，加えて他のシーケンスド経
路を探すことが重要である．
効率的な探索のために，最近傍ベース法を提案した．この手

4. 2 Bulk SkySR アルゴリズム
単純なアプローチは，複数回の OSR 検索が必要となるため効率的ではない．提案した Bulk SkySR algorithm (BSSR法) では，一度の問合せで全てのスカイラインシーケンスド経路を発見する．

法では，ダイクストラ法により，最も近い完全適合する節点をアルゴリズム 2 に BSSR 法の擬似コードを示す．SKY を最繰り返し探索する．S[s] と完全適合した節点を探索したとき，近傍ベース法で初期化し（2 行目），優先度付きキュー P Qbssr

非類似度スコアが 0 のシーケンスド経路を発見できる．この際，完全適合する節点を探索中に適合する（完全ではない）節点を発見することがある．これにより，コストの追加なしに複数のシーケンスド経路を発見することができる．
アルゴリズム 1 に最近傍ベース法の擬似コードを示す．まず，変数を初期化し（2 行目），優先度付きキュー P Q に始点を初期化する（3 行目）．そこから，口述する枝刈りダイクス
トラ法により，経路を徐々に広げていき，優先度付きキューが空になったら終了する（4–7 行目）．
効率的に SkySR 問合せを実行するためには，優先度付き
キュー内の経路数を少なくすることが重要である．そこで，

SkySR 問合せのためにダイクストラ法を拡張した枝刈りダイ

q を挿入する（3 行目）．優先度付きキューはキュー内の初期

クストラ法を提案した．アルゴリズム 3 に節点 vd からカテゴ

節点（最初の初期節点は q ）から最も近い節点を取り出す．そリ cd を探索する枝刈りダイクストラ法の擬似コードを示す．

の後，Sq [i] に完全適合する節点を繰り返し探索する（4–20 行目）．Sq [i] に完全適合する節点を見つけた場合，その節点を Rに挿入し，優先度付きキューをその節点で初期化する（21–22

ub(x) (0 <=x<= 1) は，SKY にあるシーケンスド経路のうち非類似度スコアが x 以下のシーケンスド経路の経路長の最小値を返す．枝刈りダイクストラ法のための優先度付きキュー P Qdij

Algorithm 2: BSSR アルゴリズム

4. 3 コスト解析
本節では，SkySR 問合せの時間コストを分析する．簡単化

1

procedure BSSR(q, Sq )2

SKY ← NNmethod(q, Sq );3priority queue P Qbssr ← ϕ;をもつ）と想定し，全ての節点が PoI でカテゴリは均一に位置

4

PrunedDijkstra(ϕ, S[1], q, P Qbssr , SKY);するとする．節点数および枝数をそれぞれ |V | および |E| と表

5

while P Qbssr is not empty do

す．節点数 N に対するダイクストラ法のコストを dcost (N ) と

6R ← P Qbssr .dequeue();表す．また，それぞれのカテゴリに属する PoI 数は同数（つま7PrunedDijkstra(R, S[r + 1], R[r], P Qbssr , SKY);り， |VC | ）とし，あるカテゴリが PoI に適合する確率は C1 となのために，正方格子グラフ（全ての節点が重み 1 の 4 つの枝

8return SKY;る．θ は，あるカテゴリに PoI が完全適合する確率を表す．実9

end procedure

際の確率の値は，PoI 数，節点数，カテゴリ木，および指定するカテゴリの深さに依存する．

は vd で初期化される（4 行目）．P Qdij は vd に最も近い節点を取り出す（6 行目）．経路 Rt は，Rd に取り出した節点 v を追加した経路で（7 行目），もし Rt の経路長が ub(ds(Rd )) より大きい場合，枝刈りダイクストラ法は終了する（8–9 行目）．v

正方格子グラフでは，半径 l 内にある節点数は 2l(l + 1) となる．少なくとも一つの完全適合する節点までの距離の最大値は，√
2·θ −1 +1−1
lmax = ⌊⌋ となる．距離 i で完全適合する節点が見2つかる確率 θi は以下の式で表される．



0




が cd に適合する場合，Rt の経路長を確認する（12–13 行目）．

Rt の経路長が ub(ds(Rt )) より長い場合，性質 2 に基づいてその経路は無視される．Rt がシーケンスド経路の場合，SKY は更新される（14–15 行目）．シーケンスド経路ではない場合，

P Qbssr に挿入される（16–17 行目）. v の隣接節点は v が cdと完全適合しない場合，P Qdij に挿入される（18–22 行目）．

Algorithm 3: 節点 vd からカテゴリ cd に適合する経路探索（枝刈りダイクストラ法）
1

procedure PrunedDijkstra(Rd , cd , vd , P Qbssr , SKY)2

dist[u] = inf for all vertices u ∈ V ;3

dist[vd ] = 0;4priority queue P Qdij ← {vd };5

while P Qdij is not empty do

6v ← P Qdij .dequeue;

7

Rt ← Rd ⊕ v;

8

if l(Rt ) > ub(ds(Rd )) then

9
10
11
12
13
14
15
16
17

18
19
20

break;
if v is already visited thencontinue;if v matches cd then
< ub(ds(Rt )) thenif l(Rt ) =if Rt is a sequenced route thenSKY.update(Rt );else
P Qbssr .enqueue(Rt );if v does not perfectly match thenfor each u for e(v, u) ∈ E do
if dist[v] + e(v, u).w < dist[u] then21

dist[u] = dist[v] + e(v, u).w;

22

P Qdij .enqueue(u);23

end procedureθi =(i = 0),

θ
 i−1



θi−1 · ((1 − (1 − θ)4i ))(i = lmax ),(otherwise).

ここで，始点は必ず完全適合する節点ではない（つまり，θ0 = 0）とし， θi = 1 − θi を示す．そのため，l の完全適合する節点ま∑ max
での期待値 le は，le = li=1
θi · i となる．初期上限値の最大値および期待値は，それぞれ s · lmax および s · le となる．初期上限値以内の節点数は，O(s2 · θ−1 ) でスケールする．最近傍ベース法の最大時間コストは，s 回の距離 lmax までのダイク
2
ストラ法のコストであるため，s · dcost (lmax) となる．
BSSR 法のコストは，(1) 枝刈りダイクストラ法の回数と (2)枝刈りダイクストラ法のコストに依存する．(1) と (2) ともに，上限値が重要な要素である．上限値が十分に小さい場合，枝刈りダイクストラ法の範囲が小さくなり，優先度付きキュー内の経路数も少なくなる．BSSR 法の探索範囲は，初期検索により，初期上限値より距離が短い節点のみとなる．まず，上限値を用いない場合，実行される枝刈りダイクストラ法の回数は，( |VCin | )s−1 （|Vin | は初期上限値より距離が短い節点の数）とな
る．上限値を用いる場合，探索中に経路が上限値より大きくなった経路は枝刈りされる．簡略化のため，全ての経路の上限
値を L とすると，以下の式で枝刈りダイクストラ法の回数を近
似できる．
1+

∑
4 s−1
C i=1

∑

i
∏

lk .

k=1
l1 ∈(1,··· ,L)l2 ∈(1,··· ,L−l1 )···li ∈(1,··· ,L−l(1,i−1) )この式では，lj は経路における vj−1（v0 は q ）から vj 間の距∑離を表しており，l(1,i) は ij=1 lj を表す. i は経路のサイズに対応しており，全ての経路のサイズにおいて，枝刈りダイクス
トラ法の始点の数を求めている．経路長が上限値 L を超える経路は枝刈りされるため，i が大きくなると，各 PoI 間の距離も大きなものを選択できなくなるので値は小さくなっていく．次に，枝刈りダイクストラ法のコストを求める．経路 R から次の PoIを探す探索範囲は，上限値から R の経路長を引いた値になるた
め，L − l(R) となる．そのため，経路 R から次の PoI を探索す
る場合の枝刈りダイクストラ法のコストは dcost ((L − l(R))2 )となる．最終的に BSSR 法のコストは，以下の式で表すことが
できる．

2

BSSRcost = dcost (L )
+

∑
4 s−1

∑

C i=1

l1 ∈(1,··· ,L)l2 ∈(1,··· ,L−l1 )···li ∈(1,··· ,L−l(1,i−1) )2dcost ((L − l(1,i) ) )i∏

表 2: データセット．fs と syn はそれぞれ Foursqure からの抽
lk .

k=1

実際の L は，経路 R の非類似度スコア ds(R) に依存するた出した実データと人工データを表す．
データセットTokyo
Cal
SynCalOL

位置
東京
カリフォルニア
カリフォルニア
オルデンブルグ

節点数
576,314
108,413105,240
30,525

枝数499,397
109,328
105,885
31,455

PoI 数
174,42187,36584,192
24,420

C
10
62
20
20

カテゴリ木
fs
syn
syn
syn

め，ub(ds(R)) となる．このコスト式より，上限値が小さいほどコストが下がることがわかる．

る．つまり，探索範囲を徐々に確実に小さくすることができる．

上限値を効率的に小さくしていくには，SKY を効率的に更(ds,r,l) は， (ds,l) より早くシーケンスド経路を発見すること新する必要がある．効率的な更新には，(1) シーケンスド経路ができるが， (ds,l) の方が経路長が短いシーケンスド経路をを発見するために必要な枝刈りダイクストラ法の回数，および早く見つける可能性がある．一方で，(r,ds,l) を選択した場合，(2) シーケンスド経路のスコアが重要である．そのためには，どBSSR 法は前者 2 つより早くシーケンスド経路を発見することの経路から探索していくかが問題とある．既存手法のように，ができるが，経路のスコアがどのような順番で見つかるかは予経路長のみを考慮して経路の探索順を決定する場合，シーケン測できない．前者 2 つの方が探索範囲をより小さくできるが，スド経路を発見するためには多くの PoI を探索しなければなら

後者はキュー内の経路数をより小さくすることができる．これない．なぜなら，経路長が短い経路は，経路内の PoI 数が少な

らの効率性は環境に依存する．

い可能性が高いためである．さらに発見したシーケンスド経路

4. 4. 2 一時的なキャッシュの非類似度スコアが大きい可能性が高く，非類似度スコアが大BSSR 法は同じ節点から枝刈りダイクストラ法を実行する可きい経路は枝刈りの際にあまり有効ではないことが多い．また，能性がある．そこで，枝刈りダイクストラ法の結果（vd から適別の問題として，枝刈りダイクストラ法の始点となる PoI 数は合した PoI とその PoI までの距離）を一時的にキャッシュし，(s − 1) · |VCin | であるにも関わらず，枝刈りダイクストラ法の実行回数が s · |VCin | より多いことである．PoI 数と s に比例して再利用する．しかし，一時的なキャッシュにより，枝刈りダイ

増加するべきで，この点においてもコストを削減できる．

い．枝刈りダイクストラ法の結果を再利用できない場合が存在

4. 4 最 適 化

クストラ法の実行回数が最大で (s − 1) |VCin | になるわけではな
する．

最適化方法として，まず優先度付きキュー P Qbssr からどの経路を優先的に取り出すかを議論する．さらに，枝刈りダイク

補題 2 同じ節点からの枝刈りダイクストラ法の探索範囲がストラ法の結果を再利用するキャッシュを提案する．

ub(ds(Rd )) − l(Rd ) より小さい場合，枝刈りダイクストラを再4. 4. 1 優先度付きキュー内の経路の順序
従来のダイクストラ法では，始点から最も近い節点をキューから優先的に取り出す．同じ方法を BSSR 法に用いた場合，上限値は効率的に更新されない．経路の優先度として，以下の経路の 3 つの要素を考える．

•

l: 経路長（小さいほうがよい）．

•

ds: 非類似度スコア（小さいほうがよい）．

•

r: PoI 数（大きいほうがよい）．

要 素 の 優 先 度 の 順 番 と し て ， (l,ds,r), (l,r,ds), (ds,l,r),(ds,r,l), (r,l,ds), と (r,ds,l) の 6 つが考えられる．これらの要素の組合せを分析する．

•

l を最重要とした場合，BSSR 法は優先的に始点 q に近い範囲を探索する．l は基本的に全ての経路で異なる値をもつ
ので，他の要素は無関係となる．

•

r を最重要とした場合，BSSR 法は深さ優先探索となる．

同じ値の r をもつ経路は多数存在するので，2 番目の優先度影
響する．

•

ds を最重要とした場合，BSSR 法は完全適合する節点を優先的に探索する．同じ値の ds をもつ経路は多数存在するので，2 番目の優先度影響する．
最適な優先度として，3 つの優先度 (ds,l), (ds,r,l), と (r,ds,l)が考えられる．(ds,l) もしくは (ds,r,l) を選択した場合，BSSR
法は非類似度スコアが小さい順にシーケンスド経路を発見す

度実行する必要がある．
証明: 探索範囲は経路のスコアに依存し，最大探索範囲は

ub(ds(Rd )) − l(Rd ) となる．これから探索する経路の探索範囲
が ub(ds(Rd )) − l(Rd ) より大きい場合，正しい結果を得ることができないのは自明である．□

5. 実

験

全てのアルゴリズムは C++で実装され，CPU が Intel(R)Xeon(R) CPU E5620 @ 2.40GHz で，メモリが 32.0GB の計算機を用いた．

5. 1 セッティング
アルゴリズム．単純手法（NAIVE），上限値を用いた単純手法（UOSR），および BSSR 法を用いて評価する．NAIVE とUOSR では，ダイクストラベース法と PNE 法を OSR 検索ア
ルゴリズムとして用いる．BSSR 法では，4 つの優先度 (ds,r,l),(r,ds,l), (ds, l), および (l)，と一時的なキャッシュを用いる
場合と用いない場合の 8 つのパターンを評価する．例えば，BSSR(ds,r,l)cache は，優先度が (ds,r,l) で一時的なキャッシュを用いた場合を示す．評価基準は，CPU 時間，最大メモリ使
用量（RSS），スカイラインシーケンスド経路数とする．
データセット. 実験では，複数種の道路図を用いる．グラフは，距離を枝の重みとして用い，無向グラフとする．全てのグラフ
は隣接リストにより実装する．表 2 は，データセットの位置，

表 3: 実験結果の概要．カテゴリシーケンスのサイズは 4 とする．
Tokyo
CPU time

Cal

SynCalRSS

CPU time

RSS

CPU time

OL
RSS

CPU time

RSS

BSSR(ds,r,l)cache

3.36 sec

339.5 MB2.50 sec

59.2 MB0.37 sec

50.6 MB0.27 sec

16.0 MB

BSSR(r,ds,l)cache

3.27 sec

301.6 MB3.29 sec

51.7 MB0.46 sec

50.3 MB0.38 sec

15.5 MB

BSSR(ds,l)cache

3.90 sec

339.5 MB2.31 sec

68.2 MB0.40 sec

50.5 MB0.30 sec

16.7 MB

BSSR(l)cache

4.12 sec

337.4 MB3.03 sec

81.3 MB0.62 sec

51.4 MB0.64 sec

18.0 MB

BSSR(ds,r,l)5.38 sec

316.7 MB3.96 sec

51.7 MB0.39 sec

49.9 MB0.32 sec

15.8 MB

BSSR(r,ds,l)5.69 sec

299.1 MB5.20 sec

51.9 MB0.49 sec

49.6 MB0.44 sec

15.5 MB

BSSR(ds,l)5.93 sec

317.2 MB3.63 sec

58.8 MB0.38 sec

49.5 MB0.33 sec

16.4 MB

BSSR(l)6.74 sec

318.3 MB5.20 sec

68.3 MB0.61 sec

49.5 MB0.77 sec

17.6 MBUOSR(PNE)

338.9 sec

306.3 MB84.7 sec

52.8 MB6.29 sec

49.2 MB4.73 sec

15.5 MBUOSR(Dij)

17.6 sec

333.5 MB6.47 sec

60.2 MB5.41 sec

50.2 MB1.82 sec

15.6 MB

NAIVE(PNE)

835.3 sec

307.6 MB329.9 sec

54.4 MB9.45 sec

48.8 MB15.4 sec

16.1 MB

NAIVE(Dij)5847 sec

18.4 GB

178.9 sec

543.4 MB49.1 sec

150.4 MB72.3 sec

93.2 MB# of SKY# of SKY# of SKY# of SKY

3.69

6.04

7.24

6.32

All algorithms

節点数，枝数，PoI 数，カテゴリ木の個数，カテゴリ木の種類

データセットにより最もよいものは異なるが， (ds,r,l) が全てを示す．Tokyo データセットでは，道路ネットワークは openのデータセットで比較的小さい CPU 時間を達成している．一（注 2）から，PoI は Foursquare から取得した．それ

時的なキャッシュは CPU 時間を削減するが，RSS が増加する．

ぞれの PoI を最も近い枝に埋め込み，カテゴリ木は実データを

しかし，この結果では，RSS はデータセットのサイズに大きく用いる．カリフォルニアとオルデンブルグの道路図はウェブか依存しているため，増加率は大きくない．最適化を行なっていstreet map

ら取得した

（注 3）

．Cal データセットでは，PoI の位置とカテゴ

リは実データだが，カテゴリ木はない．SynCal データセット

ない BSSR 法（つまり，BSSR(l)）は，BSSR(ds,r,l)cache に比べて CPU 時間が 2 倍程度大きくなっている．

と OL データセットは，道路図上に PoI をもっていないため，

ダイクストラベース法と PNE 法を用いた UOSR を比較す

枝の上に一様に PoI を生成する（つまり，全ての枝上で PoI 数

ると，ダイクストラベース法を用いた方が CPU 時間が小さい．

はほぼ同数である）．Cal データセット，SynCal データセット，

上限値を用いる場合は，ダイクストラベース法の OSR 検索のおよび OL データセットにおいて，PoI は人工的なカテゴリ木

方が優れていることを示しているが，上限値を用いない場合は，を保持する．人工的なカテゴリ木は，高さが 3 でそれぞれの中

データセットに依存している．ダイクストラベース法を用いた

間節点が 3 つの子節点をもつ．それぞれの PoI はランダムでカ

単純手法の RSS が非常に大きい．これは，優先度付きキュー

テゴリ木の葉節点をカテゴリとして割り当てられる．

内の経路数が非常に大きくなっていることに起因する．この結

データセットに対して，サイズが s のカテゴリシーケンスをもつクエリを 100 個生成する．始点は，PoI となる節点以外の果より，キュー内の経路数が RSS に大きな影響を及ぼすことを確認できる．

節点からランダムに選ばれる．また，カテゴリシーケンス内のまた，全ての手法で同じ数のスカイラインシーケンスド経路

カテゴリは，ランダムに葉節点から選ばれるが，重複したカテを問合せ結果としているため，全ての手法が厳密解を求められゴリ木からは選ばない．カテゴリ類似度として Wu and Palmerていることを確認できる．

similarity measure [12]，シーケンス類似度として総乗を用い

5. 3 カテゴリシーケンスのサイズの影響る. 具体的には，以下の式で計算される．

まず Tokyo データセットにおける，BSSR 法のカテゴリシー

sim(ca , cb ) =max

cx ∈ct(cb )∏2 · d(common).
d(ca ) + d(cx )ケンスのサイズの影響を調べる．図 3 は，Tokyo データセット(4)

加すると，CPU 時間が大きく増加していることがわかる．一min(s1 ,s2 )ssim(S1 , S2 ) =における CPU 時間と RSS を示している．この図より，s が増

sim(S1 [i], S2 [i]).

(5)

時的なキャッシュは実データでより効果を発揮している．これi=1

は，同じ節点から枝刈りダイクストラ法が実行されやすいため

common は ca と cx の最も深い共通の祖先節点を表す．
5. 2 結果の概要
結果の概要を表 3 に示す．この結果より，一時的なキャッシュを用いた BSSR 法が全てのデータセットで最も小さい CPU 時間を達成していることがわかる．キューの優先度を比較すると，（注 2）：https://www.openstreetmap.org（注 3）：http://www.cs.utah.edu/˜lifeifei/SpatialDataset.htm

である．また，s が増加するにつれ，RSS も増加している．優
先度が (l) の場合に顕著である．これは，キュー内の経路が増加するからであるが，s が大きくなると優先度 (l) ではなかなかシーケンスド経路を見つけることができないためである．
図 4 は，s を変化させたときの各データセットにおけるスカイラインシーケンスド経路の数を示している．この結果より，Tokyo データセットのスカイラインシーケンスド経路の数が最40(rdl)cache(l)cache(rdl)(l)(drl)cache(dl)cache
(drl)
(dl)

1400
1200
RSS [MB](drl)cache(dl)cache
(drl)
(dl)

50
CPU time [sec]6. お わ り に

1600

60

30
20

1000

(rdl)cache(l)cache(rdl)(l)

本稿では，スカイラインシーケンスド経路（SkySR）問合せ

800のためのアルゴリズム BSSR 法の最適化を行なった．最適化を

600
400

10

実施する上で，まずコスト分析を行い，最適化の要素を検証し

200

0

0
1

2

3
4
Size of sequence s

51(a) CPU time2

3
4
Size of sequence s5(b) RSS# of SKY

図 3: s を変化させた場合の Tokyo データセットの結果た．最適化のために，キュー内の経路の優先度とダイクストラ
法の結果を一時的にキャッシュする方法を提案した．実データを用いた実験より，これらの最適化を用いると CPU 時間が半分程度になり，メモリ使用量もそれほど大きくならないことを
確認した．

10
9
8
7
6
5
4
3
2
1
0

Tokyo

Cal

synCalOL謝辞本研究は科学研究費（15K21069）の支援によって行われた．
ここに記して謝意を表す．
1

2

3
4
Size of sequence s5

図 4: s を変化させた場合のスカイラインシーケンスド経路数

Zoo
Sake
Sushi 1

Route 1

Sushi 2
Route 2Bar

q

Historical

図 5: 東京における出力経路の例

も小さいのがわかる．スカイラインシーケンスド経路の数は，CPU 時間や RSS に無関係であることがわかる．さらに，PoI
およびグラフどちらも実データを用いた場合，スカイライン
シーケンスド経路はそれほど大きくならないことも示している．

5. 4 出力経路の例
Tokyo データセットを用いて，スカイラインシーケンスド経路の検索結果の例を示す．この例では，カテゴリシーケンスは，⟨zoo, sushi restaurant, sake bar⟩ とし，始点は東京駅とした．
SkySR 問合せを用いることで，6 つの経路を見つけることができる．図 5 は，2 つの代表的な経路である．Route 1 (⟨zoo,

sushi 1, sake⟩) はユーザの要求するカテゴリに完全に一致した経路であるが，経路長は長い．一方，Route2 は，要求するカ
テゴリに完全に一致するわけではないが，経路長は非常に短い．
他の 4 つの経路はどちらかの経路に類似している（つまり，zooを含むか含まないか）．この例より，SkySR 問合せは旅行計画の決定に有効であることがわかる．

文

献[1] S. Aljubayrin, Z. He, and R. Zhang. Skyline trips of multiple
pois categories. In DASFAA, pages 189–206, 2015.
[2] J. Eisner and S. Funke. Sequenced route queries: Getting
things done on the way back home. In ACM SIGSPATIAL,
pages 502–505, 2012.
[3] P. Hansen. Bicriterion path problems. In Multiple criteria decision making theory and application, pages 109–127.
1980.
[4] H.-P. Kriegel, M. Renz, and M. Schubert. Route skyline
queries: A multi-preference path planning approach. In
ICDE, pages 261–272, 2010.
[5] E. Q. V. Martins. On a multicriteria shortest path problem.European Journal of Operational Research, 16(2):236–
245,1984.
[6] Y. Ohsawa, H. Htoo, N. Sonehara, and M. Sakauchi. Sequenced route query in road network distance based onincremental euclidean restriction. In DEXA, pages 484–
491,2012.
[7] 佐々木勇和, 石川佳治. 多階層のカテゴリ分類を用いたスカイラ
イン経路検索について. 第 7 回データ工学と情報マネジメントに関するフォーラム (DEIM 2015), 2015.
[8] M. Sharifzadeh, M. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. The VLDB Journal, 17(4):765–
787, 2008.
[9] M. Sharifzadeh and C. Shahabi. Processing optimal sequenced route queries using voronoi diagrams. GeoInformatica, 12(4):411–433, 2008.
[10] M. Shekelyan, G. Jossé, and M. Schubert. Linear path skylines in multicriteria networks. In ICDE, pages 459–470,
2015.
[11] Y. Tian, K. C. Lee, and W.-C. Lee. Finding skyline paths inroad networks. In ACM SIGSPATIAL GIS, pages 444–447,
2009.
[12] Z. Wu and M. Palmer. Verbs semantics and lexical selection.
In ACL, pages 133–138, 1994.
[13] B. Yang, C. Guo, C. S. Jensen, M. Kaul, and S. Shang.
Stochastic skyline route planning under time-varying uncertainty. In ICDE, pages 136–147, 2014.