DEIM Forum 2014 D6-6

経路スカイラインの近傍探査と対話型モバイルアプリケーション
小池実†

田中慶昭††

蒲原 智也†††

上島紳一 †††††,†††† 関西大学大学院総合情報学研究科 〒 569–1095 大阪府高槻市霊仙寺町 2-1-1†† 関西大学総合情報学部 〒 569–1095 大阪府高槻市霊仙寺町 2-1-1††† 関西大学先端科学技術推進機構 〒 564–8680 大阪府吹田市山手町 3-3-35
E-mail: ††††ueshima@res.kutc.kansai-u.ac.jp
あらまし経路スカイラインは, 利用者選好コスト関数に対するパレート最適解の集合であり, 多様な選好経路を与えるため, 経路計画, 散策計画, 施設配置, 工程管理, グラフ航行等の様々な分野での応用が期待できる．著者らは経路スカイラインの任意の部分経路がスカイラインであることに着目して, 部分領域の全対経路索引を用いた経路スカイライン集合の 2 段階抽出手法を提案している. しかし経路スカイラインは, 最短経路とは異なり, グラフ上の 2 点間に対して複数経路存在するため, 離れた 2 地点間の経路を抽出する場合は, 経路索引の組合せ数が増大する特徴を持つ. 本稿では, この点に対処するため, 経路スカイラインの特徴を用いて必要な経路索引を選択的に指定して, 探査領域を刈込んで経路スカイラインの近傍経路を効率的に抽出する手法を提案し, その効果を検討する. さらに国土地理院数値地図とGoogle Map を用いるモバイル対話型インタフェースを試作して利用者選好と経路探査について議論する.
キーワード

経路スカイライン，経路探査, グラフ，ボロノイ領域, モバイルアプリ

1. は じ め に経路スカイラインは, 利用者選好コスト関数に対するパレー

2. 関 連 研 究[経路スカイライン探査と応用] 経路スカイライン計算は, 多次ト最適解の集合であり, 多様な選好経路を与えるため, 経路計画,元データのスカイライン計算と異なり, グラフ探査が必要であ

散策計画, 施設配置, 工程管理, グラフ航行等の様々な分野でのる. Kriegel ら [2] はランドマークを参照点とする距離索引を生応用が期待できる [1], [2], [4]．著者らは経路スカイラインの任成し, 距離の三角不等式を用いて経路刈込みをしながら探査を意の部分経路がスカイラインであることに着目して, 部分領域行う手法を提案している. さらに Open Street Map [18] を用い,の全対経路索引を用いた利用者選好経路のスカイライン集合のParos [5], Mario [6] などの利用者選好経路の選択・呈示のための2 段階抽出手法を提案している [1]. しかし経路スカイラインはGUI を作成している. Yang ら [3], Tian ら [4] は各属性の最小経グラフ上の 2 点 v s , vt に対して複数経路存在するため, 提案手法

路コストを用いて刈込みを行う探査法を提案している.

では離れた 2 地点間の経路を抽出する場合, 経路索引の組合せ[多次元データのスカイライン近傍探査] Jin ら [7] はスカイライ数が大きくなる特徴を持つ.

ンのみならず近傍オブジェクト集合の抽出法について議論してそこで本稿では, まず経路スカイライン集合の通過領域を調いる. 吉武ら [15] は, 多次元データのスカイライン近傍探索演算べ, 探査実行処理において経路索引を指定することで探査領域を実装している. 経路スカイラインの近傍探査の研究はない.

を刈込んで, 経路スカイラインの近傍経路を探査する手法につ[最短経路集合と経路コヒーレンス] Samet らは, 地図上の最短いて検討する. ここでは, まず, v s , vt を指定した経路スカイライ

経路集合に対して出発地点のエッジに応じた到達地点の領域分ンの各経路の通過領域をネットワークボロノイ領域 [16], [17] の割（SILC 構造) [8], [9], また近傍領域 Gi の点から離れた近傍領隣接関係を用いて特徴付け, さらにエッジ属性の相関と経路の域 G j 内の点への最短経路集合が同一部分経路を共有する特性

通過領域, また領域を指定して探査した場合の抽出経路などに（経路コヒーレンス）を用いて最短経路集合を分割し, 経路を圧ついて議論して近傍探査の動機付けを行う.

縮格納する手法 (PCPD 構造) を提案している. これにより最短

次に, 各次元の最短経路が通過するネットワークボロノイ領域の隣接領域を探査範囲として経路スカイラインの近傍を探査

経路の部分と領域を対応付けている [10], [11].

[提案手法] 先行研究で提案した経路スカイラインの部分領域のする手法を提案し, その効果を探査実行時間, アクティブ探査リ

全対索引 [1] を効率的に利用する目的で, 経路の通過領域をボロストの動きなどを評価して関連手法と比較しながら議論する.

ノイ領域を用いて特徴付け, 領域単位で探査領域を指定して近その結果, 近傍経路が効率的に抽出できることを確認する.

傍探査を高速に実行する手法を提案し評価している. さらにモさらにモバイル環境を想定してアンドロイド端末上に経路バイル環境を想定しアンドロイド端末で国土地理院数値地図と探査アプリケーションを試作し, 国土地理院数値地図 [19] とGoogle Map を用いて, 経路スカイラインや近傍経路を探査する

Google Map を用い, 端末での利用者による対話型操作とサーアプリケーションを構築し, 対話型操作とサーバー側での経路バー側での経路探査手順を関係付け, 経路スカイラインの利用探査手順を関係付け, 利用者選好に依存して適応的に探査アル法について議論する.

ゴリズムを利用する方法について議論している.

3. 経路スカイラインとボロノイ領域
3. 1 経路スカイライン[経路と経路コスト]V をノード集合, E をエッジ集合,W をエッジコストとする時, G(V, E, W), (N = |V|, M = |E|, W ⊂ Rd+ ) を多次元コストグラフという (以下, 単に G とも書く). G 上の経路

p = (v1 , v2 , . . . , vk ), vi ∈ V に対して，経路コストを各ノード間∑エッジの属性の和, すなわち costl (p) = k−1
i=1 w((vi , vi+1 ))l とする.
ここで w((vi , vi+1 ))l はエッジ (vi , vi+1 ) の第 l 属性を示す. p の d 次

図 1 経路スカイラインの通過領域と番号付されたボロノイ領域′元コストベクトルは，cost(p) = (cost (p), . . . , cost (p)) である．
1d

[ 利 用 者 選 好 関 数] 経 路 p に 対 す る d 次 元 利 用 者 選 好 ベ
ク ト ル を Π = (π1 , π2 , . . . , πd )′ ∈ Rd>0 \{⃗0} と し, 選 好 関 数 を=∑
Pre fΠ (p) = dl=1 πl · costl (p) =< Π, cost(p) > とする.
[経路間の支配関係] G(V, E, W) 上の v s , vt 間のすべての経路をP(v s , vt ) = {(v s , . . . , vi j , . . . , vt ) j } とする時, p, q ∈ P(v s , vt ) に対しjjて，costl (p) < costl (q) (∃l, 1 <=l<= d), cost (p) <= cost (q) (∀1 <=j<= d ∧ j , l) が成り立つ時， p が q を支配しているという．

経路スカイライン集合 RS (v s , vt ) とは,G 上の 2 点間 v s , vt に

図 2 第 j 隣接領域までに含まれる (v s , vt ) 間経路スカイラインの割合(N = 5284,p:母点選択確率，エッジコスト：正の相関)対して定まり, 互いに支配されない経路の集合をいう. 特にRS (v s , vt ) は, Pre fΠ (p) で πi = 1, π j = 0( j , i) にあたる v s , vt 間の次元毎の最短経路 spd を含む [1], [2].

4 章で G の部分領域を指定して探査する場合の経路スカイラインについて議論する. このため G 全領域を対象として得られる経路スカイラインを RS (v s , vt ; G), また Ĝ ⊂ G を対象とした経路スカイラインを RS (v s , vt ; Ĝ) と記す.

3. 2 ボロノイ領域を用いた通過領域の特徴付け

図 3 第 j 隣接領域までに含まれる (v s , vt ) 間経路スカイラインの割合(N = 5284,p:母点選択確率, エッジコスト:負の相関)

本節では, ボロノイ領域の隣接関係を用いて G 上で次元毎の最短経路と経路スカイラインの通過領域の関係を確認する.

3. 2. 1 ボロノイ領域の番号付け
まず次の手順で次元毎の最短経路の通過領域から順にボロノイ領域の番号付けを行う.
（ 1 ） 2 点 v s , vt に対して属性毎の最短経路を求める.
（ 2 ） 各次元の最短経路の通過領域を 0 領域とし, 0 領域から 1 隣接離れるごとに１を加算して各領域に番号付け, すべての領域が番号付られるまで繰り返す.
これにより, p ∈ RS (v s , vt ) の通過領域を番号列で表すことができる. この番号列の中の最大数 j とし, p は最短経路に対して j隣接であるという. j は p が最短経路からの最も離れた領域の番号を示す. なお, 最短経路は次元毎に d 本存在するので, 各最短経路から数えた p の値が異なる場合は小さい値をとるものとする. また簡単のため番号付けられたボロノイ領域についてもj 隣接であるという.
[例 1] 図 1 は 2 次元の場合 (d = 2) の例である. 2 点 (v s , vt ) に対して黄線, 赤線が各次元の最短経路を示し, それらを含めて緑線,青線の残り 2 本が経路スカイラインである. 青線の通過領域は,
番号列 {0, 0, 0, 1, 2, 1, 0, 0} と表せ, 青経路は 2 隣接である. 緑経路の通過領域は, {0, 1, 1, 0, 1, 1, 1, 1, 0} となり 1 隣接である.

Note: 本稿ではノード間ホップ数を基準にノードネットワークボロノイ分割している [1], [14]. このため, G のノードの次数が一様である場合, 母点選択確率 p に対してボロノイ領域当たり√の平均ノード数は 1/p となり, 縦横のホップ数は 1/ p となる.
√
従って j 隣接の経路は最短経路通過領域から見て, 最大 ( j/ p)のホップ数離れていることになり, v s , vt 間のボロノイ領域を幅√(2 j/ p) ホップ幅に存在することになる.

3. 2. 2 RS (v s , vt ) の通過領域の特徴付け
次に RS (v s , vt ) に含まれる経路と隣接数の関係を調べる.

[通過領域と隣接数の関係]
図 2,3,4 に, G(N = 5284) に対して, 第 j 隣接ボロノイ領域に含まれる経路スカイライン数の |RS (v s , vt )|(v s , vt 間の全スカイライン経路数）に対する割合を示す. hop は (v s , vt ) 間ホップ数を示し, p は母点選択確率を示し, ボロノイ領域内のノード数を示
す. また各図では，エッジの第 1 属性を距離とし，第 2 属性として，図 2 は正の相関 (相関係数 r = 0.92154), 図 3 は負の相関(r = −0.92154), 図 4 は無相関 (r = −0.00572) の値を与えた．図2 上で青線（60 hop, p = 1/4）は経路スカイライン RS (v s , vt ) の70 パーセントが 0 隣接ボロノイ領域を通過することを示す．第1 隣接領域まで含めると 98 パーセントまで含まれる．
p を固定し, ホップ数を短く（実線と点線を比較）すると, ホップ距離が短いほど含有率は上昇する．結果的に, j = 2 の時, v s -vt
間ホップ数に関わらず 95 パーセント程度の経路が含まれる．またホップ数を固定し,p を変更すると， p が小さいほど, 各ボロノイ領域は拡大し１領域の経路数も増えて含有率は上昇するこを求め, j 隣接の値が小さい領域に対応する経路索引を用いて探査すれば当該経路に近い選好を持つ近傍経路が得られる.

•[多様な経路が必要な場合] 隣接数の大きい領域, 小さい領域, 中間領域と指定し, 経路スカイラインを計算する. この場合,多様な πi の値として, 例えば, (π1 , π2 ) = (0, 1.0), (0.5, 0.5), (1, 0)を与え, それぞれに最短経路を求めてそれらの近傍領域を指定
図 4 第 j 隣接領域までに含まれる (v s , vt ) 間経路スカイラインの割合(N = 5284,p:母点選択確率，エッジコスト：無相関)

して探査を行えば, それぞれの近傍経路が探査できる.
従って利用者の目的に応じて探査領域の指定したり, エッジ属性値の相関を考慮することができる.

6 章でモバイル環境を想定して利用者選好に応じて探査する方式を実装した対話型アプリケーションについて説明する.

4. 領域指定を用いた近傍探査法
4. 1 基本的な考え方
前節で確認したように経路スカイラインは利用者選好 π に応じて各次元毎の最短経路を基準に隣接するボロノイ領域を指定し探査を行って得られる. G 上の 2 点 v s , vt に対して次元毎の最短経路は経路スカイラインに含まれるため, 最短経路を最初に
図 5 エッジの属性間の相関関係による経路の違い求め, その近傍を対象領域として指定して探査する方法が考えられる. これにより π に応じて探査に方向性を与え, 探査対象となる部分領域の数を小さく抑えることができる.とが確認できる．

[エッジ属性値の相関と経路スカイライン] 図 5 に d = 2, 同一の

この時, 探査領域が G でなく, 部分グラフ Ĝ ⊂ G となるため,

v s , vt に対してのエッジ属性値の相関を変化させた場合の経路を探査の結果得られる経路スカイライン集合は RS (v s , vt , G) でな示す. 左図が正の相関 (相関係数 r = 0.92154), 中図が負の相関

く, RS (v s , vt , Ĝ) であり, 前者の近傍経路集合となっている. つま(r = −0.92154), 右図が無相関 (r = −0.00572) の場合の次元毎のり, RS (v s , vt , G) , RS (v s , vt , Ĝ) である. ここでは先行研究 [1] で最短経路 (赤線) と経路スカイライン (青線) を示す. ここでは道の探査実行処理に領域指定を追加する. 次に近傍探査法につい路網応用を想定して第 1 属性を距離とし, r を指定して第 2 属性て述べる.

4. 2 事 前 処 理を生成している.
・正の相関がある場合: 2 つの最短経路 sp1 ,sp2 の間隔は狭い.

事前処理として G を先行研究 [1] に基づきノードネットワー

これは経路を進むに従って互いに相関のあるエッジの属性値がクボロノイ分割し, 得られた部分領域とそれに対する全対経路加算されるため, sp1 ,sp2 は互いに近い経路となる.

スカイライン探査を行い，それによって生成された経路索引をNote: G が道路網の場合, 第 1 属性として距離を用いることが多構成する．

く, 探査結果も距離が基準となっている地図を用いて可視化す

4. 3 探査実行処理るため, 結果的に狭い間隔の経路が得られる. 同様に, 経路スカ（ 1 ） v s , vt を定める

イラインも最短経路の近傍に存在し, 小さな隣接数値のボロノ（ 2 ） G 上で属性毎の最短経路探査を行い，3. 2. 1 の方法でイ領域に含まれる.

ボロノイ領域を番号付ける．

・負の相関・無相関の場合:

この場合, 最短経路 sp1 が距離最（ 3 ） ボロノイ領域の隣接数 j を指定して部分グラフ Ĝ を抽短の経路を探すのに対して, sp2 の探査では, 距離の大きなエッ出する．

ジを探すことになり, 1 ホップで距離的に遠くまで行ける経路を（ 4 ） Ĝ を用いた処理の違いにより次の I・II に分かれる．

探すため, v s , vt 間の最短ホップ経路に近くなる. このため, sp1[提案手法 I] 一般に, Ĝ 上の経路スカイラインは, 複数の部分領と sp2 の間隔は広くなる.

域 Gi を跨いだ経路になる. このため，探査処理では経路索引かNote: 第 1 属性を距離と固定せず, 第 1，2 属性とも自由な値をら得る経路スカイラインを境界で延伸する. その時点で, 経路間とる場合, sp1 と sp2 と経路スカイラインは共に最短ホップ数経の支配関係を判定して刈込み処理を行いながら，vt まで経路の路の近傍に存在する.

延伸を繰り返す．vt への到達経路が発生すると，探査途中の経3. 3 議論

提案手法では, G の部分領域単位の全対経路スカイライン索路との判定，アクティブ探査リスト内の経路との判定を行う．
探査処理は，Ĝ 上では，経路の延伸操作と探査停止判定の両方引を用いているので, 前節のエッジ属性と経路スカイラインのの役割を担う．

通過領域の関係を用いて探査領域対象を指定できる.

[提案手法 II] 経路索引を使用せず，抽出したグラフの各ノード•[特定の選好 πi が大きい場合] 当該次元に対する最短経路に対して展開処理を行う．支配関係調査は提案手法 I に同じ．

[例 3] 数値地図大阪市中央部 (N = 5284) で v s , vt を固定し隣接図 7 G(N = 5284, OSAKA city), 0,1-adjacent graphsGˆ0 , Gˆ1 の経路スカイラインの属性コスト（それぞれ赤点, 黒点, 青点; p = 1/16)
図 6 G(N = 5284, 大阪市中央部), 第 0,1 隣接グラフ Gˆ0 , Gˆ1 の経路スカイライン集合 (最短経路:赤線, 経路スカイライン:青線; p=1/16)•

道路網を対象とする場合, ノード間ホップ数を用いて NV分割を行っているため, 参照座標系で定まるノード位置に関係
表 1 G, Gˆ0 , Gˆ1 のノード数とエッジ数 (N = 5284, p = 1/16)なく, G 上のホップ数で通過領域を指定できる. このため G 上

j 隣接数 ノード数 エッジ数 エッジ抽出比のノードの粗密に影響されにくく, ノードの隣接関係にのみ基G
Gˆ05284

8003

100%

893

1236

15.4%

Gˆ1Gˆ21863

2781

34.7%

2585

3878

48.5%

づいて刈込み処理が行える. 他分割法として四木分割やエリア
ボロノイ分割 [13] [17] では, 粗密の影響を受け, 探査対象領域指定による刈込み処理が難しい. また, NV 分割においてホップ数を基準に分割せず, 特定の属性 (例えば距離) で分割する場合もボロノイ領域を指定した提案手法で求められた経路スカイライ
ン RS (v s , vt ; Ĝi ) と RS (v s , vt ; G) の関係を調べる．

[隣接数と経路スカイライン]
図 6 左図において RS (v s , vt ; G) を示す．最短経路を赤線, 他の経路スカイラインに含まれるエッジを青線，その他のエッジを黒線で表している. |RS (v s , vt ; G)| = 135 である．
図 6 中図は， p = 1/16 でノードネットワークボロノイ分割を行い，第 0 隣接領域のみを抽出したグラフ Gˆ0 とそのグラフ上で求めた RS (v s , vt ; Gˆ0 ) である. |RS (v s , vt ; Gˆ0 )| = 104 であり, そのうち RS (v s , vt ; G) に含まれる経路が 104 本, 近傍経路が 47 本同様である.

•

領域指定により探査に方向性を与えることができ, 指定された部分領域の全対経路索引を用いて経路スカラインの近傍経路を効率的に求めることができる.

•

部分領域毎の経路索引であるので, 局所的なデータ更新に対応しやすい.

•道路網以外のグラフにも対応できる. その場合, 道路網と異なり, 結果の可視化手順を検討する必要がある.

•

エッジ属性の相関性を利用して隣接数の目安を考え, 探査領域を絞ることができる.

である．

5. 評

図 6 右図は第１隣接領域までを抽出したグラフ Gˆ1 に対する RS (v s , vt ; Gˆ1 ) である．|RS (v s , vt ; Gˆ1 )| = 139 であり, そのうち本節では数値地図を対象として領域指定をし, 部分領域の全RS (v s , vt ; G) に含まれる経路が 122 本, 近傍経路が 17 本である．
な お, 第 2 隣 接 領 域 ま で を 抽 出 し た グ ラ フ Gˆ2 に 対 す る
RS (v s , vt ; Gˆ2 ) はすべての経路スカイラインを含む．すなわちRS (v s , vt ; Gˆ2 ) ⊃ RS (v s , vt ; G) となる.
表 1 に G に対する Gˆ0 , Gˆ1 , Gˆ1 のエッジ抽出比を比較する.

[隣接数と経路コスト]
図 7 に経路スカイライン RS (v s , vt ; G)(赤点）ならびに 2 種類の近傍経路 RS (v s , vt ; Gˆ0 )（黒点）, RS (v s , vt ; Gˆ1 )（青点）に対する RAS(Route Atribute Space) [1] [2] を示す．同図の各点は抽出対象集合であるグラフ G, Gˆ0 , Gˆ1 から抽出された v s から vt への経路であり, 3 つの集合に対する経路スカイラインを示している．それぞれの経路スカイラインに含まれる経路が互いに支配されていないことが確認できる. また隣接数 j を大きくして各次元の最短経路からの抽出領域幅を広くすると, 近傍経路のコストも RS (v s , vt ; G) に収束していく様子がわかる.

4. 4 特徴

提案手法は次の特徴を持つ.

価対経路スカイライン索引を用いる提案近傍探査法の実行に関する評価を行う.

5. 1 対象データと評価方法[対象地図データ] 国土地理院数値地図 2,500(空間データ基盤，1/2,500 縮尺) [19] を用いた．エッジ属性として, 第 1 属性はノード間の実距離（m), 小数点以下 3 桁を用い，第 2 属性に 10 進数 2桁の一様乱数を与えた. これらの属性値間の相関係数は-0.00572であった．

[実行環境] SunOS 5.10 Generic 144500-19 32 sparcv9 プロセッ
サ (2530 MHz，浮動小数点プロセッサ付), 主記憶 32GB，Javaversion 1.5.0-20 である．
[比較対象] 次の 2 つの手法を用いた．
(I) グラフ分割を行わず, v s から経路間の支配関係のみを調査し探査する手法（ナイーブ法）(II) Kriegel らの参照点埋込み法による距離索引を用いた探査法 (ARSC) [2][評価方法]

図8

提案手法, ナイーブ探査法, 参照点埋込み法の探査実行時間の比較

図 10 探査途中に訪問した各グラフ (G, Gˆ0 , Gˆ1 , Gˆ2 ) 上のノード数

図 11
図 9 アクティブ探査リスト展開数•

各ノードで刈込まれた刈込経路数 (提案手法, ナイーブ手法, 参照点埋め込み法)

事前処理：提案近傍探査手法と (II) では，[1] に基づいて,数値地図データを読み込み経路索引と距離見積りを作成して出力した中間ファイル用いる．このため事前処理の評価しない.

•探査実行処理：中間ファイルを読み込んだ後，次元毎の最短経路を計算し, それらのボロノイ隣接領域を番号付ける. 次に (v s , vt ) とボロノイ隣接数 j を指定 (Ĝȷ を決めることに相当する) してから, 対応するすべての経路スカイライン RS (v s , vt ; Ĝȷ)を返すまでを測定した．

Note：(参照点埋込み法 ARSC）[2]
G 上のノード上に予め参照点を配置し，各ノードから参照点までの最短経路を属性毎に求めて距離見積りとする方法である．
探査実行時に三角不等式を用いて展開先ノードから目的地点までの属性毎の最低コスト値を見積もる．

5. 2 領域指定した場合の探査に関する評価
探査に関しては, G(N = 5284)(大阪市中央部）を用い, G 上に指定ホップ数の v s , vt の 100 通りの組合せを設定し, 結果データの上下 10 パーセントをカットして平均値を求めている.

[探査実行時間] 図 8 に提案手法を比較手法 (I)(II) の探査実行時間を示す. 横軸を v s , vt 間のホップ数, 縦軸を探査実行時間（msec)(対数軸) としている.
提案手法で, 隣接領域数 j が増加すると実行時間が増加するが, 他手法に比較して優れている. j = 0 の場合で 60hop だと提案手法 I では 2,525msec である.

[アクティブ探査リストの展開数]
図 9 に各手法の探査において, 展開途中の経路を格納するアクティブ探査リストの最大長について比較する. 提案手法では,探査対象グラフが G ⊃ Gˆ0 ⊃ Gˆ1 ⊃ Gˆ2 の関係にあるため, 探査実行時間, アクティブ探査リストのいずれにおいても小さいことが確認できる.

[訪問ノード数]
各手法では, 各ノードを通過する際に既に通過した経路との間で支配関係の調査を行い, 支配関係が成立すればその時点で図 12アクティブ探査リストの動き当該経路を削除する. このため, 探査過程で訪問したノード数が小さいほど, 探査時間が小さくなる (図 10).

[経路刈込数] 図 11 にすべてのノードで経路探査中に刈込まれた支配される経路の合計を示している．

[アクティブ探査リストの動き]
図 12 に探査開始から終了に至るまでのアクティブ探査リストの動きを示す.

6. 対話型モバイルアプリケーション
経路スカイライン探査法 [1] ならびに 4 章の近傍探査法により得られる経路集合の中から, 利用者が指定した重み Π に応じた最適な経路を呈示するモバイルアプリケーションを試作実装した. 本システムでは, サーバー側で現在地から地図上に配置された対象オブジェクトまでのパレート最適な経路集合を求め,利用者選好 π1 ,π2 を用いて, 利用者選好関数の値が最小となる経路を端末上に呈示する.

6. 1 利用環境と対象データ
ここでは, モバイル端末に Nexus7/Android 4.2.2 ,Google mapへのアクセスには Google maps android v2 を使用した. 地図デー
タは国土地理院数値地図 2,500(空間データ基 盤,1/2,500 縮尺)の京都府丹後市を対象としたデータを用いた. エッジ属性として, 第 1 属性はノード間の実距離 (m), 小数点以下 3 桁を用い, 第路スカイライン及び近傍値を持つ経路を呈示する.

[領域内オブジェクト集合への経路スカイライン呈示](機能) 2 点間の探査だけでなく,1 対多の探査を考慮した領域内オブジェクト集合抽出機能を持つ. この機能により，利用者の目的地が明確で無い場合でもパレート最適な経路を呈示する.

(処理手順) 利用者は地図上の任意の場所に図 13 右図の様な矩形領域を生成することができる. 利用者はプルダウンメニュー
で「居酒屋」「郵便局」等のカテゴリ, スライドバー a で領域サイズ, スライドバー b を用いて π1 ,π2 に対して重み付けをし,「カテゴリに該当」かつ「領域内に含まれる」の条件に当てはまる全てのオブジェクトを vt としてサーバに問合せを行う. サー
図 13

左図:システム画面例, 右図：矩形領域指定

バサイドでは全対ナンバリングデータを用いて v s から各 vt に該当するナンバリングのレコードを抽出し, ボロノイ領域への番号付けを行う. さらに π1 ,π2 に応じて適切な領域を抽出し, 部分領域の全対経路索引を用いて v s から各 vt 間の探査を実行する. その後, 利用者選好関数によって返される値が最小となる対象オブジェクト及び経路スカイラインを端末上に呈示する. なお, この機能においては経路スカイラインの内最も利用者選好を満たしている経路のみが呈示され, 近傍値を持つ経路は呈示されない.

7. お わ り に図 14システムの構成図

本稿では，経路スカイラインをボロノイ領域の隣接関係を用

2 属性に 10 進数 2 桁の一様乱数を与えた.
6. 2 構成・機能[構成] 本システムの画面例を図 13 の左図, システム構成図を図14 に示す. なお, 構成図中の全対ナンバリングデータとは全 v s ,vtの組合せの番号付けを記録したデータであり, 次の理由で保持している.

•ユーザが重み π1 ,π2 のどちらか一方に 1 と重み付けした場合, 利用者選好関数によって返される値が最小となる経路は該当属性の最短経路である. 提案手法では,3 節で示したとおり,ボロノイ領域に番号付けを行う際に最短経路を求めている. よって, 番号付け時と探査時の計 2 回, 最短経路を求めていることになる. 本アプリケーションではここでの効率性を考慮し, 事前処理として全 v s ,vt の組合せで番号付けを行ったデータをサーバサイドに保持する. このデータを全対ナンバリングデータとし,ユーザから探査が要求されると,v s ,vt に該当するナンバリングのレコードを抽出し, ボロノイ領域の番号付けを行う.

[v s , vt 間の経路スカイライン呈示](機能) v s は現在地とする. 目的地 vt および重み π1 ,π2 を指定することにより,v s から vt までの経路スカイラインを呈示する.

(処理手順) 利用者はテキストフィールドに vt を入力, スライ
ドバー b で π1 ,π2 に対して重み付けし, サーバに問い合わせを行う. サーバ側で全対ナンバリングデータを用いて v s , vt に該当するナンバリングのレコードを抽出し, ボロノイ領域への番号付け行う. その後 π1 ,π2 に応じて適切な領域を抽出し, 部分領域の全対経路索引を用いて v s , vt 間の探査を実行する. この処理により得られた経路情報を用いて端末は経路表示部に v s , vt 間の経いて特徴付け, 部分領域の全対経路スカイライン索引を用いた経路スカイラインの近傍探査手法を提案し評価した．さらに提案
手法の利用可能性を検討するため, 対話型モバイルアプリケーションを構築し, 利用者選好に応じた探査を行うプロトタイプシステムを構築した. 今後の課題としては，大規模グラフへの適用，経路スカイラインの特徴を利用した応用システムの開発などが挙げられる．
文

献[1] 蒲原智也, 小池実, 玉置和也, 壷内貴弘, 上島紳一, 部分領域の全対経路索引を用いた経路スカイライン問合せ処理手法の提案と評価, 第 6 回 Web とデータベースに関するフォーラム (WebDBForum) (2013)[2] H.-P. Kriegel, M. Renz, M. Schubert, Route Skyline Queries:
A Multi-Preference Path Planning Approach, Proceedings of the26th IEEE International Conference on Data Engineering (ICDE),
pp.261–272 (2010)[3] Y.Yang, J.X.Yu, H.Gao, J.Li, Finding the Optimal Path over MultiCost Graphs, Proceedings of the ACM International Conference onInformation and Knowledge Management (CIKM), pp.2124–2128(2012)[4] Y.Tian, K.C.K.Lee, W-C.Lee, Finding Skyline Paths in Road Networks, Proceedings of the 17th ACM International Conference
on Advances in Geographic Information Systems (SIGSPATIAL),
pp.444–447 (2010)[5] F. Graf, H.-P. Kriegel, M. Renz, M. Schubert, PAROS: Pareto Optimal Route Selection, Proceedings of the ACM SIGMOD International Conference on Management of Data, pp.1199–1202 (2010)[6] F. Graf, M. Renz, H.-P. Kriegel, M. Schubert, MARiO: MultiAttribute Routing in Open Street Map, Proceedings of the Lecture
Notes in Computer Science, Vol.6849, pp.486–490 (2011)[7] W Jin, J Han, M Ester, Mining Thick Skylines over Large Databases,
Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, pp.255–266 (2004)

[8]

[9]

[10]

[11]

[12]

[13]
[14]

[15][16]
[17]

[18]
[19]

Lecture Notes in Computer Science, Springer, Vol.32022002,
Knowledge Discovery in Databases: PKDD (2004)
J. Sankaranarayanan, H. Alborzi, H. Samet, Eﬃcient Query Processing on Spatial Networks, Proceedings of the 13th ACM International
Symposium on Advances in Geographic Information Systems(ACMGIS2005), pp.200–209 (2005)
H. Samet, J. Sankaranarayanan, H. Alborzi, Scalable Network Distance Browsing in Spatial Databases, Proceedings of the 2008 ACM
SIGMOD International Conference on Management of Data, pp.43–54 (2008)
J. Sankaranarayanan, H. Samet, H. Alborzi, Path Oracles for SpatialNetworks, Proceedings of the 35th International Conference on VeryLarge Data Bases(VLDB), pp.1210–1221 (2009)
J. Sankaranarayanan, H. Samet, Distance Oracles for Spatial Networks, Proceedings of the 25th IEEE International Conference onData Engineering (ICDE), pp.652–663 (2009)
M. Sharifzadeh, C. Shahabi, The Spatial Skyline Queries, Proceedings of the 32nd International Conference on Very Large DataBases(VLDB), pp.751–762 (2006)
H.Samet, Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann (2006).
蒲原智也，上島紳一, 道路網応用のための空間索引木の提案と最短経路探査への応用，情報処理学会論文誌データベース Vol.2,No.2, pp.10–28 (2009)
吉武亮, 宮崎純, 山本豪志朗, 加藤博一, スカイラインの近傍探索を可能とする拡張スカイライン演算の実装と評価, 第 4 回データ
工 学と情報マネジメントに関するフォーラム (DEIM2012) (2012)
M Erwig.: The Graph Voronoi Diagram with Applications, Networks, Vol.36, pp.156–163 (2000)
A. Okabe, B. Boots, K. Sugihara, S.N. Chin.: Spatial Tessellations:Concepts and Applications of Voronoi Diagrams, John Wiley(2000).
OpenStreetMap, http://www.openstreetmap.org
国土地理院：数値地図 (空間データ基盤)，http://sdf.gsi.go.jp/