論文 / 著書情報
Article / Book Information
論題(和文)
Title(English)

Subtree-based XML Data Integration Using Leaf-clustering BasedApproximate XML Join Algorithms

著者(和文)

梁 文新, 横田 治夫

Authors(English)

Wenxin LIANG, Haruo YOKOTA

出典(和文), Vol. 4, No. 4, pp. 21-24

Citation(English)

DBSJ Letters, Vol. 4, No. 4, pp. 21-24

発行日 / Pub. date

2006, 3

権利情報 / Copyright

本著作物の著作権は日本データベース学会に帰属します。
Copyright (c) 2006 Database Society of Japan, DBSJ.

Powered by T2R2 (Science Tokyo Research Repository)

論文
DBSJ Letters Vol.4, No.4――――――――――――――――――――――――――――――――――――
large tree similarity degree might not be the proper one
Subtree-based XML Data Integrationthat should be integrated. To solve this problem, we haveproposed an improved algorithm, SLAX (Subtree-class
Using Leaf-clustering Based
Leaf-clustering based Approximate XML join algorithm)
Approximate XML Join Algorithms
in [6].

In this paper, we discuss the subtree-based XML data
integration using the leaf-clustering based approximate
XML join algorithms (LAX and SLAX) for the fragments
divided from large XML documents. We propose asubtree-based integration method for integrating thematched subtree pairs determined by both LAX and SLAX.
We conduct experiments to compare the effectiveness ofthe subtree-based integration for real large bibliography
XML documents using LAX and SLAX, respectively. We
show the integration result for a sample subtree from the
XML document of SIGMOD record. The experimental
results show that the previous proposed algorithms are
effective for the subtree-based XML data integration.

In this paper, we propose a subtree-based XML data
integration method for integrating the matched subtree
pairs determined by both LAX and SLAX. We conduct
experiments to compare the effectiveness of thesubtree-based integration for real large bibliography XML
documents using LAX and SLAX, respectively. And weshow the integration result for a sample subtree from the
XML document of SIGMOD record. The experimental
results indicate that the previous proposed algorithms are
effective for the subtree-based XML data integration.
The remainder of this paper is organized as follows.
Section 2 briefly reviews the work related to this paper.
Section 3 shortly introduces the basic knowledge of theleaf-clustering based approximate XML join algorithms.
In Section 4, we propose the subtree-based integration
method. In Section 5, we do experiments using real large
bibliography documents and show the integration result.
Finally, Section 6 concludes this paper.

1. Introduction

2. Related Work

Wenxin LIANG♥

Haruo YOKOTA♠

XML has become the de facto standard for representing
and exchanging data over the World Wide Web. Recently,
a large number of data, for instance bibliography datasuch as DBLP [11] and ACM SIGMOD Record [1], andbioinformatics data such as TrEMBL [9] and Swiss-Prot[8], are published and exchanged by XML on the Internet.
However, XML documents from different data sources
may have nearly or exactly the same information but may
be different on structures. Besides, even the two XML
documents contain the same data, both of them may havesome extra information what the other does not do. Fig.1
shows two example XML documents. These two
documents are structurally different because of different
DTDs, but they represent very similar information. In
addition, each of them has some information what theother does not do. For example, endPage in Fig. 1 (a) andyear in Fig. 1 (b).
In previous work [5], we have proposed LAX (Leafclustering based Approximate XML join algorithm) for
measuring the approximate similarity between XML
documents. In order to compare the work based on thetree edit distance [3, 4], the output of LAX is oriented tothe pair of documents that has larger tree similarity
degree than the user-defined threshold [5]. However, large
XML documents must be divided into small fragments
when they are too large to be loaded into the main memory.
In this case, the target subtrees are distributed in eachfragment document. Therefore, when we apply LAX tosuch fragment documents, the matched subtrees selectedfrom the output pair of fragment documents that has

A well formed XML document can be parsed into anordered labeled tree [10]. The edit distance between twoordered labeled tree is defined as the minimum cost edit
operation (insertions, deletions and substitutions)required to transform one tree to another [12]. The tree
edit distance is regarded as an effective metric formeasuring the structural similarity in XML documents [2,3, 7]. However, the computational cost is extremely
expensive; in the worst case, it is an O (n4) operation forthe document of size n.
SIGMOD Reco rd

articlesarticle...
title

article...

...

articlee ndP age authors

A F ormal De finition o f
the re latio nal Mo de l29

author
C. J.
Date

(a)
D BLP

i npro cee d i ngs...

a rti cl e

...

...

a utho ry ea rA Fo rmal D ef i ni tio n o f
the re l ati o nal M od e l

C .J .
D ate

1 98 2ti tl eb oo k♥Student Member
Graduate School of Information
Science and Engineering, Tokyo Institute of Technology
wxliang@de.cs.titech.ac.jp♠
Regular Member
Global Scientific Information andComputing Center, Tokyo Institute of Technology
yokota@cs.titech.ac.jp

1

(b)
Fig.1

Example XML Documents

日本データベース学会 Letters Vol.4, No.4

論文
DBSJ Letters Vol.4, No.4――――――――――――――――――――――――――――――――――――
S. Guha, et al. proposed the lower and upper bound as
inexpensive substitutions for the tree edit distance
operation [2]. However, when the upper bound is greaterthan the threshold τ and the lower bound is less than τ ,the tree edit distance will still must be calculated.

3. Preliminaries
3.1 LAXLet Tb and Tt (b denotes base and t denotes target) be
two XML document trees. Assume Tb and Tt aresegmented into kb and kt subtrees t bi (1 ≤ i ≤ k b ) andt tj (1 ≤ j ≤ k t ) , respectively. The subtree similarity degree
between tbi and ttj, SSD (t bi , t tj ) is defined by Equation (1),where n and ni denote the number of matched leaf nodes(the pair of leaf nodes that has the same PCDATA value)
and the total number of leaf nodes in the base subtree .

SSD(t bi , t tj ) =n× 100%ni(1)

The matched subtree, TM[i] is defined as the pair ofsubtrees that has the maximum subtree similarity degree
in a join loop. The similarity degree of TM[i], SM[i] can becalculated by Equation (2).

S M [i ] = Max kj=t 1 ( SSD (tbi , ttj ))(2)

The tree similarity degree between Tb and Tt,
TSD (Tb , Tt ) is determined by the following equation
based on the mean value of the similarity degrees ofmatched subtrees.

∑ S [i] × 100%
TSD(T , T ) =
kb

i =1

b

t

kb

M

(3)

For two XML data sources Sb and St, assume eachdocument db ∈ Sb and dt ∈ St are parsed into XML
document trees Tb and Tt. Let Tb and Tt be segmented into
kb and kt subtrees tb and tt. Given a user-defined
threshold τ , LAX will output the pair of documents thathas larger tree similarity degree than the threshold τ ineach join loop. It is an O (n2) operation in the worst casefor the document of size n. The details of LAX areavailable in [5].

3.2 SLAX
When the XML documents are too large to be loaded
into the main memory, they must be segmented into small
fragments. Thus, when LAX is applied to such fragment
documents, a mismatching problem sometimes may occur.
Namely, the matched subtree selected from the output
pair of documents that has larger tree similarity degree
might not be the most similar one as the base one.
In [6], we have proposed SLAX to solve the mismatchingproblem in LAX. For two XML data sources Sb and St,
assume each document dbm ∈ Sb and dtn ∈ St are parsed
into XML document trees Tbm ( 1 ≤ m ≤ K ) and Ttn( 1 ≤ n ≤ L ). Let Tbm and Ttn be segmented into kb and kt
subtrees tbmi ( 1 ≤ i ≤ kb ) and ttnj ( 1 ≤ j ≤ kt ).

equation.

M [n] = Max kj =t 0 ( SSD(tbmi , ttnj ))(4)

The maximum match value, MMV[i] for the basesubtree tbmi is defined as followings.
L
MMV [i ] = Maxn=
0 ( M [ n])(5)Given a user-defined threshold T, SLAX will output thematched subtree pairs whose maximum match values arelarger or equal to the threshold T. The details of SLAX areavailable in [6].

4. Subtree-based XML Data Integration
In this section, we will propose a subtree-based XML
data integration method for integrating the matchedsubtree pairs selected by LAX and SLAX.
For a matched subtree pair tbi and ttj, assume tbi and ttj
have nb and nt leaf nodes, respectively.
Definition 1 (Matched Leaf). For a pair of leaf nodes Lbi

in tbi and Ltj in ttj, they are matched leaves, iff Lbi and Ltj
have the same PCDATA value.
Definition 2 (Nonmatched Leaf). For a leaf node Lbi in
tbi or Ltj in ttj, it is a nonmatched leaf, iff there is not any
leaf node in tbj or tti that has the same PCDATA value as
Lbi or Ltj.
Definition 3 (Insert Operation). For a nonmatched leaf
node Ltj in ttj, the insert operation, ins (Ltj, tbi) inserts thewhole path from the child node of Rt to Ltj into tbi below its
root node Rb.
The procedure of the subtree-based XML data
integration is illustrated in Fig. 2. Assume the number ofmatched leaves in the target subtree ttj is nm, the total
number of leaf nodes in the integrated subtree, N can be
figured out by the following equation.

N = nb + nt − nm

(6)

Example 1. For the matched subtree pair tb and tt
shown in Fig. 3, the nonmatched leaf in the target subtree
tt is “1998”. Therefore, the path {“year”, “1998”} will beinserted into the base subtree tb under its root node“article” as shown in the integrated subtree in Fig 4.
According to Equation (6), the total number of the result
subtree N = 3+4-3 = 4.
Input: Matched subtree pairs (tbi, ttj)
Output: Integrated subtree t(i)Assume tbi and ttj have nb and nt leaf nodes,
respectively.
begin{
t(i)=tbi ; //Reserve the whole base subtree as theprimal resultfor (k =1 to nt) {if (Ltk is a nonmatched leaf){ins (Ltk, t(i)) ; //Insert the nonmatched leaves inthe target subtree}}
return t(i) ;} end

The match value, M[n] for the base subtree tbmi andeach target tree Ttn ( 1 ≤ n ≤ L ) is defined by the following

Fig. 22

日本データベース学会 Letters Vol.4, No.4

Procedure of subtree-based integration

論文
DBSJ Letters Vol.4, No.4――――――――――――――――――――――――――――――――――――

...

...

article
title
XML

...

authors...

articleauthorauthortitle author author year

Max

John

XML

Max

John

1998

(a) Base subtree tb(b) Target subtree tt
Fig. 3 Example matched subtree pair

CPU
MemoryOS
Programming
EnvironmentIntel Pentium 4 2.80 GHz
1.0 GBMS Windows XP Professional
Sun JDK 1.4.2<article><title>On Global Multidatabase Query Optimization.</title><initPage>6</initPage><endPage>11</endPage><authors><author position="00">Hongjun Lu</author><author position="01">Beng Chin Ooi</author><author position="02">Cheng Hian Goh</author></authors></article>

articleFig. 5author author 1998
Max

Fig. 4year

John

Example integrated subtree

5. Experimental Evaluation
We conduct experiments to compare the effectiveness ofthe subtree-based integration for real large bibliography
XML documents using LAX and SLAX, respectively. The
experiments have been done under the environment asshown in Table 1.
In our experiments, we use a fragment file ofSigmodRecord.xml [1] named sigmod.xml (240KB, about
10,000 nodes) as the base document and 20 fragments of
DBLP.xml [11] named dblp1-20.xml (300KB, about 15,000
nodes) as the target ones. We sample a base subtree fromsigmod.xml as shown in Fig. 5. The match values for the
sample subtree and dblp1-20.xml are shown in Fig. 6 (a),and the tree similarity degrees for sigmod.xml anddblp1-20.xml are shown in Fig. 6 (b). The matched subtree
for the sample one will be selected from dblp8.xml by
SLAX because of the maximum match value. While thematched subtree for the sample one will be selected from
dblp13.xml by LAX.
Fig. 7 shows the real XML code of the matched subtree
for the sample one. From Fig. 7 (a), we can observe thatthe matched subtree selected from dblp8.xml by SLAX isexactly the same article as the sample subtree in Fig. 4.
However, Fig. 7 (b) indicates that the matched subtree
selected from dblp13.xml by LAX is not exactly the same
article as the sample one but written by the same authors.
Fig. 8 indicates the integration results for the matchedsubtrees selected by SLAX and LAX. From Fig. 8 (a), we
can see that the integration result using SLAX contains
the complete information for the same article from boththe base subtree and the matched target one. Although
the result using LAX shown in Fig. 8 (b) indicates that the
integrated subtree sometimes may not represent the same
information of an identical article, it is still available forcollecting valuable information, articles written by thesame authors for example. Therefore, we consider that ourprevious proposed algorithms are effective for thesubtree-based XML data integration.
Table 1 Experimental Environment

3

Sample subtree from sigmod.xml

6. Concluding Remarks
As more and more data are represented and exchanged
by XML on the World Wide Web, an algorithm that canefficiently measure the approximate similarity between
XML documents for the subtree-based integration ofmultiple XML documents becomes important.
In this paper, we have proposed a subtree-based XML
data integration method for integrating the matchedsubtree pairs determined by the previous proposed
leaf-clustering based approximate XML join algorithms,
LAX and SLAX. We conduct experiments to compare theeffectiveness of the subtree-based integration for reallarge bibliography XML documents using LAX and SLAX,
respectively. And we show the integration result for asample subtree from the XML document of SIGMOD
record. The experimental results indicate that ourprevious proposed algorithms are effective for thesubtree-based XML data integration.

Match valueXMLauthors

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
-0.1 1 2 3 4 5 6

7 8 9 10 11 12 13 14 15 16 17 18 19 20

dblp1-20.xml(a) Match values for the sample subtree fromsigmod.xml and dblp1-20.xml
0.19

Tree similarity degree

title

0.15
0.11
0.07
0.03
-0.01

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
dblp1-20.xml(b) Tree similarity degrees for sigmod.xml anddblp1-20.xml
Fig. 6 Results for bibliography data<article mdate="2002-01-03" key="journals/sigmod/LuOG92"><ee>db/journals/sigmod/LuOG92.html</ee><author>Hongjun Lu</author><author>Beng Chin Ooi</author><author>Cheng Hian Goh</author><title>On Global Multidatabase Query Optimization.</title><cdrom>sigmodR/21-4/P006.pdf</cdrom><year>1992</year><volume>21</volume><number>4</number>……
</article>

日本データベース学会 Letters Vol.4, No.4

論文
DBSJ Letters Vol.4, No.4――――――――――――――――――――――――――――――――――――(a) Selected from dblp8.xml by SLAX
<inproceedings mdate="2002-01-03" key="conf/sigmod/LowOL92"><crossref>conf/sigmod/92</crossref><author>Chee Chin Low</author><author>Beng Chin Ooi</author><author>Hongjun Lu</author><title>H-trees: A Dynamic Associative Search Index for OODB.</title><year>1992</year>……
</inproceedings>

Fig. 7(b) Selected from dblp13.xml by LAX
Real XML code of the matched subtree for the
bibliography documents<article><title>On Global Multidatabase Query Optimization.</title><initPage>6</initPage><endPage>11</endPage><authors><author position="00">Hongjun Lu</author><author position="01">Beng Chin Ooi</author><author position="02">Cheng Hian Goh</author></authors><ee>db/journals/sigmod/LuOG92.html</ee><cdrom>sigmodR/21-4/P006.pdf</cdrom><year>1992</year><volume>21</volume><number>4</number>……
</article>(a) Integration result using SLAX
<article><title>On Global Multidatabase Query Optimization.</title><initPage>6</initPage><endPage>11</endPage><authors><author position="00">Hongjun Lu</author><author position="01">Beng Chin Ooi</author><author position="02">Cheng Hian Goh</author></authors><crossref>conf/sigmod/92</crossref><author>Chee Chin Low</author><title>H-trees: A Dynamic Associative Search Index for OODB.</title><year>1992</year>……
</article>

Fig. 8(b) Integration result using LAX
Integration result for the sample subtree[Acknowledgements]
This work is partially supported by the Grant-in-Aid for
Scientific Research of MEXT Japan (#16016232), by
CREST of JST, and by the TokyoTech 21COE Program“Framework for Systematization and Application of
Large-Scale Knowledge Resources”.

[1] ACM SIGMOD Record in XML. Available at
http://www.acm.org/sigmod/record/xml/[2] M. Garofalakis and A. Kumar. Correlating XML data
streams using tree-edit distance embeddings. In Proc of
PODS'03, page 143-154, 2003.
[3] S. Guha, H. V. Jagadish, N. Koudas, D. Srivastava andT. Yu. Approximate XML Joins. In Proc. of ACM
SIGMOD 2002, pages 287-298, 2002.
[4] S. Guha, N. Koudas, D. Srivastava and T. Yu.
Index-Based Approximate XML Joins. In Proc. of ICDE
2003, pages 708-710, 2003.
[5] W. Liang and H. Yokota. LAX: An EfficientApproximate XML Join Based on Clustered Leaf Nodes
for XML Data Integration. In Proc. of BNCOD 2005,
Springer LNCS 3567, pages 82-97, July 2005.
[6] W. Liang and H. Yokota. SLAX: An Improved
Leaf-clustering Based Approximate XML Join Based on
Clustered Leaf Nodes for XML Data Integration at
Subtree Classes. In Proc. of DBWeb 2005, IPSJ
Symposium Series, 2005(16):41-48, November 2005.
[7] A. Nierman and H. V. Jagadish. Evaluating Structural
Similarity in XML Documents. In Proc. of WebDB 2002,
pages 61-66, 2002.
[8] Swiss-Prot. http://www.ebi.ac.uk/swissprot/.
[9] TrEMBL. http://www.ebi.ac.uk/trembl/.
[10] World Wide Web Consortium (W3C). The Document
Object Model (DOM). http://www.//w3.org/DOM/.
[11] XML Version of DBLP. Available at http://dblp.unitrier.de/xml/.
[12] K. Zhang and D. Shasha. Tree Pattern Matching.
Pattern Matching Algorithm, chapter 11. Oxford
University Press, 1997.

Wenxin LIANG
He received the B.E. and M.E. degrees in biomedical
electronic engineering from Xi’an Jiaotong University,
China in 1998 and 2001, respectively. He is currently aPh.D. student at the Department of Computer Science,
Graduate School of Information Science and Engineering,Tokyo Institute of Technology, Japan. His current researchinterests include XML data integration and management,
XML storage, indexing, labeling and querying techniques.
He is a student member of DBSJ and SIGMOD-J.

Haruo YOKOTA

He received the B.E., M.E., and Dr. Eng. degrees from
Tokyo Institute of Technology in 1980, 1982, and 1991,
respectively. He joined Fujitsu Ltd. in 1982, and was a
researcher at the ICOT for the Japanese 5th Generation
Computer Project from 1982 to 1986, and at Fujitsu
Laboratories Ltd. from 1986 to 1992. From 1992 to 1998,
he was an associate professor in Japan Advanced Instituteof Science and Technology (JAIST). He is currently aprofessor at Global Scientific Information and Computing
Center, and Department of Computer Science in Graduate
School of Information Science and Engineering in Tokyo
Institute of Technology. His current research interests
include general research area of data engineering,
information storage systems and dependable computing.
He is a member of DBSJ, IPSJ, IEICE, JSAI, IEEE,
IEEE-CS, ACM, ACM-SIGMOD, and ACM-SIGARCH.

[References]4

日本データベース学会 Letters Vol.4, No.4