論文

Journal of the DBSJ Vol. 7, No. 1

ここではじめの二つの問題に本質的な違いはない．本研究で取有向グラフ上の最短経路問題に対 り扱うのは最後の問題であり，
1 質問あたり定数時間で答えを得る手法として，あらかじめすべての組み合わせに対して値を計算する効率的な索引付け

Scalable Indexing for Reachability Problem
on Directed Graphs

原口 新平∗

中村 有作†

Shinpei HARAGUCHI
Hiroshi SAKAMOTO

坂本 比呂志‡Yusaku NAKAMURA

して表の形式で保存しておくダイクストラ法を応用したものが提案されている [5]．
ところがこれらの手法は，ダイクストラ法を素朴に実行した場
合は O(n2 m) 時間かかり，巧妙なデータ構造で改善した場合でもO(n2 log n + nm) 時間かかる．また，表の形式で値を保存するため，領域は常に Ω(n2 ) である．ここで，n はグラフのノード数であり m は辺数を表す．本研究の手法では，要求された距離を定数時間で得ることをあきらめて，より大規模なグラフに対しても実行可能な距離計算のためのラベル付けを行う．

1.2 グラフのラベル付け
本研究では，有向グラフ上の任意の２ノード間の距離を高速に有向グラフ G が木構造であるとき，各ノードに対して前置順と計算できる規模耐性の高い索引構造を提案する．本研究で提案す 後置順による順位付けを考える．あるノード v の前置順および後る手法は，有向グラフ上の最短距離計算として，ノード間の距離 置順による順位をそれぞれ pre(v), post(v) とする．このとき，整計算の結果をあらかじめ隣接行列に格納しておく方法がある．し 数の組 (pre(v), post(v)) は，以下の性質を満たす．
かしながら，この方法では時間計算量と領域計算量の両方のコス
木の任意のノード u, v に対して，pre(u) < pre(v) かつトが高く，大規模なグラフ構造に適用する事は困難である．そこ post(u) > post(v) であるときまたそのときに限り u は v の先で本研究では，一般の有向グラフに適用可能な距離計算のための 祖である．また (pre(u), post(u)) は (pre(v), post(v)) を包含する
ラベル付けを提案し，その有効性を実験により検証する．特に， という．
XML データにおいて，前処理に必要な主記憶量，計算時間およこのような性質を満たすラベルを範囲ラベルと呼ぶ．この範囲
び索引サイズを示す．
ラベルを使う事で実辺上の先祖子孫関係かどうかを判定できるが，参照辺を介した先祖子孫関係については判定できない．
We propose an eﬃcient algorithm which reports the
一般には，有向グラフに対する無矛盾な範囲ラベルは存在しな
length of a shortest path between any two nodes of a いため，有向グラフの到達可能性の判定には別の手法が必要であdirected graph in constant time. In usual method, we る [13]．そこで，この範囲ラベルに加え，次のように 2Hop ラベ
can obtain the constant time response for any query ルをつける．2Hop ラベルとは一般の有向グラフに対する到達可in this problem by using an adjacent matrix for the 能性を判定する手法である．
graph. However, this method requires huge memory
有向グラフ G = (E, V ) の各ノード v ∈ V に対して，ラベルのspace and it is diﬃcult to apply it to lage database. So 集合 vin , vout ⊆ V を決めたとき，L(G) = {(uin , uout )|u ∈ V }we introduce more practical method for this problem を G の 2Hop ラベルという．このとき，任意の u, v ∈ V に対し
and evaluated the eﬃcency by experiments.
て，u から v へ到達可能 ⇔ uout ∩ vin ̸= ∅ であるなら，そのような L(G) を G の 2Hop カバーという．
以降では，2Hop カバーの条件を満たす L(G) のことを単に 2Hop
1. はじめに本研究では，有向グラフのラベル付けを応用した任意の 2 ノー ラベルと呼ぶことにする．各ノードがなるべく小さい数のラベルド間の最短距離を高速に計算する索引付けを提案する．XML デー を持つような，到達可能性を判定するための索引として都合がよ
タは，リンク構造をグラフの有向辺と見なすことで順序木や有向 い．しかし，与えられた有向グラフに対して，最小の 2Hop ラベ
グラフと同等である．そこで，半構造データ上の問い合わせ言語 ルを計算する問題は NP 困難である．
その他，効率的なグラフのラベル付け手法として，R2Hop[14]において，任意のノード間の先祖子孫関係を高速に判定する技術が知られており，本研究のDR2Hop はこの手法に基づいている．
が提案されている．本研究では，そのようなラベル付けを拡張し，
R2Hop
は，有向グラフG=(V, E) を強連結成分分解した非巡回
比較的大規模なデータに対して，ノード間の距離すなわち最短の′グラフ
Gに対し，深さ優先探索で全域木T を計算することで T
経路長を実用的な時間で計算できる手法を提案する．本研究では有向グラフ全体を対象としている．有向グラフ G に対するある全 に範囲ラベルを設定する．T に対しては通常の範囲ラベルが計算
域木 T を求めたとき，G ∩ T の辺を T によって定まる G の実辺， 可能であるが，それ以外のノードの到達可能性に対してのみ 2Hop
ラベルを計算することで，全体のラベルサイズを抑えている．
それ以外の G − T の辺を参照辺と定義する．

1.1 最短経路問題

1.3 提案手法

本研究では，有向グラフ上の全点対間最短経路問題にグラフのグラフにおける最短経路問題は，グラフ G が与えられたとき，ラベル付けのための手法を応用し，距離計算を高速かつ省スペー
ノード u, v の条件によって次のように分類される．
スで実現する索引付けを提案する．特に，疎なグラフに対しては
1. 単一始点最短経路：固定された v からの最短経路
ほぼグラフのサイズ (辺数) に比例する時間で索引付けを実行できる．本提案手法では，
O(n2 ) サイズの領域が必要ないため比較的
2. 単一点対間最短経路：固定された (u, v) 間の最短経路
大規模なグラフに対しても妥当な時間と領域で索引を構築可能で
3. 全点対間最短経路：すべての (u, v) 間の最短経路ある．
本研究で提案する手法は，範囲ラベルと 2Hop ラベルを組み合∗ 九州工業大学 大学院情報工学府
わせた R2Hop を応用した手法である．まず，与えられた有向グ
s haraguchi@donald.ai.kyutech.ac.jp
ラフ G に対して，深さ優先探索などの標準的な手法で G の全域† 日立製作所 ソフトウエア事業部
木を求めて，その全域木に対する範囲ラベルを計算する．このとyuusaku.nakamura@gmail.com
き，範囲ラベルとして木の深さも持たせることで，木の先祖子孫‡ 正会員 九州工業大学 大学院情報工学研究院
間の距離が計算できる．そして，範囲ラベルで判定できないが互hiroshi@ai.kyutech.ac.jp1

日本データベース学会論文誌 Vol 7, No.1

論文

Journal of the DBSJ Vol. 7, No. 1

1

×

1

アルゴリズム DRVOU T (G)2

入力：連結な有向グラフ G = (V, E) とその全域木 T
出力：任意の v ∈ V に対するラベル vout

(1) T を v から深さ優先探索する(1-1) v が被参照ノードならば先祖へ幅優先探索:
u をカレントノード,i を v から u までの幅優先探索による距離とし,
u が以下の (a),(b),(c) すべてを満たすならば
uout ← uout + {(v : i)} とする(a) v ̸∈ uout(b) v の先祖かつ，u から v の実辺距離が k > i(c) u ̸= v
(1-2) v からの深さ優先探索に戻る(2) vout を出力

6

×

3

9

step5
vout{(4,4)}

6 vout{(4,2)}

9
step4

4

7

8

10

7

vout{(4,1)}

5

8

10

vout{(4,2)} vout{(4,3)}

vout{(4,1)}

11

step1

11
vout{(4,2)}

1

1

6 vout{(4,2)}

7

9

8

10

vout{(4,2)}vout{(4,1)}

6 vout{(4,2)}

2

3

9

×

4

7

5

vout{(4,2)}vout{(4,3)}

11

step3

vout{(4,2)}

10

8vout{(4,1)}

11

step2

×

vout{(4,2)}

図 2. DRVOU T (G) の動作例

Fig. 2. An example run of DRVOU T

図 1. vout 構築アルゴリズム

Fig. 1. Algorithm for vout

2.2 最短距離計算方法

次に，距離計算についての説明とその計算アルゴリズムを提案
いに到達可能な関係にあるノードに対して 2Hop ラベルを計算し， する．任意のノード v ，u が実辺上で先祖子孫関係の場合，このそのラベルにも距離を持たせる．ただし，到達可能性の判定では， 実辺パスの距離を計算は，それぞれの木における深さを用いる．
ある二つのノードが共通のラベルを持つだけでそれが判定できた そして，この 2 つの深さの差をそのまま距離とみなせる．任意ののに対して，最短経路問題では，ノードラベルとして常に最短の ノード v ，u が参照辺を通り到達可能な場合は，距離情報付きの距離を与えるものを保証しなければならない．そこで，ダイクス 2Hop ラベルで距離計算を行う．(w : i) ∈ v ∩ u
inout の場合，こトラ法を部分的に適用することでこの問題を解決する．本研究の れは u から距離 i 先にある w を経由して v に到達可能であるこ索引付けは，大規模な表を必要としないため，実データにおいて とを示している．
は主記憶量，前処理時間および判定時間に対する効率がよいこと
1. u から w までの最短距離が i であることは，vout アルゴリが実験によって示される．
ズムで保証されている．

2. 提案手法による効率的な距離計算
2.1 DR2Hop のラベル構築アルゴリズム
本研究で提案する最短距離計算は，グラフの全域木 T の各ノード v に深さ情報を持たせる事と vout 内の各ラベル u に v から u ま
での距離 i を付加させる事により実現される．この最短距離計算に必要な vout のラベル構築アルゴリズムと最短距離の計算アルゴ
リズムを示す．なお，距離計算に必要なもう一方のラベル vin の構築は，[14] で提案された手法をそのまま用いる．すなわち，あるノード v のラベル vin とは，全域木における v の先祖である被参照ノード全体の集合である．
図 1 に vout 構築アルゴリズム，図 2 にその動作例を示す．本
手法で構築する vout のラベルの集合は，v の子孫の全ての被参照
ノード (実辺パスのみで辿れる，かつ，実辺パスの方が距離が短い
ノードは除く) の集合である事を意味している．本手法では，グラフ内の各被参照ノードを始点に幅優先探索によりラベルと距離を付けしているので，ラベル内の距離情報は最短距離であることを保証する．n はノード数，ℓ は被参照ノードの数，m は辺の数とした時，本手法では，1 ノードあたりの vout の最大ラベル数はℓ であり，ラベル付けは各被参照ノードごとにグラフの辺を巡回しながら追加していくので，vout 構築にかかる時間計算量と領域
計算量はそれぞれ O(ℓm) と O(ℓn) である．

2. vin は，v の先祖でかつ被参照ノードの集合であるので，wと v は全域木における先祖子孫関係があり，その距離は深さの差で計算できる．
よって，u から v までの距離は，上記いずれかの小さい方の値として計算可能である．深さの差と距離情報付き 2Hop ラベルでの距離計算の例を図 3 で示す．

深さ：0
深さ：1
深さ：2

1
9

2
3

4

10

深さ：3 5 6
深さ：4
7
深さ：5
8
「2から8までの距離：5-1=4」

深さ：0
深さ：1
深さ：2

1
9

2
3

4

10

vout{(6,2)}

vout{(6,1)}

深さ：3 5 6 v {(6)}深さ：4
7 v {(6)}深さ：5
8 v {(6)}「9から8までの距離：2+(5-3)=4」
in

in

in

図 3. 2 ノード間の距離計算

Fig. 3. A computation of the distance of two nodes2

日本データベース学会論文誌 Vol 7, No.1

論文

Journal of the DBSJ Vol. 7, No. 1

vout｛t2|dt2，
t3|dt3｝～

実辺のみ

表 1. データの概略と各手法のノードサイズ比較
Table. 1. Outline of data and comparison of node size
サイズ

ノード数

t3

～

～

t2

v

503

被参照

ラベル数

ラベル数

[15]

4.87

469

267

[14]

(3.6%)

R2Hop

1.68
20.81

116
–

提案手法

20.81

263

525

[15]
[14]

4.78
1.65

723
217

(3.5%)

R2Hop

44.05
44.05

521
521

[15]

4.57

1811

1546

[14]

(3.5%)

R2Hop

1.67
148.68

699
–

提案手法

148.68

1543

提案手法

3044

44170

2.3 最短距離の保証
ノード v の持つ vin 内のラベル u は，v と u が実辺のみで接続されていることを意味するので，v − u 間の実辺経路の距離は全域木の深さで計算できる．そして，vout 内のラベル u′ と対になっている距離の値は，アルゴリズム DRVOU T (G) の幅優先探索に
より，v − u′ 間の最短距離を保証している．ノード v の持つ voutは，v から参照辺を介し到達可能な被参照ノードのラベルをすべてを持っている (ただし，実辺のみでも到達可能でかつ，実辺のみの経路の距離が短い場合は除く)．これらの事実から，本手法による計算が最短距離を計算することを示す．
ノード v, u の最短距離を以上の手法で計算したとき，この距離が最短でないと仮定する．最短でない場合とは，求めた経路 p よりも短い経路 q でたどり着けることである．この時，q が実辺のみの経路でない事はあきらかであるので，q は参照辺を少なくともひとつは通る経路である．参照辺を通る経路は必ず被参照ノー
ド x を経由するので，v の vout には x が含まれる．しかし，参照
辺を通る経路の距離は幅優先探索による計算ですでに得られており，その最小値と全域木における経路の距離の比較がすでに行われているので，x を経由した経路 q が最短距離になるという事はありえない．したがって，求めた p の距離が 2 点間の最短距離である．図 4 にこの証明の概略を示す．

最大

14974

図 4. 最短経路の保証：実辺だけを辿る経路と参照
辺を辿る経路のそれぞれの最小値を求めることが可能であるので，全体として最短の経路を計算できる

Fig. 4. The guarantee of the shortest path

平均

7526

vin｛t2，t3｝

1026

手法

ノード数

(KB)

～

t1

～
～

u

～

参照辺
＋
辺
実

前処理時間の比較
100000
]
秒
リ
ミ
[

HOPI
(scc)R2Hop
R2Hop
DR2Hop

10000
1000
100

20686

1618
719
446

331

437 596

503KB

2441

31370
16643

3056

543

1026KB

3044KB

図 5. 100 万回の判定の実行時間

Fig. 5. Computation time for 1M queries

かし XML データをそのまま表現したグラフに対しての R2Hopと比べると，ラベル数は変わらないにも関わらず最短距離計算の本研究で提案する手法の有効性を実験によって確認する．使用 機能を追加できている．この要因のひとつとして，XMark におい
したデータは，XMark [16] によって生成した 3 つの XML データ ては，あるノード x からあるノード y へと参照辺を通過して到達(503KB,1026KB,3044KB) である．実験環境は，Celeron 3.2GHz， する経路があったとき，x が y の実祖先である可能性が極めて低992MB メモリ上の WindowsXP であり，参照辺を含む XML の いことが挙げられる．オーダ表記では差が見えなくとも，平均ラDOM 木を C++による双方向リストで実装した．実験は，本手 ベル数・最大ラベル数は判定時間と強い相関関係があるので，実法における前処理時間および最短距離を判定する時間を測定した． 際のラベル数の差が判定時間の差となると考えられ，後で示す測また，HOPI [15]，強連結成分分解によって巡回を無くしたグラフ 定結果からもそれが正しいことが分かる．巡回を含むグラフに対に対する R2Hop ラベル付け手法 [14]（以下 (scc)R2Hop），巡回 する R2Hop と提案手法のラベル数の増加が大きいのは，データを含んだまま R2Hop ラベル付けする手法の 3 手法を実装し，前 サイズの増加に伴って大きくなる巡回経路上のノードがすべて等
処理時間や平均ラベル数などの比較を行った．ただし，この 3 手 しく vout のラベルを持つためである．
法は到達可能性を判定できる距離計算はできない．
最後に，提案手法と他 3 手法における前処理時間と，判定時間
表 1 に，使用した XML データの基本的な情報と，提案手法で の比較結果を示す．図 5 は，ランダムに生成した 100 万組のノー得られた 2Hop ラベルのサイズを他の 3 手法のものと比較した結 ドに対する到達可能性判定 (提案手法については最短経路判定) 時
果を示す．ノード数とは XMark を巡回グラフで表したときのノー 間を測定した結果である．ラベル数に違いがないが，実行時間でド数を表す．XMark では，全体のノードのおよそ 3.5%が被参照 提案手法の方が R2Hop よりもわずかに時間が掛かっているのは，ノード (すなわち 2 つ以上の親を持つノード) である．
R2Hop が 2 ノード間に到達可能な経路を発見した時点で処理を平均ラベル数は 1 ノードあたりの 2Hop ラベルの個数を表す． 終えて良いのに対し、提案手法は最も距離数の少ない経路を探す
提案手法は HOPI と (scc)R2Hop にはラベル数で劣っている．し ために最後のラベルまで追っているためと考えられる．

3. 実験

3

日本データベース学会論文誌 Vol 7, No.1

論文

Journal of the DBSJ Vol. 7, No. 1

100万回の判定の実行時間
100.0057.13

HOPI(scc)R2Hop
R2Hop
DR2Hop

]
10.00
秒
[

5.49

1.36

1.36

11.39

67.42

15.27

6.30

1.41

1.51

1.40

1.61

1.00
503KB

1026KB

3044KB

図 6. 前処理時間の比較

Fig. 6. Comparison of preprocessing time[8] 江田毅晴, 天笠俊之, 吉川正俊, 植村俊亮, XML 木のための更新に強い節点ラベル付け手法, DBSJ Letters, Vol. 1, No.
1, pp. 35-38, 2002.
[9] R. Goldman, J. Widom, DataGuides: Enable Query Formulation and Optimization in Semistructured DataBases,
In VLDB 1997, pp. 436-445, 1997.
[10] T. J. Green, A. Gupta, G. Miklau, M. Onizuka, D. Suciu,
Processing XML Streams with Deterministic Automata
and Stream Indexes, ACM TODS, vol. 29, no. 4, 2004.
[11] D. B. Johnson, Eﬃcient algorithms for shortest paths insparse networks, Journal of the ACM, vol. 24, no. 1, pp.113, 1977.
[12] T. Milo, D. Suciu, Index structures for path expressions,
In ICDT 1999, pp. 277-295, 1999.
[13] 中村有作, 舞田哲哉, 坂本 比呂志, 参照構造を持つ XML 上の
高速な到達可能性判定, 人工知能学会論文誌, Vol. 22, No.2,
pp. 191-199, 2007.

図 6 は提案手法と他 3 手法の前処理時間の比較結果である．提案手法の前処理時間は，503KB および 1026KB のとき R2Hop の[14] 中村有作, 舞田哲哉, 坂本 比呂志, 高速な到達可能性判定の2 倍以内，3MB のとき HOPI および R2Hop の時間の 2 倍以内にための規模耐性の高い索引付け, DBSJ Letters, Vol. 6, No.
収まっている．この結果より，本研究で提案する R2Hop に距離1, pp. 77-80, 2007.
情報を持たせたラベル付け手法は，2 点間の最短距離を計算できない従来の手法に比べて妥当な速度で構築することが結論できる． [15] R. Schenkel, A. Theobald,G. Weikum, Creation and Incremental Maintenance of the HOPI Index for Complex
XML Document Collections, In ICDE 2005, pp. 360-371,
4. おわりに2005
本研究では，比較的大規模で疎なグラフ構造を持つ XML デー
タに対して，前処理によって 2 点間の最短距離を計算するアル [16] A. Schmidt, F. Waas, M. Kersten, M. Carey, I. Manolescu,
R. Busse, Xmark: A benchmark for XML data manageゴリズムを提案した．実験では，HOPI と本手法の基礎となる
ment, In VLDB 2002, pp. 974-985, 2002.
(scc)R2Hop と巡回を含むグラフへの R2Hop とを比較した．本手法では，強連結成分分解をしない場合，ラベル数や判定時間が増 [17] T. Schwentick, XPath Query Containment, SIGMOD
加したが，妥当な計算時間で最短距離に対するラベル付けが可能
Record, Vol. 33, No. 1, pp. 101-109, 2004.
であることが確認された．今後は，本手法を応用したパターン発[18] 鳥井修, 白井智, 金井達徳, 非巡回グラフのための拡張レンジ
見等の枠組みを提案することが課題である．
ラベリング手法, DBSJ Letters, Vol.5, No.1, pp. 157-160,
2006.

［謝辞］

本研究の一部は，平成 19 年度科学研究費補助金 (基盤研究 (A)
課題番号 17200011 課題名” 大規模半構造データからの高速知識
発見システムの開発”) の支援を受けて行われた．

［文献］[1] S. Abiteboul, P. Buneman, D. Suciu, Data on the Web,
Morgan Kaufmann, 2000.
[2] S. Abiteboul, H. Kaplan, T. Milo, Compact labelingschemes for ancestor queries, In SODA 2001, pp. 547-556,
2001.
[3] R. Agrawal, A. Borgida, H.V. Jagadish, Eﬃcient Management of Transitive Relationships in Large Data andKnowledge Bases, In SIGMOD 1989, pp. 253-262, 1989.
[4] L. Chen, A. Gupta, M. E. Kurul, Eﬃcient Algorithms for
Pattern Matching on Directed Acyclic Graphs, In ICDE
2005, pp. 384-385, 2005.
[5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction
to Algorithms, MIT Press, 1990.
[6] E. Cohen, E. Halperin, H. Kaplan, U. Zwick Reachability
and Distance Queries via 2-Hop Labels, In SODA 2002,
pp. 937-946, 2002.

[19] Y. Wu, J. M. Patel, H. V. Jagadish, Structural Join Order
Selection for XML Query Optimization, In ICDE 2003,
pp. 443-454, 2003.

原口 新平

Shinpei HARAGUCHI2007 年九州工業大学情報工学部知能情報工学科卒業．現在，同大
学院情報工学府知能情報工学研究系に在学．高速な XML データ
ベース，大規模な半構造データの索引付けに関する研究に従事．

中村 有作

Yusaku NAKAMURA

2006 年九州工業大学情報工学部知能情報工学科卒業．2008 年同
大学院情報工学府知能情報工学研究系修了．現在，(株) 日立製作所に勤務．

坂本 比呂志Hiroshi SAKAMOTO

九州工業大学情報工学部准教授．1998 年九州大学大学院システム
情報科学研究科情報理学専攻博士後期課程修了 (日本学術振興会
特別研究員)．博士 (理学)．1999 年から 2003 年 7 月まで九州大学大学院システム情報科学研究科助手．機械学習，半構造データからの知識獲得および半構造データに対する索引付けに関する研究に従事．2006 年度人工知能学会論文賞などを受賞．電子情報通信学会，人工知能学会，情報処理学会，日本データベース学会各
会員．

[7] E. Cohen, H. Kaplan, T. Milo, Labeling Dynamic XML
Trees, In PODS 2002, pp. 271-281, 2002.

4

日本データベース学会論文誌 Vol 7, No.1