DEIM Forum 2014 D6-5

道路網に対する全対最短経路索引に関する検討
田中翔†

壷内貴弘†

蒲原智也††

上島紳一 ††††,††† 関西大学総合情報学部 〒 569–1095 大阪府高槻市霊仙寺町 2-1-1†† 関西大学先端科学技術推進機構 〒 564–8680 大阪府吹田市山手町 3-3-35
E-mail: †††ueshima@res.kutc.kansai-u.ac.jp
あらまし

本稿では，道路網上の任意の 2 点間の全対最短経路の経路索引を生成する手法について検討する. 本手法

では最短経路の持つ経路コヒーレンスの特徴を生かすため, ノードの位置座標による領域分割を用い, 最短経路が領域分割線と交差してできる境界に着目して, 最短経路の部分経路と経路索引を生成する. これにより最短経路は出発地点と目的地点と境界の列を用いて表すことができ,最短経路抽出のみならず, 領域の包含関係を用いた刈込処理や道路網の詳細度に応じた経路の抽出が可能となる. 経路索引は, 全対最短経路集合の全データ量に対して小さく, モバイル応用などに利用しやすい特徴を持つ. 提案手法を評価するため, 国土地理院発行数値地図を用いて経路索引の生成時間,サイズ, 問合せ時間などを定量的に検討する. また経路索引のデータベース格納についても検討する．
キーワード

経路索引, 全対最短経路, 経路コヒーレンス, 道路網, グラフ

1. は じ め に

2. 関 連 研 究

近年, 大規模グラフに対して全対最短経路の高度計算環境を[経路コヒーレンス] Samet ら [6] は, 最短経路の出発地点の持つ利用した計算法の研究が進められている [1] [3] [4] [5]. 全対最短out エッジに着目してデータ集合を連続領域に分割できることに経路データは汎用性が高く，グラフ航行，旅程計画，工程管理着目したデータ構造 (SILC 構造) を提案している. この性質は到など様々な分野での利用が期待できる [2]. さらに，データを構達地点の経路コヒーレンスと呼ばれる. さらに Sankaranarayanan

造化して格納することで，最短経路計算を行う度にグラフを探らは最短経路集合に対して出発地点・到達地点間の経路コヒー査する処理が不要となり，複数の利用者間で経路データを共有レンスを定義し, 最短経路集合を経路コヒーレント対の集合にしたり，注釈を付けるなど，経路を属性付けて利用できる．
本稿では, 道路網応用を想定してグラフが参照座標系に埋め分割 (PCPD 分割) して四分木に格納する方法について議論している [7], [8], [9]. これにより最短経路を（出発地点, 目標地点, 中込まれているものと仮定し，全対最短経路データに対する経路間地点）の 3 つ組で捉え, 最短経路の距離情報と合わせて距離問索引を構成する手法について議論する. ここでは最短経路の経合せにも対応できる格納法を提案している. ここで中間地点は路コヒーレンス [7] [8] [9] を生かして，領域分割でできる境界にノードまたはエッジである. しかし, ノードが平面上に偏在する着目して，ノード位置を基準に道路網データから領域間全対最場合への対応や領域分割でのエッジの取扱いや不整形なグラフ短経路を生成し，木構造へ格納する. 一方, 最短経路の問合せ処への対応が必ずしも明確でない. Wu ら [10] は, 上記手法とノー

理では木構造を辿って境界を抽出し，最短経路を抽出する．問ドの重要度付けを用いる手法とを比較しながら評価している.

合せ処理はｚコードの接頭辞処理に帰着できる [11].

[部分領域の全対最短経路計算] Jing ら [12] は 2 次元方向に領域

提案手法は次の特徴を持つ．すなわちを分割してグラフを分割し, 部分領域での全ての地点間の最短•経路を前処理として計算し, 階層化したデータ構造 (経路ビュー)

最短経路の各部分を領域に対応付けることにより，領域の包含関係による刈込みを用いた問合せ処理が可能となる．

•整形・不整形なグラフにも適用することができる．また，経路の詳細度に応じた最短経路の抽出が可能である.

•経路索引のデータ量は，全対最短経路の全データ量に対を提案している。蒲原ら [13] は, グラフを NV 分割し [11], ボロ
ノイ領域毎に境界と母点からの全対最短経路を求めて経路索引を構成している. さらに隣接するボロノイ領域を統合して階層化し, 遠方の 2 点間の最短経路を求める手法を提案している.

して小さく，モバイル環境での最短経路探査，距離問合せ，範[提案手法] 最短経路を領域分割線でできる境界に着目し, ノー囲問合せ処理などを用いた位置情報サービスなどに利用できる．

ド位置による領域分割と, 次にエッジの接続関係をもとにした提案手法を評価するため, 国土地理院発行の数値地図 [14] を各最短経路の部分経路生成を行って, グラフ上の任意の 2 点間用いて，経路索引の生成時間，問合せ処理時間，サイズなどをを結ぶ最短経路の構成を問合せ処理で行っている. これにより定量的に評価する．さらに，経路索引をデータベースに格納し，出発地点と目的地点と境界の列を用いて最短経路を表すことがSQL を用いて検索を行う方法についても検討する.

でき, 二分木の高さに応じた境界列の飛び抽出などにより詳細

以下，2 節で関連研究について述べ，3 節で全対最短経路の特度に応じた経路の抽出が可能となる. またノード・エッジ位置

徴，4 節で経路索引の生成と抽出について述べ，評価し，5 節でに粗密のある不整形グラフにも適用できる. さらに経路索引を索引のデータベースへの格納と問い合わせ法を述べ，評価する．

データベースに格納し SQL を用いた検索法を検討している.

3. 全対最短経路集合
3. 1 定義と特徴
V をノード集合，E をエッジ集合 (E ⊂ V × V) とし，e ∈ E は非負値を属性値として持つグラフ G(V, E), (N = |V|, M = |E|) を考える (単に G とも書く)．本稿で G は無向グラフであり，参照座標系に埋め込まれていることとする．また，任意のノードv は，位置座標 (v x , vy ) を持つものと仮定する．

図 1 分割線 l1 , l2 による領域分割

G を道路網とみる場合は，交差点をノード，交差点を結ぶ道

Fig. 1 Region Splitting by l1 , l2

路片をエッジ，道路片の属性値をエッジの属性値とする．

[定義] (全対最短経路集合) G(V, E) 上の全ての 2 ノード間を結ぶ最短経路の集合を全対最短経路集合という. 各最短経路はG(V, E) 上の 2 ノード間に対して定義され, ノード列で表せる.
[特徴] 全対最短経路集合と各最短経路は次の特徴を持つ.
（ 1 ） 全対最短経路集合は N 2 の経路を含み, N >> 0 の場合,大規模データとなる.
（ 2 ） 最短経路の部分経路はその区間で最短経路である.
（ 3 ） 最短経路は経路コヒーレンスを持つ.

[Note] 上記 (3) で，G 上のある地点 v s から最短経路で到達可能なノード集合は，v s の第 1 エッジにより分類できる性質を，到達地点の経路コヒーレンスという [6]．また，出発地点 v s と目的地点 vt のそれぞれの近傍からの最短経路集合が，共通エッジ・ノードを持つ性質を経路コヒーレント対と呼ぶ．

[例 1]

図 2 で，赤色のエッジを共通エッジとして持つ最短経路集合が黄色部分であり，これは経路コヒーレンス対を示す．
つまり近傍領域にある v s , v′s から遠方領域にある vt , v′t への 2

図2

経路コヒーレンス (左：疎 (N = 960)，右：密 (N = 5284))

Fig. 2 Path Coherence (left : sparce (N = 960), right : dense(N = 5284)）

A1 を通過しないと到達できない最短経路が存在する．従って境界と交差する最短経路に着目すれば, 最短経路は両端ノード

v s , vt と通過する境界のリストを用いて次のように表せる.

つの最短経路は同一の部分経路 ψ(ψ はノードまたはエッジ）を(v s , [b j1 , . . . b jm ], vt , c), v s ∈ Ai , vt ∈ A j , i , j(1)持つ [7] [8] [9].

(v s , [b j1 , . . . b jm ], vt , c), v s ∈ Ai , vt ∈ Ai ,(2)上記の特徴を考慮し, 全対最短経路集合の格納構造に対する次の要件を挙げる.

但し i, j ∈ {0, 1} で，境界リスト [b j1 , b j2 , . . . b jm ] は，p が l1 を m[要件１] (3) より全対最短経路集合の各最短経路のノード列を回交差する場合を示し，式 2 で m は偶数，式 2 で m は奇数で全て格納するのではなく，領域の包含関係を利用しながら，最ある. c は v s , vt 間の最短経路のコストである．

短経路と部分経路の関係を組み込んで，格納する方法がよい.

[境界による全対最短経路集合の分割] 全対最短経路集合は分割[要件 2] (v s , vt ) の組に対して格納・抽出できる方法がよく，従線 l によって 4 種類の最短経路集合に分割される. すなわち来のデータベース技術を利用できることが望ましい．

(i) A0 内の 2 ノードを結ぶ最短経路で l1 と交差しない経路. 即

上記要件を考慮して, 提案手法では [7], [9] の手法を発展させ

ち A0 内にあるノード列で表せる最短経路集合.て, ノードの位置座標をもとにして領域分割を行い，最短経路(ii) A1 内の 2 ノードを結ぶ最短経路で l1 と交差しない経路. 即が交差する領域の境界に着目して，索引を生成する．

ち A1 内にあるノード列で表せる最短経路集合.

3. 2 領域分割線と全対最短経路集合の分割(iii) A0 内のノードから l1 を（1 回または奇数回）跨いで A1 内

[境界と最短経路] G に対して，水平・鉛直な領域分割線 l を引のノードに至る経路.

く．l と交差する G のエッジを境界エッジ (単に境界）といい，(iv) A0 内のノードから l1 を（2 回または偶数回）跨いで A0 内

境界エッジの両端のノードを境界ノードという．のノードに至る経路.

[例 2] 図 1 左のグラフで全対最短経路集合を考えると, 鉛直[例 3] 上記 (i)-(iv) の分割で境界から見れば, 各領域 Ai においな分割線 l1 に対して，b1 , b2 , b3 が境界となり, 境界ノードはそて Ai 内の全ての境界ノードから, 並列ダイクストラ法 [13] を実

れぞれ異なる 2 つの部分領域 A0 , A1 に属する．ノード v s ∈ A0

行すれば, 各境界から A0 内と A1 内でそれぞれ最も近い複数のからノード vt ∈ A1 を結ぶ最短経路 p(緑色) を考えると， p は必ノード集合が得られる．同様に右側領域に属す境界ノードからず 3 つの境界のうちの１つを通過する．但し，G が整形な場合，も同様にノード集合を分割できる. これは領域内の各ノードか最短経路が通過する境界は 1 つであるが，G が不整形 (図 1 右)ら最も近い境界を求めていることに相当する.の場合，v′s ∈ A0 , v′t ∈ A0 ) のように G 上では到達可能であって，l1 による分割後に A0 の部分グラフのみでは到達できず，一旦同様にして, 次に水平方向に集合を分割し, 分割を各領域にノードが１つになるまで繰り返すことができる.

4. 全対最短経路索引
3.2 節の全対最短経路集合の分割手順を用いて, 本節では G の全対最短経路の計算と, 全対最短経路のための経路索引の生成手順を述べる. 経路索引は二分木構造を持ち, G 上の任意の 2 点

v s , vt に対して木を辿ることで最短経路を求めることができる.
4. 1 生 成 手 順与えられた G に対する生成手順は以下の通りである.

図 3 領域分割と二分木(1) 二分木構造生成 参照座標系によるノードの位置座標を用

Fig. 3 Region Splitting and Binary Tree Representation (z-code)

いてトップダウンに領域を分割し，二分木を構成する (図 3)．

表 1 評価用国土地理院道路地図データ

すなわち二分木の根ノードを G の存在する全領域 S とした時,

Table 1 Road Map Data issued by GSI

S を鉛直線・水平線で交互に 2 等分し, ノード集合 V を領域内ノード数が 1 になるまで分割を繰り返す．1 となったとき， 各|N||M|

960

1,325921,600

GSI2 5,601 7,509

31,371,201

GSI1

ノード ID を自身が所属するユニークな領域コードに置換する．

全対最短経路数分割された領域 Ai のインスタンスはリストに格納され，i は
表2

図 3 のような z 曲線 [11] を用いた z コードで表現される. 生成

原データと経路索引のデータサイズ比較

Table 2 Size Comparison of Binary Tree and Original Graph Data

される二分木の高さは，o(log2 n) となる.

(2) 最短経路計算と境界エッジ生成 最下層レベルから順にボ

地図

原データ 全対経路

経路索引 二分木高さ 索引生成時間

トムアップに各レベルで領域内・領域間の全対最短経路と境界GSI1

180KB

222MB

39.2MB

2563,325msを求め, 境界エッジのデータを格納する.

GSI2

1,592KB

13.8GB

1.43GB

3222,646,154ms(2-1) 最短経路計算と境界エッジの番号付け 隣 接 領 域 間 の 全てのノードの組合せに対して最短経路計算を行い，それぞ定ノードとなったときに生成された最短経路ノード列が最短経れに関して境界エッジ b，コスト c を求める．

路を示す．

(2-2) 最短経路索引の格納 b，c と v s ，vt を (v s , [b j1 , . . . b jm ], vt , c)[Note] 前節のうち, 再帰的に木を辿る処理の呼び出し回数を制の形式とし，これを最短経路索引として，部分木に格納する．

限することによって，詳細度に応じた最短経路のノード列を抽(3) 全領域の最短経路索引生成及び格納 全ての領域において出できる．

(2) を実行し，最短経路索引を生成，格納する．

4. 3 評価[Note] 木構造は (1) で生成し，(2)(3) で全対最短経路及び境界[対象地図データ] 表 1 に示す国土地理院数値地図 2,500(領域エッジデータを小さな領域からボトムアップに生成・格納する．

データ基盤，1/2,500 縮尺) [14] を用いた．

[Note] 全対最短経路データが既に得られている場合に本手法を[実行環境] SunOS 5.10 Generic 144500-19 32 sparcv9 プロセッ

適用する場合は，最短経路が領域分割線 l を交差する境界を求

サ (2530 MHz，浮動小数点プロセッサ付), 主記憶 32GB，Javaめる処理が必要になる．

version 1.5.0-20 である．
[評価方法]

4. 2 2 点間の最短経路の抽出手順
G 上の任意の 2 点 v s , vt が与えられた場合の経路索引を用い•た最短経路抽出手順は，次の通りである.

(1) 部分木の指定と最短経路索引の抽出

ダイクストラ法との比較によって評価を行う．

v s , vt 間に共通な領域を求め，最短経路索引を抽出する．

(1-1) v s , vt 間の共通部分木の指定 ノード ID が z 曲線コード

経路索引生成：提案手法では，原地図データを読み込み，全対最短経路索引を生成し，中間ファイルに出力するまでを測定した．

•

最短経路抽出：任意の (v s , vt ) を指定し，最短経路を返すで表現されていることを用い，v s , vt 間に共通な部分木のコードまでを測定した．ダイクストラ法は索引生成処理が必要ないたを v s , vt の ID から求める．

め，直接探査を行う．

[例 4] v s のノード ID が ”0000001”，vt のノード ID が ”0001000”であるとき，共通部分木のコードは ”000” である．

4. 3. 1 経路索引生成に関する評価
表 2 で経路索引生成時間とデータサイズを示している．生成(1-1) で求めた共通部分木内の最時間，データ量ともにノード数 N の増加にしたがって増加す

短経路索引集合から，v s , vt に対応する最短経路索引を抽出す

る．経路索引のデータサイズに関しては，原地図データサイズ

る．抽出された最短経路索引のノードを 2 つずつの組 (v′s , vt ) とより大きくなるが，完全な全対最短経路データサイズより小さし，各組に対して，(1-1) の処理を行う．

くなる．

(1-2) 最短経路索引の抽出(2) 最短経路ノード列の抽出

再帰的に二分木を辿り，v s , vt

4. 3. 2 最短経路抽出に関する評価間の最短経路ノード列を抽出する．(1) の処理を再帰的に行い，それぞれの地図データに対し，各ホップ数で到達可能な (v s , vt )組の 2 ノードが同一ノードとなったとき，そのノードを確定を 100 組用意し，提案手法とダイクストラ法で処理を行い，平ノードとし，最短経路ノード列に追加する．全てのノードが確均実行時間及び展開数を計測した．

よって境界ノード数が異なるため、境界ノード数が短い場合には NULL を用いる. ここでは, 最短経路索引の数だけテーブルを作成, テーブル名を最短経路索引とし, フィールド StartN,GoalNに索引を付与する. また, 最短経路問い合わせをする際, ノードID を z コードで表したものをを利用ため,StartN,GoalN,Egi では, ｚコードを用いる.
表3
図4

ホップ数に応じた最短経路抽出時間と展開数 (GSI1, N = 960)

Fig. 4 Extraction Time and Number of Expansions vs. Hops for (v s , vt )(GSI1,N = 960)

全対最短経路索引に対するスキーマ

Table 3 Relational Schema for Indices of All-pairs Shortest Paths
StartN

GoalN

00010001100

5841.48 000100

CostEg1

Eg2...

00010001101

5735.17 000100 01100011 ... NULL ... NULL

0110011

Egi

...

Eg14

... NULL ... NULL

[全対最短経路集合を直接格納するスキーマ] 表 4 は, ダイクス
トラ手法でもとめた全対経路集合をデータベースに格納する際に用いたスキーマを示す. フィールドは, 始点ノード (StartN), 終点ノード (GoalN), 距離 (Cost), ホップ数 (Rtm ) とし, 始点と終点ノードの組合せによって, ホップ数が異なるため, ホップ数が短い場合には NULL を用いる. ここでは, 一つのテーブル (allpairs)
図5ホップ数に応じた最短経路抽出時間と展開数 (GSI2, N = 5601)

Fig. 5 Extraction Time and Number of Expansions vs. Hops for (v s , vt )(GSI2,N = 5601)(1) 抽出及び探査時間に関する評価に全対経路集合を格納し, フィールド StartN,GoalN に索引を付与する. また, 全対経路集合は生成する際, 経路結果をノード IDで出力しているため,StartN,GoalN,Rtm では, ノード ID を用いる.
表 4 全対最短経路集合を直接格納するためのスキーマ

Table 4 Relational Schema for All-Pairs Shortest Paths

図 4，図 5 で，ホップ数ごとの各手法による最短経路探査及び抽出時間について示す．本手法ではホップ数に大きな影響をStartN

GoalN

Cost

Rt1

Rt2...

Rtm...

Rt300

受け，実行時間が長くなる傾向にある．それに対して, ダイク

347881 347899 5841.48 347881 347923..

347926 ... 347899

ストラ法による処理時間はホップ数の影響を受けるものの，軽347881 347918 5735.17 347881 347924..

NULL...

NULL

微なものとなっている.

(2) 展開数に関する評価
図 4，図 5 で，ホップ数ごとの各手法による展開数について示す．本手法では，v s から vt に対して最短経路上のノードのみを展開するため，ホップ数と展開数はほぼ同じ値となる．それ5. 2 最短経路問合せ[全対最短経路索引を用いた問合せ手順] G 上に任意の 2 点 v s , vtが与えられた場合の最短経路の問合せ手順を次に示す.

(1) 最短経路索引の抽出に対して，ダイクストラ法では，全方位に展開するため展開数

データベース内に v s , vt が格納されているテーブルを指定する

はホップ数に大きく依存し，ホップ数が増加すると，展開数もため,v s と vt の z コードを用いて，最短経路索引を求める．

大きく増加することがわかる．

5. データベースの利用(1-1) v s , vt を含む最短経路索引の指定とデータベース問合せ
ノード ID が z コードで表現されていることを利用して,v s , vt の最短経路索引を求める．求めた最短経路索引を用いて, データ4 章で生成した全対経路索引集合をデータベース (MySQL) 利用効果を確認する. ここでは JDBC を用いて接続する．

5. 1 ス キ ー マ

ベース内のテーブルを指定し, フィールド StartN と GoalN から

v s , vt に対応するフィールド全てを問合せる.
(1-2) v s , vt の最短経路を構成する境界列の再帰的抽出

ここでは全対最短経路索引を格納する場合と, 全対経路集合再帰的にデータベースに問合せることで, 任意の 2 点 v s , vt 最を格納する場合のスキーマを示す．ここでは全対最短経路索引

短経路を構成する境界列を抽出する. 抽出した最短経路索引のと全対経路集合を，データベースへ格納する前にあらかじめ最ノードを組 ([S tartN,Eg1 ],...,[Eg14 ,GoalN]) とし，各組に対して大境界数・経路長を調べ，それぞれ固定長のテーブルを作成しそれぞれ (1-1) の処理を行いデータを問合せる．ている.

(2) 最短経路ノード列の抽出[全対最短経路索引に対するスキーマ] 表 3 に提案手法で生成し組の 2 ノードが同一ノードとなったとき，そのノードを確定た全対経路索引をデータベースに格納する際に用いたスキーマノードとし，最短経路ノード列に追加する．全てのノードが確を示す. フィールドは, 始点ノード (StartN), 終点ノード (GoalN),定ノードとなったときに生成された最短経路ノード列が最短経距離 (Cost), 境界ノード (Egi ) とし, 始点と終点ノードの組合せに路を示す．

データベースに全対最短経路索引を格納する場合，最短経路問合せ処理を再帰的に行っているため，実行時間の増加の原因となっており，問合せ回数を抑える方法を検討する必要がある．
文

図6

ホップ数による問合せ回数, 問合せ実行時間 (GSI1,N = 960)

Fig. 6 Access Count and Query Time vs. Hops for (v s , vt ),(GSI1,N = 960)

図7

ホップ数による問合せ回数, 問合せ実行時間 ,(GSI2,N = 5601)

Fig. 7 Access Count and Query Time vs. Hops for (v s , vt ),(GSI2,N =5601)[全対最短経路を直接格納する場合の問合せ手順] 最短経路の問合せ手順を次に示す.

•allpairs テーブルを指定し, フィールド StartN,GoalN からv s , vt に対応する最短経路を問合せる.
5. 3 評価[対象データ] 4 章で生成した全対最短経路集合と全対経路集合をデータベース内に格納したものを利用.

[評価方法] それぞれの地図データに対し，各ホップ数で到達可能な組合せ (v s , vt ) を 100 組用意し, 問合わせ実行時間と問合せ回数を測定する.

[問合せ実行時間に関する評価]

図 6 に，960 ノードにおけるホップ数と問合せ回数, 問合せ実行時間の関係，図 7 に，5601
ノードにおけるホップ数と問合せ回数，問合せ実行時間を示す.
全対最短経路索引問合せでは，経路索引を用いて探査するため，ホップ数の増加と共に問合せ回数が増加し，問合せ実行時間も増加する．一方，全対最短経路を直接格納する場合の問合せでは，最短経路が格納されている部分を問合せればよく，アクセス数が一定となり, ホップ数による問合わせ実行時間のばらつきが少ない．

6. お わ り に
本稿では, 二分木を用いた全対最短経路の格納及び抽出方法について議論した. これは，探査処理の代替として問合せ処理により最短経路を抽出する方法である. 提案手法では経路索引生成時間が長く，大規模グラフに適用する場合には，生成時間を短縮する方法を検討する必要がある．また，最短経路抽出処理の実行時間のほとんどを索引ファイルの読み込み時間が占めているため，ファイル編成を再検討することが必要である．次に，

献[1] A. Moﬀat, T. Takaoka, An All Pairs Shortest Path Algorithm with Expected Time O(n2 log n), SIAM Journal on Computing, 16(6), 1023–1031 (1987)[2] A. Botea, D. Harabor, Path Planning with Compressed All-Pairs
Shortest Paths Data, Proceedings of the 23rd International Conference on Automated Planning and Scheduling(ICAPS 2013), pp.1–5,(2013)[3] G. J. Katz, J. T. Kider Jr, All-Pairs Shortest-Paths for Large
Graphs on the GPU, Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics Hardware(GH’08) pp.47–55 (2008)[4] T.Okuyama, F. Ino, K.Hagihara, A Task Parallel Algorithm for Finding All-Pairs Shortest Paths Using the GPU, International Journal ofHigh Performance Computing and Networking, Vol. 7, No. 2, pp.
87–98, (2012).
[5] GraphCREST(代表：藤澤克樹), 科学技術振興機構,
http://www.graphcrest.jp/jp/fujisawa-g.html[6] J. Sankaranarayanan, H. Alborzi, H. Samet, Eﬃcient Query Processing on Spatial Networks, Proceedings of the 13th ACM InternationalSymposium on Advances in Geographic Information Systems(ACMGIS2005), pp.200–209 (2005)[7] 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)[8] J. Sankaranarayanan, H. Samet, H. Alborzi, Path Oracles for Spatial
Networks, Proceedings of the 35th International Conference on Very
Large Data Bases(VLDB), pp.1210–1221 (2009)[9] J. Sankaranarayanan, H. Samet, Distance Oracles for Spatial Networks, Proceedings of the 25th IEEE International Conference on
Data Engineering (ICDE), pp.652–663 (2009)[10] L. Wu, X. Xiao, D. Deng, G. Cong, A. D. Zhu,. S Zhou, Shortest Pathand Distance Queries on Road Networks: An Experimental Evaluation, Proceedings of the 38th International Conference on Very Large
Data Bases(VLDB), pp.406–417 (2012)[11] H.Samet, Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann (2006).
[12] N.Jing, Y.-W.Huang, E.A.Rundensteiner, Hierarchical Encoded Path
Views for Path Query Processing: an Optimal Model and its Performance Evaluation, IEEE Transactions on Knowledge and Data Engineering,Vol.10,No.3, pp.409–32 (1998)[13] 蒲原智也，上島紳一, 道路網応用のための空間索引木の提案と最短経路探査への応用，情報処理学会論文誌データベース Vol.2,No.2, pp.10–28 (2009)[14] 国土地理院：数値地図 (空間データ基盤)，http://sdf.gsi.go.jp/