DEIM Forum 2013 B2-4

MapReduce による大規模な並列 XML 類似検索手法の評価
VuTuanDat†

渡辺 陽介††

横田 治夫†††† 東京工業大学 工学部 情報工学科†† 東京工業大学 学術国際情報センター††† 東京工業大学 大学院情報理工学研究科 計算工学専攻〒 152-8552 東京都目黒区大岡山 2-12-1
E-mail: †vu.t.aa@m.titech.ac.jp, ††watanabe@de.cs.titech.ac.jp, †††yokota@cs.titech.ac.jp
あらまし XML はデータ交換や蓄積のためのフォーマットとして，企業や組織において Office Open XML，XHTMLなどで様々な形で多く利用されている．データの爆発的増加に伴い，複数の XML 木の中から類似した XML 木を探し出すことが重要になっている．既存の高速な類似度計算アルゴリズムとして LAX があるが，それでも膨大なデー
タに対して処理時間がかかる．そこで本稿では，大量の XML 木に対応するため，MapRedue フレームワークを用いて LAX の並列化アルゴリズムを提案する．MapReduce の各タスクへの割り当ての手法として，同一リーフノードの部分木を集約する手法と部分木集合の組み合わせを割り当てる手法を実現し，実際の XML 木を利用してそれらの手法の評価を行う．
キーワード

XML 類似検索，MapReduce

Evaluation of MapReduce-based Large-Scale Parallel XML Similarity
Search Methods
TuanDat VU† , Yousuke WATANABE†† , and Haruo YOKOTA†††† Department of Computer Science，School of Engineering，Tokyo Institute of Technology†† Global Scientific Information and Computing Center，Tokyo Institute of Technology††† Department of Computer Science，Graduate School of Information Science and Engineering
Tokyo Institute of Technology
2-12-1 Ookayama，Meguro-ku，Tokyo，152-8550 Japan
E-mail: †vu.t.aa@m.titech.ac.jp, ††watanabe@de.cs.titech.ac.jp, †††yokota@cs.titech.ac.jp
Abstract As a format for data exchange and data storage，XML is most commonly used in companies and organizations in various types of applications such as Office Open XML and XHTML. Along with the data explosion，
searching similar XML tree from multiple XML trees becomes important. The existing LAX algorithm was proposed
for efficiently calculating the XML Similarity degree of two XML trees. However it takes much time with large scaledata. In this paper，to cope with a large number of XML trees，we propose parallel algorithms that perform LAX
using MapReduce framework. In our experiments，we evaluate our methods by using actual xml trees and synthetic
ones.
Key words XML Similarity Search，MapReduce

1. は じ め にExtensible Markup Language(XML) はデータ交換と蓄積のされている．データの爆発的増加に伴い，大量の XML 木に対しては，複数の XML 木の中から類似した XML 木を探し出す
需要が高まっている（ [4] [6] [8] [10] [11] [12]）．

ためのフォーマットとして 1998 年 2 月に World Wide Web

既 存 の 類 似 度 計 算 ア ル ゴ リ ズ ム と し て Tree Edit Dis-

Consortium(W3C) から勧告された．XML はデータの記述能

tance(TED) [8]，tag similarity [10]，または entropy を用いた力に優れ，伝達，交換にも適しており，近年，企業や組織にお手法 [11] などがある．精度が高く計算量も低い Leaf-Clustering

いて Office Open XML，XHTML などで様々な形で多く利用

Based Approximate XML(LAX [4]) アルゴリズムも知られている. しかし，高速な LAX アルゴリズムでも膨大なデータにクエリを並列に処理する手法を提案している．野村らは，XPath

対して処理時間がかかる．そのため並列化による高速化が求めクエリのパス表現について，木スケルトンを用いて処理する手られている．

法を提案している．そのほかに，武藤らの GPU と CPU を用

並列分散プログラミング環境として，MPI(Message Passing

いた XML 検索手法 [13] もある．これは GPU と CPU を用い

Interface) ライブラリ [3] がよく使われているが，プログラムがて並列に処理可能な XML インデクスの手法を提案し，それを大規模になるに従い複雑化し，エラー処理や障害処理などを記用いた検索手法となっている．

述する実装コストが高いことが知られている．一方で，並列プ

MapReduce を用いた XML 類似検索については Yuan らのログラミングに慣れていない開発者でも扱いやすい分散処理フ手法 [6] がある．これは pq-grams を利用し，XML 木を tree-

レームワーク MapReduce [2] が注目されている．MapReducegram に分解して，Jaccard similarity を使って類似度を計算すでは，map 関数と reduce 関数を定義するだけで，大規模なデー

る．しかし，このアルゴリズムは XML 木の構造しか考えない．

タの並列処理が可能となるシンプルなフレームワークである．

LAX は木の構造とリーフノードの値の一致から類似度を求めまた，計算機の故障や追加に対応する．

ることができる．

このような背景から，本研究では MapReduce を用いた LAXの並列化を目的とする．MapReduce の各タスクへの割り当ての手法として，同一リーフノード部分木集約数え上げ手法と部

3. 前 提 知 識
3. 1 Hadoop と MapReduce

分木集合組み合わせ割り当て手法を実現する．LAX において

Hadoop [1] とは大規模なデータを複数のコンピューターで部分木の類似度を計算するとき，同じ値を持つリーフノードを分散処理できるようにしたオープンソースソフトウェアであカウントする必要があり，同一リーフノード部分木集約数え上る．Hadoop は分散ファイルシステム Hadoop Distributed File

げ手法は同一リーフノードを含む部分木を数え上げるときに並System（HDFS），分散処理フレームワーク MapReduce とい列化を行う．一方，部分木集合組み合わせ割り当て手法は複数

う大きく二つのコンポーネントで構成される．

回の XML 木間の類似度計算を計算スレッドごとに分割して処MapReduce のデータは非常にシンプルで key と value の組

理する．また，実際の XML 木を利用してそれらの手法の評価

み合わせで管理する．MapReduce の処理は map 処理，shuffleを行う．

& sort 処理と reduce 処理の 3 段階に分けて実行される仕組み

本稿の構成は以下の通りである．まず，2. 節で関連研究について述べ，3. 節で MapReduce と LAX アルゴリズムを説明すになっている．このうち，ユーザーが外部から処理内容を与えるのが map と reduce である．

る．次に 4. 節で MapReduce を用いた並列化手法を提案する．

5. 節で実験を通じて，提案手法の評価を行い，最後に 6. 節で

2. 関 連 研 究の中で最も有名なのは Tree Edit Distance(TED) [8] である．

TED は文字列の比較アルゴリズムの編集距離から木構造に使

ศ๭㸰

0DS



ධຊ

XML 木の類似度計算にはいくつかの方法が提案される．そShuffle&Sortศ๭㸯

まとめを述べる．

ࢹ࣮ࢱ

5HGXFHฟຊ㸯

5HGXFH

ฟຊ㸰

ศ๭㸱
ศ๭㸲

0DS




えるように拡張した．TED の精度が高いが計算量が現在最も

ศ๭㸳

咄
咄
咄

計算量が少ない方法 [9] でも O(n3 ) である．そのほかに，tagsimilarity [10]，entropy を用いた手法 [11] 等が存在し，いずれ0DS

図 1 MapReduce 処理の流れも高速で計算量 O(n) であるが，それらのアルゴリズムは精度が低いという問題がある．精度が高く計算量 O(n2 ) の高速な類似度計算手法として LAX [4] もよく知られている．LAX は

そ れ ぞ れ の フェー ズ で は ，「key − value ペ ア」ま た はXML 木を部分木に分割し，部分木の類似度により XML 木の「key − value の リ ス ト ペ ア」を 入 出 力 と し て 扱って い る ．

類似度を計算する．

MapReduce 処理の流れは図 1 を示し，以降では，各フェーXML 類似検索のアプリケーションの一つとして，Structure-ズの詳細を述べる．

based Office Document Search(SOS [15] [16]) があり，これはMap フェーズでは，入力データは細かいブロックに分割さOffice Open XML 文書を対象にしたスタイル類似検索手法でれ，多くのマシンに分散される．一つのブロックは一つの map

ある．SOS は OOXML 文書内に含まれる複数 XML 木同士の処理を実行する単位である map タスクへ割り当てられる．map

類似度を計算し，それらを集約して OOXML 文書の類似度をタスクはブロックを読み込み，ユーザーが定義した map 関数

求める．しかし，大量の OOXML 文書の類似検索には実行時を実行する．map 関数は入力された 1 個の key-value ペアを内間がかかるため，高速な類似度計算手法が望まれる．

部で処理して，新たな key-value ペアとして出力する．出力す

分散環境での並列 XML 検索に関連する研究として，野村芳明ら [14] は，スケルトン並列プログラミングを用いて，XPathる key-value ペアは 2 個以上になることもあるし，1 個もない
こともある．

Shuffle & Sort フェーズは，map フェーズが出力した keyvalue ペアをマージしてソートし，同じ key を持つ key-value
ペア同士を集約する．key ごとに value をリストアップして，下の式で定義される．

Simsub (Tbi ，Ttj ) =|M atchedLeaf (Tbi ，Ttj )|×100(%)(2)|Leaf (Tbi )|reduce タスクに振り分ける．この処理は Hadoop 側が面倒を

ただし，|Leaf (Tbi )| は部分木 Tbi に属するリーフノード数，

見てくれるので，ユーザーは何もする必要がない．

|M atchedLeaf (Tbi ，Ttj )| は Tbi ，Ttj に属するリーフノードのReduce フェーズは（key，value のリスト）ペアを受け取って，内部で処理した結果を新たな key-value ペアとして出力する．

中で，PCDATA が同じペアを作った場合のペア数とする．
（ 3 ） XML 木間の類似度
部分木同士の類似度から XML 木全体の類似度を求める．XML

本研究では，LAX の処理を並列化するため，LAX と同等の処理を行うアルゴリズム map 関数，reduce 関数として実現

木 Tb ，Tt の類似度を求める関数 Sim(Tb ，Tt ) は，各 XML 木の部分木集合 Sbase ，Starget から以下の式で定義される．

する．

Sim(Tb ，Tt )3. 2 LAX による XML 木間の類似度計算
LAX [4] は与えられた 2 つの XML 木の Tb (base)，Tt (target)=P

Tbi ∈Sbase(maxTtj ∈Starget (Simsub (Tbi ，Ttj )))|Sbase |に対して類似度 Sim(Tb ，Tt ) を求めるアルゴリズムである．

XML 木を部分木に分解し，部分木間の類似度をリーフノードに着目して求めていくという処理を行う．LAX の処理手順を(3)

4. 提 案 手 法
本節は最初に 4. 1 で本研究が扱う問題について明確化し，4. 2

図 2 に示し，以降では各手順の詳細を述べる．

以降で提案手法について述べる．
Sbase
Tb1 T

Tb

4. 1 問 題 定 義

Sbase
Tb1

b2

2 つの XML 木集合 Base と T arget が与えられたとき，BaseTb2

集合の各 XML 木 Tb に対して，T arget 集合の中から類似度の
A B
Segmentation
Spot

C
Tt

A

D C

A B

C

StargetTt1
Tt2

A

1. 㒊ศᮌ䜢⏕ᡂ

C

A B

k 以上となる XML 木 Tt を全て求める．

䐠

䐟
Tt1

D C

䐢
䐡
StargetTt2

A

TargetBase

D C

2. 㒊ศᮌ䛾㢮ఝᗘィ⟬…

max(ձ, ղ) + max(ճ, մ)Sim(Tb , Tt ) =
2

…

...

3. XMLᮌ䛾㢮ఝᗘ䜢ィ⟬
図 2 LAX の処理の流れ…
㢮ఝXMLᮌ䝨䜰(㢮ఝᗘӍk)（ 1 ） 部分木の生成

LAX で は XML の 木 構 造 を 部 分 木 に 切 り 分 け る 点 を
SegmentationSpot と呼んでいる．XML 木内のあるノード

図 3 XML 類似検索の問題

x が，どれだけ SegmentationSpot に相応しいかを表す値 Wは 以下の式で表される．

W = n × dφ

入力：

(1)

閾値 k(0 < k < 100)

ただし，n はノード x の子ノードの数，d はノード x からリー

Base:XML 木集合

フノードまでの最大距離，φ は重み付け調節できる定数を表わ

T arget:XML 木集合

している．base と target の XML 木それぞれに対して，全ノー

出力：

ド中最も大きい Wx を持つノード x を見つけ，x の子ノードを{((Tb , Tt ), Sim(Tb , Tt ))|Tb ∈ Base, Tt ∈ T arget,
Sim(Tb , Tt ) >= k}

ルートノードとした部分木に元の XML 木を分割する．
（ 2 ） 部分木の類似度

4. 2 概Tb の部分木集合 Sbase と Tt の部分木集合 Starget のそれぞれ

3. 2 節より LAX による XML 木の類似度を計算するとき，の要素同士のペア (Tbi , Ttj ) ∈ (Sbase × Starget ) で，部分木とステップ 1 で XML 木から部分木を生成しなければならない．

しての類似度を求める． XML 木 Tb の部分木 Tbi , XML 木 Tt

複数の XML 木に対しては XML 木を各 Map タスクに分割し，の部分木 Ttj の類似度を計算する 関数 Simsub (Tbi ，Ttj ) は以

分散処理を行う一つの XML 木は 1 回のみ解析する．

要Map㒊ศᮌ䚸䝸䞊䝣䝜䞊䝗⏕ᡂ

Tb11 ,Tt11

1
ẁ┠

Reduce䝸䞊䝣䝜䞊䝗ẖᩘ䛘ୖ䛢

Map
2
ẁ
┠

ReduceXMLᮌẖ㢮ఝᗘィ⟬Reduce䝷䝧䝹ẖ䛾㢮ఝᗘィ⟬㒊ศᮌ㞟ྜ䛾⤌䜏ྜ䜟䛫๭䜚ᙜ䛶ᡭἲ

ྠ୍䝸䞊䝣䝜䞊䝗㒊ศᮌ㞟⣙ᩘ䛘ୖ䛢ᡭἲ
図4

Tb12 ,Tt12

Key: 㒊ศᮌ
Value: 㒊ศᮌ

map2

Map

㒊ศᮌ䛸๭䜚ᙜ䛶䝷䝧䝹సᡂXMLᮌ䛤䛸䛾䝨䜰సᡂ

Tb11 ,Tt21(Tb1 ,Tt1),(Tb11 ,Tt11)(Tb1 ,Tt2),(Tb11 ,Tt21)(Tb1 ,Tt1),(Tb12 ,Tt12)

Key: XMLᮌId䝨䜰
Value: 㒊ศᮌ䝨䜰

Shuffle&Sort(Tb1 ,Tt1),[(Tb11 ,Tt11) ,(Tb12 ,Tt12)]

Simsub(Tb11,Tt11)=1/2=50%
Simsub(Tb11,Tt12)=0/2=0%
Simsub(Tb12,Tt11)=0/1=0%
Simsub(Tb12,Tt11)=1/1=100%=>Sim(Tb1,Tt1)=(max(50,0)+max(0,100))/2=75%(Tb1 ,Tt2),[(Tb11 ,Tt21)]

Key: XMLᮌId䝨䜰
Value: 㒊ศᮌ䝨䜰䛾䝸䝇䝖

Simsub(Tb11,Tt21)=1/2=50%
Simsub(Tb11,Tt22)=0/2=0%
Simsub(Tb12,Tt21)=0/1=0%
Simsub(Tb12,Tt21)=0/1=0%=>Sim(Tb1,Tt2)=(max(50,0)+max(0,0))/2=25%

reduce2

図 6 同一リーフノード部分木集約数え上げ手法 MapReduce2 段目

木ペアごとにグループ化しなければならないので MapReduce2

提案手法段で行う必要がある．まず，1 段目では各 XML 木を解析して，Base

同じ値を持つリーフノードを含む部分木をグループ化して，部

TargetTb1

Tt1

分木ペアとして出力する．次に，2 段目では部分木のペアを集

Tt1

計して，部分木ごとの類似度を計算して，XML 木の類似度を
A B

C

Tb12

Starget1
Tt11
Tt12

C

A

B,Tb11

Sbase1

Tb11

D C

A

計算する．

D

B

同一リーフノード部分木集約数え上げ手法はにおける MapRe-

map1
Starget2
Tt21
Tt22

duce の手順は以下のように行われる（図 5 と図 6 は実行例）．
（ 1 ） 一段目の Map（図 5 の map1）

A

B

D

C

B

A,Tt11

D,Tt12

B,Tt21

C,Tt12

D,Tt22
Shuffle&Sort

D

入力： key: XML 木 Id，value: XML 木
出力： key: リーフノードのデータ，value: 部分木A,Tb11
C,Tb12

A,[Tb11 ,Tt11]

B,[Tb11 ,Tt21]

C,[Tb12 ,Tt12]

Key: 䝸䞊䝣䝜䞊䝗䛾䝕䞊䝍
Value: 㒊ศᮌD,[Tt12 ,Tt22]

reduce1
Tb11 ,Tt11

Tb11 ,Tt21

Tb12 ,Tt12

Key: 䝸䞊䝣䝜䞊䝗䛾䝕䞊䝍
Value: 㒊ศᮌ䛾䝸䝇䝖

Key: 㒊ศᮌ
Value: 㒊ศᮌ

図 5 同一リーフノード部分木集約数え上げ手法 MapReduce1 段目

処理：XML 木を解析し（LAX のステップ 1），各リーフノードに対して，データとリーフノードを含む部分木を出力する．
（ 2 ） 一段目の Reduce（図 5 の reduce1）
入力： key: リーフノードのデータ，value: 部分木のリスト
出力： key: Base の部分木，value: Target の部分木
処理：部分木のリストから同じリーフノードの値を key とする (Tbi ，Ttj ) の部分木ペアを生成する．これは LAX のステップ 2 において，同じ値を含むリーフノードを持つ部分木のペア

また，MapReduce の各タスクへの割り当て手法として，2手法を提案した．同一リーフノード部分木集約数え上げ手法はLAX のステップ 2 において，同じ値を持つリーフノードを含む部分木を数え上げるときに並列化を行う．部分木集合組み合
わせ割り当て手法は LAX のステップ 1 において，大量の XML(Tbi , Ttj ) の MatchedLeaf 集合の要素を求める処理に相当する．
（ 3 ） 二段目の Map（図 6 の map2）
入力： key: Base の部分木，value: Target の部分木
出力： key: XML 木 Id ペア，value: 部分木ペア
処理：Base の部分木 Tbi と Target の部分木 Ttj からそれぞれ木に対して，XML 部分木集合の組み合わせごとに分けて計算の部分木を含む XML 木の Id を取り，XML 木 Id ペア (Tb ，Tt )する．XML 部分木集合それぞれに対する処理をどこの Reduceを key，部分木ペア (Tbi ，Ttj ) を value として出力する．

で行うかをラベル付けする．以降では各手法の詳細を説明する．

4. 3 同一リーフノード部分木集約数え上げ手法
LAX のステップ 2 で部分木の類似度を計算するとき，同じ値を持つリーフノードをカウントする必要がある．そして，

base の XML 木と target の XML 木の部分木同士のすべての類似度を計算しなければならないので，カウント時間がかかる．そこで，同一リーフノード部分木集約数え上げ手法はリー
フノードのデータを key，その key を含む部分木を value とし，

MapReduce によって同一リーフノードを含む部分木を数え上げるときに並列化を行う．
同じ値を含むリーフノードの部分木リストがあっても，部分（ 4 ） 二段目の Reduce（図 6 の reduce2）
入力： key: XML 木 Id ペア，value: 部分木ペアのリスト
出力： key: XML 木 Id ペア，value: XML 木の類似度
処理：部分木ペア (Tbi ，Ttj ) のリストから，LAX のステップ 2 の残りの処理である．同じ値を含むリーフノードの MatchedLeaf
集合の要素数のカウントと，部分木の類似度を計算を行う．そして，その結果から XML 木の類似度を計算する（LAX のス
テップ 3）．
上記は部分木を value としたが，実際に部分木のすべての情報を利用する必要がなく，一部の情報を使えばいいので部分木の代わりに部分木オブジェックトを用いる．部分木オブジェッ

表1

Tt1 Tt2 Tt3 Tt4
Tb1 …Label1…
Tb2(Reduce…䝍䝇䜽Id)…

Tb3 … …
Label3
Tb4 … …

Intel Xeon E5620OS

Core 数8

CoreFrequency

2.40GHzメモリ…
…
Label2…
…
…
…
Label4
…
…

実験機材

CPU

24GB

OS

Ubuntu11.10

Java

1.6

HadoopVersion 1.0.4

Ethernet

1GB/s（ 2 ） Reduce（図 8 の reduce）
入力： key: Reduce タスク Id，value: 部分木集合のリスト
出力： key: XML 木 Id ペア，value: XML 木の類似度
処理：部分木集合のリストの中に base の部分木集合 Sbase を

図7

部分木集合組み合わせ割り当て手法

listOf Bases に格納する．部分木集合リストの中に各 targetの部分木集合 Starget に対して，全ての Sbase ∈ listOf Bases

クトは（XML 木 Id，XML 木の部分木数，部分木 Id，部分木のリーフノード数）のみを持つものとする．

に，Sim(Sbase ，Starget ) を計算する．

5. 実

験

4. 4 部分木集合組み合わせ割り当て手法
Base の集合と T arget の集合のそれぞれの要素同士で，XML

本節では，実際に大量の XML 木に対して提案手法を適用し木の類似度を計算する必要があるので．Base，T arget それぞて高速化することができたのか，どの程度効果があるのかを実れの要素数を m，n とすると XML 木ペアの数は m × n とな験により検証する．

る．すなわち，類似度は m × n 回を計算しなければならない．

5. 2 節では，人工データを生成し，データセット内の似ていそこで，部分木集合組み合わせ割り当て手法は m × n 回の計算るものを増やして提案手法の性能を比較する実験を行った．5. 3を計算スレッドごとに分割して処理する．

節と 5. 4 節では，実際の XML データ (DBLP のレコード [5])XML 部分木集合それぞれに対する処理をどこの Reduce でを利用し、マシン台数を変更した場合と XML 木数を変更した

行うかをラベル付けする．例として，図 7 は ReduceTask を四場合の実験を行った．

つにした場合であり，各タスクは 4 回の類似度計算を負担する．

5. 1 実験の設定

まず，map では XML 木を解析する．解析した XML 木は部分

マシン台数 1 台〜4 台 (表 1) を利用して実験を行った．

木集合の Sbase または Starget とする．そして，部分木集合を

5. 2 節では，人工データとして部分木数を 100，各部分木の振り分ける reduce タスクを求め，reduce タスク Id を key，部

リーフノード数を 10 となる XML 木を生成した．5. 3 節と 5. 4

分木集合のリストを value とした key-value ペアを出力する．

節では，実際の XML データの DBLP のレコード [5] から取り，

Reduce では全ての Sbase ∈ 部分木集合のリスト をメモリ上に小さな XML 木に分けたものを用いた．ただし，各 XML 木は乗せて，各 Starget に対して Sbase と Starget の類似度を計算す

部分木数 100，リーフノード数は約 900 とした．

る（LAX のステップ 2，3）．部分木集合のリストの Sbase は

5. 2 人工データによる類似度変化した場合の性能の比較多すぎるとメモリ上に乗せられないこともあるので利用するマ

同一リーフノード部分木集約数え上げ手法の実行時間はデーシンのメモリに応じて Sbase の集合を何等分に分けるかを事前

タセット内の同一リーフノードの部分木ペア数によっても変わに決める必要がある (図 7 の場合は Sbase ,Starget とも 2 等分にると予想し，二つの提案手法を比較するため，人工データセッ

分けた)．

トを用いた実験を行った．

部分木集合組み合わせ割り当て手法はにおける MapReduce

各データセットは Base の XML 木数 400，Target の XMLの手順は以下のように行われる（図 8 は実行例）．

木数 800 の XML データを生成した．各 XML 木では，部分木（ 1 ） Map（図 8 の map）

数を 100，各部分木のリーフノード数を 10 とした．

入力： key: XML 木 Id，value: XML 木

データセット中の同じデータを含むリーフノードの部分木の

出力： key: Reduce タスク Id，value: 部分木集合 (Sbase また

ペアの数を変えて，実験を行った．データセットを表 2 に示し，は Starget )実験結果を図 9 に示す．縦軸は実行時間であり，横軸は右に行

処理：XML 木を解析し（LAX のステップ 1），部分木集合のけばいくほどデータセット内の似ているものが多くなる．

Sbase または Starget が得られる．XML 木 Id と reduce タスク

図 9 より，データセット内の似ているものが多くなると同一数を利用して，その部分木集合に振り分ける reduce タスクのリ

リーフノード部分木集約数え上げ手法の実行時間が線形的に増ストを求める．それぞれの reduce タスクに対して，reduce タ

えるが，部分木集合組み合わせ割り当て手法の実行時間はあまスクを key，部分木集合を value とした key-value を出力する．

り変動しないことが分かった．その理由はデータセット内の似

Tb1

Tb2

Tb3

Tb4

Tt1

Tt2

Tt3

Tt4

Sbase1 = parse(Tb1); Sbase2 = parse(Tb2); …. Starget4 = parse(Tt4) (LAX䛾䝇䝔䝑䝥1)
1,Sbase1

1,Sbase2

3,Sbase3

3,Sbase4

1,Starget1

2,Sbase1

2,Sbase2

4,Sbase3

4,Sbase4

2,Starget1

1,Starget2…
2,Starget2

map

3,Starget3

3,Starget4

4,Starget3

4,Starget4

Shuffle&Sort
1,[Sbase1,Sbase2,Starget1,Starget2]

3,[Sbase3,Sbase4,Starget1,Starget2]

2,[Sbase1,Sbase2,Starget3,Starget4]

4,[Sbase3,Sbase4,Starget3,Starget4]

Sim(Sbase1,Starget1);
Sim(Sbase2,Starget1);
Sim(Sbase1,Starget2);
Sim(Sbase2,Starget2);
䜢ィ⟬䛩䜛

……

Key:Reduce㻌
Task䛾Id
Value: 㒊ศᮌ㞟ྜ

Key:Reduce㻌 Task䛾Id
Value: 㒊ศᮌ㞟ྜ䛾䝸䝇䝖

Sim(Sbase3,Starget3);
Sim(Sbase4,Starget3);
Sim(Sbase3,Starget4);
Sim(Sbase4,Starget4);䜢ィ⟬䛩䜛

reduce(LAX䛾䝇䝔䝑䝥䠎䠈䠏)図 8 部分木集合組み合わせ割り当て手法

表 2 XML データセット情報ᐇ⾜᫬㛫(seconds)

300

同一リーフノードの部分木ペア数

Data1

0

Data2

20,000,000

Data3

40,000,000

Data4

60,000,000

Data5

80,000,000ྠ୍䝸䞊䝣䝜䞊䝗㒊ศᮌ㞟⣙ᩘ䛘ୖ䛢ᡭἲ㒊ศᮌ㞟ྜ⤌䜏ྜ䜟䛫๭䜚ᙜ䛶ᡭἲྠ୍䝸䞊䝣䝜䞊䝗㒊ศᮌ㞟⣙ᩘ䛘ୖ䛢ᡭἲ300
ᐇ⾜᫬㛫(seconds)

350

データセット㒊ศᮌ㞟ྜ⤌䜏ྜ䜟䛫๭䜚ᙜ䛶ᡭἲ

250

200
150
100

50
0
200

250
200
150

400
600
Target XMLᮌᩘ

800

図 10 XML 木数による並列化の効率

100
50

5. 3 木数による並列化の効率

0
0
2
4
6
8
ྠ୍䝸䞊䝣䝜䞊䝗䜢ྵ䜐㒊ศᮌ䛾䝨䜰ᩘ(༓୓)

本実験では実際の DBLP [5] から XML データを取り，小さな XML 木に分けたものを用いた．各 XML 木は部分木数 100，
リーフノード数は約 900 とした．Base 集合の XML 木数は 100

図9

人工データによる類似度変化した場合の性能の比較とし，Target 集合の XML 木数を増やした場合の実行時間を図10 に示す．
ているものが多くなると同一リーフノードを含む部分木ペア数が増えるが，一方で XML 木ペア数は似ているものの数に依存しないからである．
同一リーフノードの部分木ペア数は 0 と 2 千万の場合で，実行時間がほぼ同じ理由については，Hadoop のハートビートの最小値は 3 秒であり，各タスクの処理が 3 秒以内で終了したとしても次のハートビートまでは待つ必要があり，処理の軽いタ
スクでも少なくとも最低 3 秒がかかってしまうためである．
同じデータを含むリーフノードの部分木のペア数により，2手法の実行時間が違うことから，データセットの線形的な特徴
によりどの手法を利用するかを決めることが望ましい．

図 10 より，XML 木数が上昇するにつれて 2 手法とも実行時間が線型的に増える傾向がある．
また，部分木集合組み合わせ割り当て手法は同一リーフノー
ド部分木集約数え上げ手法よりかなり早いと分かった．その理由については，まず同一リーフノード部分木集約数え上げ手法の場合 2 段階での MapReduce において各段の準備時間がある [1] ので，MapReduce1 段の部分木集合組み合わせ割り当て手法より 2 倍くらい時間がかかる．そして，実験データの特徴
で，同じ値を含むリーフノードの部分木ペアが多く，5. 2 節と同様に，実行時間が遅くなったと考えられる．

(A)(#22240005) の助成により行われた。

800

ྠ୍䝸䞊䝣䝜䞊䝗㒊ศᮌ㞟⣙ᩘ䛘ୖ䛢ᡭἲ

ᐇ⾜᫬㛫(seconds)

700
600

㒊ศᮌ㞟ྜ⤌䜏ྜ䜟䛫๭䜚
ᙜ䛶ᡭἲ

500
400
300

文

200
100
0
1

2
䝬䝅䞁ྎᩘ

4

図 11 マシン台数による並列化の効率

5. 4 マシン台数による並列化の効率
節 5. 3 の実験と同じように DBLP [5] のレコードから取り，
小さな XML 木に分けたものを用いた (各 XML 木は部分木数

100，リーフノード数は約 900 とした)．Base 集合の木数は 100，
Target 集合の木数は 800 とし，マシン台数を増やした場合の実行時間を図 11 に表す．
図 11 より，どちらの手法でもマシン台数が増えることによって実行時間が短くなり，並列化の効果が見える．
また，部分木集合組み合わせ割り当て手法は同一リーフノー
ド部分木集約数え上げ手法よりかなり早い理由は 5. 3 節の実験で述べた理由と同様である．

6. ま と め
本研究では，MapReduce を用いた XML 類似度計算 LAX
アルゴリズムを並列化し，大量の XML 木に対する XML 類似検索を行う同一リーフノード部分木集約数え上げ手法と部分木集合組み合わせ割り当て手法を提案した．実験により，提案手法を評価した．データセット内に類似したものが少ない場合は同一リーフノード部分木集約数え上げ手法の方が早く，逆に類似したものが多い場合は部分木集合組み合わせ割り当て手法の方が早いことが分かった．また，どちらの手法も XML 木数が増えると実行時間が線形的に増加する．更に，マシン台数が増
えるとどちらの手法でも実行時間が短くなり，並列化の効果が確認できた．
今後の課題として，データセットを変えた実験を行う必要がある．同一リーフノード部分木集約数え上げ手法の実行時間は異なるデータセットによっても変わると予想しており，異なる
データセットを用いた実験を行う．また，XML 木の部分木数やリーフノード数も変えて実験する必要がある．また，マシン
台数を更に増やした実験を行う．XML 木間の類似度を計算す
る途中で類似度の閾値以下のことが分かる場合もあるので，枝刈りの手法も検討する．

謝

辞本研究の一部は、日本学術振興会科学研究費補助金基盤研究

献[1] Apache Hadoop.
http://hadoop.apache.org，2012[2] Jeffrey Dean，Sanjay Ghemawat，“Mapreduce: Simplied
data processing on large clusters”，Proceedings of the 6th
Symposium on Operating Systems Design and Implementation (OSDI ’04)，pp.137-149，2004[3] Message Passing Interface Forum
http://www.mpi-forum.org，2012[4] W. Liang and H. Yokota. “LAX: An Efficient Approximate
XML Join Based on Clustered Leaf Nodes for XML Data
Integration”，In Proc. of BNCOD，pp.82-97，2005[5] DBLP XML records.
http://dblp.uni-trier.de/xml/，2012[6] Peisen Yuan，Chaofeng Sha，Xiaoling Wang，Bin Yang，
Aoying Zhou，Su Yang，“XML Structural Similarity Search
Using MapReduce”，Web-Age Information Management，
11th International Conference，WAIM 2010，Jiuzhaigou，China，July 15-17，2010. Proceedings Volume 6184，pp.169181，2010[7] T. Elsayed，J. Lin，and D. Oard. “Pairwise document similarity in large collections with MapReduce”，In ACL，Companion Volume，pp.265-268，2008.
[8] K.C.TAI.，“The Tree-toTree Correction Problem”，Journalof the Association for Computing Machinery Vol 26，No 3，
July 1979，pp.422-433，1979[9] E.D.Demaine, S.Mozes, B.Rossman, and O.Weimann, “AnOptimal Decomposition Algorithm for Tree Edit Distance”,
ACM Trans. Algorithms, 6(1) : Article 2, 2009.
[10] D.Buttler，A Short Survey of Doucment Structure Similarity Algorithms，In Proceedings of the 5th International
Conference on internal Computing，USA，pp.3-9，2004.
[11] S.Helmer，“Measuring the Structural Similarity of Semistructured Documents Using Entropy”，In Proceedings of the
VLDB 07Conference，pp.0122-1032，2007.
[12] Nikolaus Augsten，Michael Bhlen，Johann Gamper，“Approximate matching of hierarchical data using pq-grams”，
VLDB，pp.301-312，2005[13] 武藤教宏，廣田雅春，横山昌平，福田直樹，石川博，“GPU と
CPU の並列処理に適した XML インデクス生成と検索手法”，
DEIM，2012[14] 野村芳明，江本健斗，松崎公紀，胡振江，武市正人，“木スケルトンによる XPath クエリの並列化とその評価”，コンピュータ
ソフトウェア 24(3)，pp.51-62，2007[15] 上垣外 英剛，渡辺 陽介，横田 治夫，“Office XML 文書の部分木に着目した類似スタイルのファイル検索”，DEIM，2012[16] Yousuke Watanabe，Hidetaka Kamigaito，Haruo Yokota“Style-based Similarity Search for Office XML Documents”，
iiWAS，pp.138-146，2012