DEIM Forum 2016 D5-4

木構造データに対する類似部分木検索の並列化
小柳

涼介†

天笠

俊之††

北川 博之††† 筑波大学システム情報工学研究科コンピュータサイエンス専攻 〒 305–8573 茨城県つくば市天王台 1 丁目 1-1†† 筑波大学システム情報系情報工学域 〒 305–8573 茨城県つくば市天王台 1 丁目 1-1
E-mail: †rkoya@kde.cs.tsukuba.ac.jp, ††amagasa@cs.tsukuba.ac.jp, †††kitagawa@cs.tsukuba.co.jp
あらまし

木構造データに対する類似部分木検索問題として，与えられたクエリ木との木編集距離が T 以下であるという条件を満たすデータベース木の部分木を列挙する問題を考える．類似部分木検索問題は，XML を始めとする半構造データに対する類似検索の一手法として重要な問題である．近年に見られるビッグデータ化の傾向とともに，XML を始めとする木構造データのデータサイズも拡大の一途を辿っており，木編集距離に基づく類似部分木検索問
題は多くの先行研究により高速化手法が考案されている．先行研究はどれも枝刈りをベースとした高速化であったが，本研究では既存の手法を効率的に並列処理化する手法を提案する．本手法は，(1) 与えられたデータベース木を効率良く複数ノードに割り当てるための分割方法と，(2) 複数ノード間にまたがる部分木への計算方法の二部から構成される．(1) ではノードをまたぐネットワークの通信量とノード間の計算対象の偏りを考慮した一般的な分割方法を考える．(2) では適切に木を順序付けることにより，ノード間の依存関係と処理順序から発生するオーバヘッドを抑える
方法について考える．最後に，実験によって並列化効率を評価し，本手法が充分なスケーラビリティと拡張性を持つことを確認する．
キーワード

XML 類似度, 木編集距離, 類似検索, 並列処理

1. は じ め にいる．

Structure Search では，データベース木が持つ部分木全ての近年，木構造データは XML や JSON を始めとして，Web構造を調べ，予め同一の構造を持つ部分木を特定し，インデッにおいて広く使われている．また，それら木構造データの広がクス付けしておくことでクエリ処理時に計算の再利用を行うこりに伴い，効率よい処理方法に関する需要も高まっている．中とで，さらなる高速化を実現した．

でも，木構造データに対する類似検索は，単純なデータ検索に我々の先行研究である [11] では，類似尺度として木編集距離加え重複検出，コピー検出，データの統合など様々な目的に応とテキストの類似度の 2 種類の尺度を採用し，それらの比重を用できる重要な問題である [1]．

考慮した類似度モデルについて提案した．また，テキスト類似

木構造データに対する類似検索において，二つの木の類似度度の計算にかかるコストが木編集距離計算に比べ軽いことを利を表す尺度は既存の多くの研究により様々なものが提案されて用し，テキスト類似度による枝刈りを取り入れることで高速化きた．その中の一つに木編集距離 [2] がある．木編集距離は，を成し遂げた．

二つの木を同型にするために必要な操作（頂点の挿入・削除・

同じく我々の先行研究である [12] では，[11] において構造類

値の変更）のコストの和として定義される．適用することがで似度の比重が大きい場合にテキスト類似度による枝刈りが適用きる操作の種類によって様々なバリエーションが存在し，求めできず，効率が落ちてしまう問題に対し，構造の局所性を用いるためにかかる計算量も多様である [3–8]．

て情報の再利用を行うことで木編集距離計算回数を削減し，高木構造データの類似検索に関する問題の中でも特に，与えら速化を成し遂げた．

れた木構造データ（クエリ木）に対して，予め用意しておいた木本研究では，並列処理環境下での類似部分木検索について考

構造データ（データベース木）に含まれるすべての類似した部

える．また，本研究における類似部分木検索とは，クエリ木と分木を列挙することを類似部分木検索と呼ぶ．類似部分木検索の木編集距離が θ 以下であるようなデータベース部分木を全て問題を対象とした研究として Augsten らの提案する TASM [9]列挙する問題と定義する．計算効率のためにノード間通信の量や Cohen らの提案する Structure Search [10] や我々の先行研とノード間の木編集距離計算量のバランスの二種類をコストと究である [11, 12] がある．[9, 10] はどちらも類似度として木編して考慮し，これらを環境に応じてどちらをより抑えるべきか

集距離を使用しており，計算手法に木編集距離の計算回数を低を決定できるような類似部分木検索手法を提案する．そして最減する工夫を取り入れることで高速化を達成している．

後に，実際に手法の実装を行い，巨大な XML ファイルに対し

TASM では，Top-k 類似部分木検索（類似部分木の上位 kて本手法を適用し並列化の性能を確認する．

個を列挙）を対象とし，クエリ木の頂点数に基づき探索対象の本論文の構成は以下のとおりである．第 2. 節で本研究の前提

部分木の頂点数に上限を設けることで処理の効率化を実現して知識となる諸定義について述べる．第 3. 節で本研究の提案手法

について述べる．本手法における前提知識である木編集距離計

次に，二つのラベル l1 , l2 ∈ (Σϵ = Σ ∪ {ϵ}) についてそのコ

算と， TASM を基にしたシングルプロセスアルゴリズムを説

スト関数を γ(l1 , l2 ) と定義する．3 つの操作はこのコスト関明し，次いでデータベース木の分割について論じる．その後，数に紐付けられる．delete(v, l1 ) のコストは γ(l1 , ϵ) で表され，それらに基づくマルチプロセスアルゴリズムについて説明する．

insert(v, l2 ) のコストは γ(ϵ, l2 ) で表され，rename(v, l1 , l2 )第 4. 節では評価実験について述べ，本手法の効率性の確認をのコストは γ(l1 , l2 ) で表される．

行う．最後に，第 5. 節で本稿のまとめと今後の課題を述べる．

2. 諸 定 義

コスト関数 γ は以下の性質を満たす距離関数でなくてはならない:•

γ(l1 , l2 ) >= 0 with equality if l1 = l2 ,2. 1 デ ー タ 木•

本研究ではデータベース木を，頂点が値を持つ根付き順序•γ(l1 , l2 ) = γ(l2 , l1 )γ(l1 , l3 ) <= γ(l1 , l2 ) + γ(l2 , l3 ).

木 D = (V (D), E(D), L(D), λ, r) として扱う．V (D), E(D),A

L(D) は，それぞれ木に含まれる頂点，辺，値の集合である．
3

λ : V (D) → L(D) は各頂点とラベルの対応を表す．任意のB

アルファベット列から成るラベル集合を Σ とした時，全てのl ∈ L(D) は l ∈ Σ を満たす．また，r ∈ V (D) を 木 D の根にあたる頂点とする．
木 D に関して，D に含まれる頂点数を |D| で表す．また，

D

X

B

E
1

D

F

木 D に含まれる頂点 V (D) には後行順に基づく全順序を定義する．後行順において i 番目に出現する頂点を di とし，頂点

3

C

F

G
2

(a)

di の親に当たる頂点の後行順番号を par(di )，頂点 di を根とC(b)

図 1: 木編集距離の計算例

する部分木を Di とする．部分木 Di に含まれる頂点において
後行順番号が最も小さい頂点の後行順番号を l(di ) と定義する．
任意の部分木において |Di | = i − l(di ) + 1 が成り立ち，またdi が葉である時 i = l(di ) が成り立つ．また，この定義において 部分木 Di について V (Di ) = {dj | l(di ) <=j<= i} が成り立
つ．すなわち，任意の部分木は後行順において連続する頂点集合から構成される．
最後に，クエリ木 を Q とし，D と同様に各種記号を定義
する．

2. 2 木編集距離
二つの木 D, Q について，木編集距離とは，二つの木を同型にするために必要な操作のコストの総和の最小値で定義される．
本研究では，「頂点の削除」，「頂点の挿入」，「頂点の値の変更」の 3 つの基本的操作を許可する．

delete(v, l1 ) は 木 D から λ(v) = l1 である頂点 v の削除を表す. この時，v が親頂点を持っていた場合， v の全ての子はその親頂点の子となる．そうでない場合，つまり v が根にあたる
場合， v の全ての子はそれぞれが非連結になり、 木 D は森となる．なお，この森についても各頂点の順序は分割される前の順序が保たれる．insert(v, l1 ) は 木 D への λ(v) = l1 である
頂点 v の挿入を表す. 削除時と対照をなすように，insert(v, l1 )にも 2 つの場合が存在する．v が 頂点 u の子として挿入される場合，u の子となる順序付き頂点集合について，いずれかの連続する部分頂点列（空にもなり得る）は v の子として移動

例として図 1 の木 (a), 木 (b) 間の木編集距離を考える．また，木への操作として頂点の追加，頂点の削除，頂点の値の変更の 3 種類の操作に対し，それぞれ 1 のコストとする．木 (a)を 木 (b) に変形させるためには（ 1 ） 頂点 E を削除（ 2 ） 頂点 G を追加（ 3 ） 頂点 A を頂点 X に改名の 3 つの操作が必要となる．これらの操作のコストは 3 であり，コストが 3 未満になるような操作は存在しないため，木 (a), 木(b) 間の木編集距離は 3 となる．
木編集距離の計算手法については様々な研究が存在するが，Zhang らの提案している手法 [4] は動的計画法を用いて 時間
計算量 O(n2 m2 ) ，空間計算量 O(nm) （ここでそれぞれ n, mは比較対象となるそれぞれの木の頂点数）を達成している．本
研究と同じく木編集距離に基づく類似部分木検索を対象としている TASM, StructureSearch もこの手法により木編集距離計
算を行っている．

[4] に基づく木編集距離計算アルゴリズムを Algorithm1 に示す．このアルゴリズムはデータベース部分木 DI とクエリ部
分木 QJ が与えられた時に，それぞれの部分木に含まれる兄を持たない頂点同士の木編集距離を計算する．なお，このアルゴリズムが実行される際には，それぞれの部分木に含まれる兄を持つ頂点同士の木編集距離は既に求まっている必要がある．

される．そうでない場合，つまり v が新しく根として挿入される場合， 森（木） D に含まれる任意の連続する根頂点が vの子として移動される．rename(v, l1 , l2 ) は 木 D に含まれる

λ(v) = l1 である頂点に対する， λ(v) = l2 となるよう値の書
き換えを表す. 以上の全ての操作において，操作の前後で任意の頂点間の順序が前後することはない．

3. 提 案 手 法
3. 1 シングルプロセスアルゴリズム
シングルプロセスでの類似部分木検索アルゴリズムを Algo-rithm 2 に示す．図 2 のデータベース木と図 3 のクエリ木にAlgorithm 1 T EDCalculation
Require: DI , QJ , {di .T ED[j]

|

21 e

lef t(di )=|lef t(dI ) and

lef t(qj ) =| lef t(qJ )}Ensure: {di .T ED[j] | lef t(di ) = lef t(dI ) and lef t(qj ) =lef t(qJ )}1: F orestDist[lef t(dI ) − 1][lef t(qJ ) − 1] = 0
2: for i : lef t(dI ) to I do
3:

2

c

1

b

0

a

8

3

5

b

a

4

a

c

20 d

7

b

6

a

15 c
13 b

11 b

19 c
14 b

17 b

18 b

F orestDist[i][lef t(qJ ) − 1] = F orestDist[i − 1][lef t(qJ ) −91] + γ(di , ∧)4: end for

a

12 a

10 a

16 a

図 2: データベース木 D の一例

5: for j : lef t(qJ ) to J do
6:

F orestDist[lef t(dI ) − 1][j] = F orestDist[lef t(dI ) − 1][j −51] + γ(∧, qj )7: end for

2

b

a

1

c
4

b

3

d

8: for i : lef t(dI ) to I do
9:
10:
11:

for j : lef t(qJ ) to J do0

if lef t(di ) = lef t(dI ) and lef t(qj ) = lef t(qJ ) thena

図 3: クエリ木 Q の一例

di .T ED[j] = F orestDist[i][j] = min(F orestDist[i − 1][j] + γ(di , ∧),F orestDist[i][j − 1] + γ(∧, qj ),Algorithm 2 SubtreeM atchingSingleP rocess

F orestDist[i − 1][j − 1] + γ(di , qj )Require: D, Q, θ
Ensure: Result = {i | T ED(Di , Q) <
= θ}

)
12:
13:

1: max|D| = |Q| + θelse
F orestDist[i][j] = min(2: for di : D by post-order do

if |Di | > max|D| thenF orestDist[i − 1][j] + γ(di , ∧),3:

F orestDist[i][j − 1] + γ(∧, qj ),4:

F orestDist[lef t(di ) − 1][lef t(qj ) − 1] + di .T ED[j]5:

end if)6:p = par(di )14:

end if7:

if di は兄を持つ or di は根 or |Dp | > max|D| then15:

end for8:

16: end forgoto NEXTFOR

for j : 0 to |Q| − 1 do
if qj は兄を持つ or qj は根 then9:

T EDCalulation(Di , Qj )10:

end if11:

対して θ = 3 でこのアルゴリズムを適用した場合について考12:える．なお，図における各頂点の左の数字は後行順番号を表13:

end if

し，右の文字は値を表す．1 行目の max|D| は計算対象となる

14:

if di は根 or |Dp | > max|D| then

部分木のサイズの上限を表す．例では，|Q| = 6, θ = 3 のため，

15:

max|D| = 9 となる．D20 , D21 は頂点数が max|D| を超える

16:

for k : lef t(di ) to i do
if dk .T ED[|Q| − 1] <= θ then

ため，無視される（4 行目）．また，ある部分木とクエリとの17:

木編集距離を全て埋める為には，その部分木に含まれる全てのend foradd k to Result18:

end if

19:

end for

兄を持つ頂点と根に対して子から順に Algorithm 1 による木

20:

編集距離計算アルゴリズムを適用する必要がある（7-13 行目）．

21:

end if

今見ている頂点の親を根とする部分木の頂点数が max|D| を超22:

NEXTFOR:

えている場合，その頂点を根とする部分木が計算対象となる極

23: end for

大な部分木となる．よって，そのような頂点を根とする部分木

24: return Result// we can release buﬀer

に対しクエリ木との木編集距離を列挙し， θ 以下のものを検索結果として格納する（14-21 行）．

TASM [9] でも触れられているように，極大部分木を処理した後はそれらの頂点情報は必要なくなるため，20 行目時点で過去の頂点情報を全て破棄することができる．これにより，空間計算量は O((|Q| + θ)|Q|) に抑えることができる．

時にいくつかの連続する部分列になるようデータベース木を分割する．表 1 に，図 2 のデータベース木を先行順に並べた列を示す．
図 4，図 5 に 3 個のプロセスに割り当てるための 2 種類の分割例を示す．分割例 1 は先行順番号 [0, 9], [10, 17], [18, 21] で分

3. 2 データベース木の分割

割されている．分割例 2 は先行順番号 [0, 6], [7, 13], [14, 21] でデータベース木を分割し，複数のプロセスに木編集距離計算

分割されている．各図において，青い点線で示される辺は異なを割り当てることを考える．本手法では，木を先行順に並べたるプロセス間での頂点情報の通信が発生する可能性があることを示す．分割例 1 において，D20 が計算対象部分木である場合，

Algorithm 3 DivideT ree

D20 の木編集距離の計算に D16 ...D19 の頂点情報（lef t(di ),Require: D, t, k

値，木編集距離）が必要となるため，プロセス 3 からプロセス

Ensure: Assign[|D|]2 へ頂点情報および計算結果を送信しなければならない．この1: l ⇐ 1, r ⇐ |D|

ような通信が発生する条件は， プロセスをまたぐ辺の親側の頂

2: while do

点を根とする部分木の頂点数（境界頂点数とする）が max|D|3:x ⇐ (l + r)/2

4:

j⇐1

5:

for di : D by preorder doを超えているかどうかで決まる．各プロセスにおける境界頂点数は，そのプロセスに与えられている先行順頂点列の先頭の頂

6:

Assign[i] = j

点の親部分木の頂点数となる．分割例 1 において，プロセス 3

7:

if j < k and di+1 で分割可能 andの境界頂点数，すなわちプロセス 3 からプロセス 2 への通信が起こる max|D| の下限は，先行順番号 18 である頂点の親である頂点を根とする部分木の頂点数 |D20 | = 12 となる．
分割例 1 は max|D| が 12 未満の場合に通信が発生しないが，分割例 2 は 3 以上の場合に通信が発生してしまう．しかし，各プロセスに割り当てられる頂点数は分割例 1 よりも分割例 2 のプロセス j の頂点数が x 以上 thenj ⇐j+18:
9:

end if

10:

end for11:

if l = x then12:

goto BREAKWHILE

13:

end if方が均等に割り振られており，木編集距離計算回数の偏りは少14:

if j = k then

ないと考えられる．一般に，プロセス間通信のコストが大きい

15:場合は分割例 1 のように境界頂点数が大きい方が効率がよく，

16:

プロセス間通信のコストが小さい場合は分割例 2 のように割り17:当てられる頂点数が均等である方が効率が良いと考えられる．

18:l ⇐ midelser ⇐ mid
end if

19: end while
20: BREAKWHILE:

表 1: 図 2 の木を先行順に並べた時の頂点列
先行順

0

1

2

3

4

5

6

7

8

9 10

後行順

21

2

1

0

8

5

3

4

7

6 20

先行順

11 12 13 14 15 16 17 18 19 20 21

後行順

15 11

21: return Assign

本手法では，プロセス数 k と各プロセスの境界頂点数の下限

t をユーザが指定し，その条件下で各プロセスに割り当てられ9 10 13 12 14 19 17 16 18る頂点数の最大値を最小化するような分割を行う．Algorithm

3 に分割アルゴリズムを示す．なお，このアルゴリズムにおい
21 e

2

8

c

1

b

0

a

3

5

b

a

4

a

てのみ di は 木 D の先行順番号が i である頂点を示す．

22頂点

c

このアルゴリズムでは，頂点数の最大値を二分探索すること
20 d

7

b

6

a

15 c
13 b

11 b

で，
「木 D を，与えられた条件下で， x 頂点以上の k 個の連続

12頂点部分列に分解できるか」という問題に帰着する．この問題は，

19 c
14 b

先頭から順に見ていき，切ることができる部分が来た時に，現

17 b

18 b

在の頂点数が x 以上であるならば貪欲に切る，という方法を取り，実際に k 個に切り分けられたかどうかで判定することがで

10頂点

9

a

10 a

12 a

16 a

8頂点

きる．また，ここでの di と di+1 の間で切ることができるため

4頂点

図 4: データベース木の分割例 1の条件とは「di が葉である」かつ「di+1 の親部分木の頂点数がt より大きい」である．
3. 3 マルチプロセスアルゴリズム
マルチプロセスでの類似部分木検索アルゴリズムを Algorithm

21 e

2

8

c

4 に示す．なお，このアルゴリズムは SPMD(Single Program

22頂点

c

Multiple Data) であり，r を現在実行しているプロセスのラ
20 d

6頂点
1

b

5

7

b

15 c

b

7頂点

3頂点
0

a

7頂点

3

a

4

a

6

a

13 b

11 b

14 b

9

a

10 a

頂点を後行順で格納した頂点配列を表す．Dr は，各頂点の後

19 c
17 b

行順番号，頂点の値と lef t(di ) に加え，親部分木の頂点数を18 b表す parSize と，親の頂点が属するプロセスのランクを表す

parRank ，di+1 が属するプロセスのランクを表す nextRank

3頂点
7頂点

ンクとする．Dr は r 番目のプロセスに割り当てられている

12頂点

12 a

16 a
8頂点

図 5: データベース木の分割例 2を持つ．

r = 2 番目のプロセスにおいて，図 5 に従い分割されたデー
タベース木と図 3 のクエリ木に対して θ = 3 でこのアルゴリ

ズムを適用した場合について考える．表 2 に，D2 に含まれる

Algorithm 4 SubtreeM atchingM ultiP rocess for Node r

情報を示す．Algorithm 2 との違いは主に受信部分である 7-13

Require: D r , Q, θ, r

行目と，送信部分である 29-32 行目である．d4 を処理した時

Ensure: Result = {i | T ED(Dir , Q) <= θ}

点で parRank が 1 を示しており，parSize が max|D| 以下

1: max|D| ⇐ |Q| + θであるため，プロセス 3 に頂点情報を送信しなければならない（29-30 行目）．同様に，d6 , d7 も d7 の処理後にプロセス１に送信される．次に， d11 を処理する際に next は３を示してい

2: next ⇐ r
3: for di : D r by post-order do
4:
5:

if |Di | > max|D| thengoto NEXTFOR

るため，プロセス 3 から頂点情報を受信しなければならない（96:

end if行目）．d10 をプロセス 3 から受信した時点で next が 2 にな

7:

while next =| r doり，処理が続行される（13 行目）．同様にして d12 ..d14 も受信

8:if next > r thenする．最後に，d20 を処理するが，|D20 | > max|D| であるた

9:

め，全ての処理は無視される（5 行目）．

10:

このアルゴリズムの重要な特徴として，先行順で木を分割し後行順で処理を行うことで，ほとんどの場合に各頂点情報の送

11:

receive dj from next node
else
next ⇐ r

12:

end if13:

end while

信タイミングが受信タイミングより早くなることが期待できる

14:

p = par(di )という点がある．これにより，プロセスをまたぐ頂点の処理の15:

if di は兄を持つ or di は根 or |Dp | > max|D| then

依存関係による通信待ちを防ぐことが期待できる．

16:
17:

値

4

a

lef t(di ) parSize parRank nextRank
4

3

1

1

6

a

6

2

2

2

7

b

6

6

1

1

9

a

9

3

2

3

11

b

9

7

2

3

15

c

9

12

2

3

20

d

9

22

if qj は兄を持つ or qj は根 thenT EDCalulation(Di , Qj )18:

表 2: 頂点配列 D 2
後行順

for j : 0 to |Q| − 1 do

1

1

19:
20:

end ifend for21:

end if22:

if di は根 or |Dp | > max|D| then23:

for k : lef t(di ) to i do
if dk .T ED[|Q| − 1] <= θ then24:

add k to Result

25:
26:

end if27:

end for28:// we can release buﬀer

4. 評 価 実 験29:else if di .parRank =| r then30:

send di to di .parRank node

4. 1 実験の目的および実験環境31:

本節では，実際に巨大な XML ファイルを用いて並列計算を行

32:

end ifうことで，手法の性能を評価する．実験は CPU: Xeon E5-2650

33:

NEXTFOR:34:

next = di .nextRankv3 2.3GHz 10 cores (hyper-threading: 20 cores)，Disk: Intel
Solid-State Drive 730 Series 240 GB を搭載したマシンを 9// we can release buﬀer

35: end for
36: return Result

ノード用意し，最大 180 コアの環境で行った．
実験では，データベース木 D として実データである dblp [13],SwissProt [14]，ProteinSequenceDatabase (PSD) [15] を使用
した．dblp, SwissProt，PSD の XML ファイルは XML Data

Repository [16] の物を利用した．また，Q にはそれぞれ D から抽出した適当なサイズの部分木を使用した．
本実験では，木編集距離の計算時のコストはどの操作も一律

1 として計算する．XML ファイルは予めパースし，プロセスの数に合わせて分割し，バイナリファイルに保存しておくものとする．また，各頂点が持つ値は XML ファイルの各頂点が持つラベルのハッシュを取り整数化したものを使用する．

4. 2 並列化効率の評価
3 種の XML データに対し，1 プロセスから 180 プロセスで類似部分木検索を行い実行時間を計測し，並列化効率を評価す
T1
る．なお，r プロセスでの実行時間が Tr とした時の， rTをr

並列化効率とする．|Q| = 64, θ = 20 とし，分割時の t は通信が発生しない程度に大きな値である 100 を使用した．
図 6 にプロセス数を変化させた時の実行時間との並列化効率を表す．結果では，プロセス数 9 から 18 にかけて大きく性能が減少しているが，これは実験環境が 9 ノード × 20 コアであるため，ディスクのシークにかかる時間が発生しオーバヘッドが生じていると考えられる．r = 1...9 および r = 18...180 にかけて，並列化効率を維持していることが確認できるため，本手法は充分なスケーラビリティを持つと考えられる．

4. 3 境界頂点数による通信量と実行時間のばらつきのト
レードオフ
データベース木 D の分割時に指定する t の値を変化させた
時にデータ通信量と実行時間がどのように変化するかを調べる．

|Q| = 512, θ = 20 とし，t = 1, 10, 100, 1000 の 4 種類の分割

0

20

40

60

80 100 120 140 160 180
プロセス数

実行時間 [秒]1

604.28604.86

実行時間 [秒]送受信バイト数
400

実行時間

50

実行時間

100
0

1

10

t

100

30
25

30

20
15
10
5
1

10

100

t

0
1000

図 8: 境界頂点数による実験 (180 プロセス)

1.4

1

0.6

200

35

40

1.6

0.8

300

45
40

10

1.2

500

66.09

送受信バイト数

0

602.9

67.25

20

0.1

バイト数 [MB]600

609.0167.260

図 6: 並列化効率の評価
700

67.27

70

100
10

50

80

バイト数 [MB]1000
dblp （効率）
SwissProt （効率）
PSD （効率）dblp （実行時間）
SwissProt （実行時間）
PSD （実行時間）

実行時間 [秒]プロセス数 1 に対する高速化率

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

5. ま と め
本稿では木構造データに対する類似部分木検索という問題を対象とし，複数ノードによる並列処理による手法を提案した．
同じ問題に対する既存の研究では枝刈りによる高速化が主だっ

0.4

たが，本研究では並列化という方法により高速化を成し遂げた．

0.2

実験による並列化性能の評価では，充分なスケーラビリティを

01000

図 7: 境界頂点数による実験 (9 プロセス)

確認できた．また，本手法は実験環境の通信コストの大小や想定されるクエリや閾値の大きさから，状況に適したデータの割り当てを行う方法を提案した．これは処理性能の良し悪しを左右することが予想されるが，実験では用いたデータの特徴から，通信量の違いによる時間の差しか確認することができなかった．

方法で実験した．

より局所性の高い木構造データを用いることで分割データの偏図 7 に 9 プロセスでの実験結果を，図 8 に 180 プロセスでりによる性能への影響が確認できることが期待できるが，これの実験結果を示す．実験結果では想定通り t が大きくなるほどは今後の課題とする．また，関連研究である [10] や [12] では

データ通信量が減り，わずかながら実行時間も減っていること

構造の局所性を利用し高速化を行っている．本手法にもこの工が確認できる．また，今回の設定では max|D| = 532 であるた

夫を取り入れることでさらなる実行時間の改善が期待できる.

め， t = 1000 の場合にはデータ通信が発生しない．今回の実

しかしながら，並列化効率を維持したまま取り入れることは難験環境はローカルネットワーク内で構成されたクラスタである

しいと考えられるため，これも今後の課題とする.

ため，プロセス間の通信コストが比較的小さい．通信コストが謝

さらに大きい環境で実行する場合は通信量の差による実行時間

本研究の一部は JSPS 科研費 25330124 の助成を受けたものの変化もより大きくなると考えられる．

辞

である．

また，さらに t の値を増やしていくと分割された木の頂点数に偏りが生じ実行時間が伸びていくと考えられる．しかし，今回使用したデータセットは木の頂点数に比べ木の高さが低く，根から出る辺のみで偏りの生じない分割が可能となり，t = |D|のような極端なパラメータ設定でも，180 プロセス程度であればある程度偏りの無い分割が可能となり，差が生じなかった．
一般的に XML データはこのような理由から分割の自由度が高いと考えられるが，もっと分割の自由度が低いような木構造
データを対象とする場合は t を値を増やすことにより性能が低下する可能性があると考えられる．

文

献[1] Joe Tekli, Richard Chbeir, and Kokou Yetongnon. Survey: An overview on XML similarity: Background, current
trends and future directions. Comput. Sci. Rev., Vol. 3,
No. 3, pp. 151–173, aug 2009.
[2] Philip Bille. A survey on tree edit distance and related problems. Theor. Comput. Sci., Vol. 337, No. 1-3, pp. 217–239,
jun 2005.
[3] Kuo-Chung Tai. The tree-to-tree correction problem. J.
ACM, Vol. 26, No. 3, pp. 422–433, July 1979.
[4] K. Zhang and D. Shasha. Simple fast algorithms for theediting distance between trees and related problems. SIAM
J. Comput., Vol. 18, No. 6, pp. 1245–1262, December 1989.
[5] Philip N. Klein. Computing the edit-distance between unrooted ordered trees. In Proceedings of the 6th Annual Eu-

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]
[14]
[15]
[16]

ropean Symposium on Algorithms, ESA ’98, pp. 91–102,
London, UK, UK, 1998.
Weimin Chen. New algorithm for ordered tree-to-tree correction problem. J. Algorithms, Vol. 40, No. 2, pp. 135–158,
August 2001.
Joe Tekli, Richard Chbeir, and Kokou Yétongnon. Efficient XML structural similarity detection using sub-tree
commonalities. In XXII Simpósio Brasileiro de Banco deDados, 15-19 de Outubro, João Pessoa, Paraı́ba, Brasil,
Anais, pp. 116–130, 2007.
Sudarshan S. Chawathe. Comparing hierarchical data inexternal memory. In Proceedings of the 25th International
Conference on Very Large Data Bases, VLDB ’99, pp. 90–
101, San Francisco, CA, USA, 1999.
Nikolaus Augsten, Denilson Barbosa, Michael M. Bohlen,
and Themis Palpanas. Eﬃcient top-k approximate subtree
matching in small memory. IEEE Transactions on Knowledge and Data Engineering, Vol. 23, No. 8, pp. 1123–1137,
2011.
Sara Cohen. Indexing for subtree similarity-search using
edit distance. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, SIGMOD’13, pp. 49–60, New York, NY, USA, 2013.
小柳涼介, 天笠俊之, 北川博之. テキストおよび構造の類似度に基づいた XML データに対する効率的な類似検索. In DEIM
Forum 2014 D7-5, 2014.
小柳涼介, 天笠俊之, 北川博之. 構造情報の再利用による XML
データに対する類似検索の高速化. 情報科学技術フォーラム講演
論文集, Vol. 13, No. 2, pp. 71–72, aug 2014.
dblp computer science bibliography.
http://dblp.
uni-trier.de/db/.
Uniprotkb/swiss-prot. http://web.expasy.org/docs/swiss-prot_
guideline.html.
Protein information resource. http://pir.georgetown.
edu/.
XML data repository. http://www.cs.washington.edu/
research/xmldatasets/www/repository.html.