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

SLAX: An Improved Leaf-Clustering Based Approximate XML Join
Algorithm for Integrating XML Data at Subtree Classes

著者(和文)

梁 文新, 横田 治夫

Authors(English)

Wenxin Liang, Haruo Yokota

出典(和文)

情報処理学会論文誌データベース, Vol. 47, No. SIG 8 (TOD30), pp. 4757

Citation(English)

IPSJ Transaction on Database, Vol. 47, No. SIG 8 (TOD30), pp. 47-57

発行日 / Pub. date

2006, 6

権利情報 / Copyright

ここに掲載した著作物の利用に関する注意: 本著作物の著作権は（社）情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
The copyright of this material is retained by the Information Processing
Society of Japan (IPSJ). This material is published on this web site withthe agreement of the author (s) and the IPSJ. Please be complied with
Copyright Law of Japan and the Code of Ethics of the IPSJ if any users
wish to reproduce, make derivative work, distribute or make available tothe public any part or whole thereof.

Powered by T2R2 (Science Tokyo Research Repository)

Vol. 47

No. SIG 8(TOD 30)

IPSJ Transactions on Databases

June 2006

Regular Paper

SLAX : An Improved Leaf-Clustering Based Approximate XML
Join Algorithm for Integrating XML Data at Subtree Classes
Wenxin Liang† and Haruo Yokota†,††XML is widely applied to represent and exchange data on the Internet. However, XML
documents from diﬀerent sources may convey nearly or exactly the same information but may
be diﬀerent on structures. In previous work, we have proposed LAX (Leaf-clustering based
Approximate XML join algorithm), in which the two XML document trees are divided into
independent subtrees and the approximate similarity between them are determined by the tree
similarity degree based on the mean value of the similarity degrees of matched subtrees. Our
previous experimental results show that LAX, comparing with the tree edit distance, is more
eﬃcient in performance and more eﬀective for measuring the approximate similarity between
XML documents. However, because the tree edit distance is extremely time-consuming, weonly used bibliography data of very small sizes to compare the performance of LAX with thatof the tree edit distance in our previous experiments. Besides, in LAX, the output is oriented
to the pair of documents that have larger tree similarity degree than the threshold. Therefore,
when LAX is applied to the fragments divided from large XML documents, the hit subtree
selected from the output pair of fragment documents that has large tree similarity degree might
not be the proper one that should be integrated. In this paper, we propose SLAX (Subtreeclass Leaf-clustering based Approximate XML join algorithm) for integrating the fragments
divided from large XML documents by using the maximum match value at subtree classes.
And we conduct further experiments to evaluate SLAX, comparing with LAX, by using both
real large bibliography and bioinformatics data. The experimental results show that SLAX
is more eﬀective than LAX for integrating both large bibliography and bioinformatics data
at subtree classes.

plete information.
The Document Type Descriptor (DTD)
is recognized as a helpful tool to detect
the structural information from XML docHowever, even if XML
uments 2),6),7),13) .
documents have the same DTDs, they may
not have identical tree structures because of
the repeating and optional elements and atFigure 1 shows an extributes 9),10),13) .
ample of two XML documents (sample fragments from the XML ﬁles of Swiss-Prot 20)
and TrEMBL 21) , respectively) with very similar DTDs. Although these two documents
are structurally diﬀerent due to the repeating
and optional elements, they express very similar information. Besides, each of the document
has some information what the other does not
do. For instance, comment in Fig. 1 (a); andevidence in Fig. 1 (b).
The tree edit distance is widely used as an effective metric for measuring the structural similarity between XML documents 9),13) . However,
it is a very expensive operation; in the worst
case, the time complexity is O(n4 ) for the document of size n, where n is the number of thenodes of the document.
In previous work 11) , we have proposed LAX

1. Introduction
The Extensible Markup Language (XML) is
widely applied to represent and exchange dataon the Internet, because it can represent diﬀerent kinds of data from multiple sources. Nowadays more and more data, especially bioinformatics such as Swiss-Prot 15) , TrEMBL 17)
and bibliography data such as DBLP 22) andACM SIGMOD Record 1) , are published andexchanged by XML on the Internet. However,XML documents from diﬀerent data sources
might contain nearly or exactly the same information but might be constructed by diﬀerent
structures. Besides, even the two XML documents convey the same contents, both of them
may have some extra information what theother does not do. Therefore, it becomes important that an algorithm can eﬃciently measure the similarity between XML documents for
integrating such data sources so that the users
can conveniently access and acquire more com† Department of Computer Science, Graduate Schoolof Information Science and Engineering, Tokyo Institute of Technology†† Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology
47

48

IPSJ Transactions on Databases

(a)

(b)
Fig. 1 Example XML documents.

(Leaf-clustering based Approximate XML join
algorithm), in which the two XML document
trees are divided into subtrees representing independent information units, and the output
is oriented to the pair of documents that haslarger tree similarity degree than the userdeﬁned threshold. We have also proposed aneﬀective algorithm for segmenting XML documents into independent subtrees for LAX. We
have shown that LAX is more eﬃcient in performance comparing to the tree edit distance,
because it is an O(n2 ) operation for the document of size n in the worst case. Because thetree edit distance is extremely time-consuming,
we only used bibliography data of very small
sizes to compare the performance of LAX withthat of the tree edit distance in our previous
experiments. In addition, in order to compare with the work based on the tree edit distance 9),10) , the output of LAX is oriented tothe pair of documents that have larger tree similarity degree (mean value of the similarity degrees of matched subtrees) than the threshold.
The large XML documents sometimes can not
be loaded into the main memory, they must
be divided into small fragments. In this case,the target subtrees are distributed in each fragment document. Therefore, when LAX is applied to such fragment documents, the hit subtrees selected from the output pair of fragment
documents that has large tree similarity degree
might not be the proper one that should be integrated.
In this paper, we propose SLAX (Subtree-

June 2006

class Leaf-clustering based Approximate XML
join algorithm) to integrate fragments divided
from large XML documents by using the maximum match value at subtree classes. We conduct further experiments to compare SLAX
with LAX on the performance and eﬀectivenessby using both large real bibliography and bioinformatics data. The experimental results indicate that the precision of subtree matching using SLAX is twice larger than that using LAX
for bibliography data. And SLAX is useful andvaluable for people to acquire similar proteins
belonging to the same species, organisms, andso on, even if the two XML documents do notcontain exactly the same proteins.
The rest of this paper is organized as follows.
Section 2 brieﬂy introduces the work related
to the paper and the requirements for the issues of measuring approximate similarity between XML documents. In Section 3, we introduce the basic knowledge of LAX. Section 4
describes the problem of LAX when it handles
fragments divided from large XML documents
and proposes SLAX for solving this problem.
In Section 5, we conduct experiments to compare SLAX with LAX by using both large real
bioinformatics and bibliography data. In theend, Section 6 concludes the paper and outlines
the future work.
2. Related Work and Requirements
A well formed XML document can be parsed
into an ordered labeled tree 19) . The tree structure represents the nesting of its elements, andnode labels record the contents of the elements
by element tags, attribute names, attribute values and PCDATA values.
Many researches have been done to solve theproblem of measuring the edit distance between
ordered labeled trees 3)∼5),8),12),14),16),18),23)∼25) .
The edit distance between two ordered labeledtrees is deﬁned as the minimum cost edit operations (insertions, deletions and substitutions)required to transform one tree to another. It
can be ﬁgured out by a mapping between thenodes of the two trees 25) . The tree edit distance is regarded as an eﬀective metric for measuring the structural similarity in XML documents 8),9),13) . However, its computational cost
is extremely expensive; in the worst case, it isan O(n4 ) operation for the document of size n.
Thus, it is of diﬃculty for the tree edit distanceto handle the XML documents of large sizes.
In order to avoid the expensive tree editVol. 47

No. SIG 8(TOD 30)

SLAX : An Improved Leaf-Clustering Based Approximate XML

distance operation as much as possible, S.
Guha, et al. proposed the lower and upper bound as inexpensive substitutions forthe tree edit distance operation 9) . However,when the upper bound is greater than thethreshold distance τ and meanwhile the lower
bound is less than τ , the tree edit distancewill still must be calculated. Therefore, weneed a more eﬃcient metric for measuring
the approximate similarity between XML documents. As the matter of fact, many real
XML documents are constructed by repeating
elements, entry in the uniprot sprot.xml 20)
and uniprot tremb.xml 21) for example. Suchkind of XML documents can be segmented
into subtrees representing independent units byrooting the subtrees at the repeating elements.
The approximate similarity between the wellsegmented documents can be eﬀectively determined by computing the similarity degree basedon the clustered leaf nodes of each pair of subtrees even without considering the structuraland semantic heterogeneity.
3. Introduction of LAX
3.1 Overview
In previous work 11) , we have proposed LAX
for evaluating the approximate similarity between XML documents. In LAX, the two XML
documents to be joined are segmented into
subtrees representing independent information
units. And the approximate similarity between
them are determined by the tree similarity degree that is the mean value of the similarity
degrees of the matched subtrees.
Notation. Let T1 and T2 be two XML document trees. Let T1 be the base tree, and T2
be the target one. Assume T1 and T2 are segmented into k1 and k2 sub-trees t1i (1 ≤ i ≤ k1 )and t2j (1 ≤ j ≤ k2 ), respectively.
The subtree similarity degree between t1i andt2j , SS (t1i , t2j ) is deﬁned by Equation (1) as thepercentage of the number of matched leaf nodes(the pair of leaf nodes that has the same PCDATA value) out of the number of leaf nodes inthe base subtree t1i , where n and n1i denote thenumber of matched leaf nodes and the numberof leaf nodes in the base subtree t1i .
n
SS (t1i , t2j ) =× 100 (%)
(1)
n1i
The matched subtree, TM [i] is deﬁned as thepair of subtrees that has the maximum subtree
similarity degree in one join loop; that is, thesimilarity degree of TM [i], SM [i] can be calcu-

49

lated as follows.
2(SS (t1i , t2j ))SM [i] = M axkj=1(2)

In the ith join loop, the matched subtree
TM [i] is a hit subtree, iﬀ SM [i] ≥ T (0 < T ≤ 1),
where T is the user deﬁned threshold for the
output subtrees.
The tree similarity degree between T1 and T2 ,ST (T1 , T2 ) is determined by Equation (3) basedon the mean value of the similarity degrees ofmatched subtrees.
k1
SM [i]
× 100 (%) (3)ST (T1 , T2 ) = i=1k1
3.2 Segmentation Algorithm
Many real XML documents are constructedby repeating elements, and they can be divided
into independent subtrees at the repeating elements. However, there might be many diﬀerent
repeating elements with the same tag names
in diﬀerent levels. For instance, entry andname in Fig. 1 (a). Therefore, it is not an easytask to segment the XML document tree into
subtrees at the proper positions. In previous
work 11) , we have proposed an eﬀective algorithm for segmenting XML document trees, inwhich the spot for segmentation is determinedby the weighting factor w. For a candidate element E(n, d), where n denotes the number ofcandidate elements among its children, and drepresents the the distance to its furthest descendant. The weighting factor w can be calculated by the following equation,w = n × dθ

(0 < θ ≤ 1)

(4)

where, θ is an adjustable constant.
3.3 Join Process
Let S1 and S2 be two XML data sources. Assume each document d1 ∈ S1 and d2 ∈ S2 areparsed into XML document trees T1 and T2 .
Let T1 and T2 be segmented into k1 and k2 subtrees t1i and t2j . Given a user-deﬁned thresholdτ , the join process of LAX is illustrated by Algorithm LAX shown in Fig. 2.
3.4 Comparison with Tree Edit DistanceFor the document of size n, in the worst case,
LAX is an O(n2 ) operation while the tree edit
distance is an O(n4 ) one. Our previous experimental results indicate that as the size of document increases, LAX becomes overwhelmingly
faster relative to the tree edit distance 11) . As
for two XML documents with diﬀerent DTDs
that have the same number of nodes, the tree

50

IPSJ Transactions on Databases

June 2006
TB1

Algorithm LAX {Input: XML data source S1 and S2
Output: Pairs of XML documents (d1 , d2 )for each d1 ∈ S1 {parse d1 into T1 ;segment T1 into k1 subtrees;for each d2 ∈ S2 {parse d2 into T2 ;segment T2 into k2 subtrees;
calculate ST (T1 , T2 );

tB11

}

tB12

(a) Base document tree

if(ST (T1 , T2 ) ≥ τ ) {TT 1

output (d1 , d2 );

TT 2

}
}
}

Fig. 2 Algorithm LAX.

edit distance of them will not increase muchwhen the PCDATA values of the leaf nodes
change. While in LAX, the tree similarity degree will change in a large scale as the values ofthe leaf nodes change. Our previous experimental results show that LAX can eﬀectively distinguish the similarity diﬀerences between XML
documents even the tree edit distances of them
are almost the same 11) .
4. SLAX
4.1 Problem of LAX
In this paper, we just use the original reallarge XML documents without storing theminto RDBs. When the XML documents are toolarge to be loaded into the main memory, theymust be divided into small fragments. In thiscase, the target subtrees are distributed in eachfragment document. Besides, in LAX, the output is oriented to the pair of documents thathave larger tree similarity degree (mean valueof the similarity degrees of matched subtrees)
than the threshold. Therefore, when LAX isapplied to such fragment documents, the hit
subtrees selected from the output pair of fragment documents that has large tree similarity
degree might not be the proper one that should
be integrated.
Example 1. For the base document tree TB1 ,and the target ones TT 1 and TT 2 divided froma large XML document tree TT in Fig. 3, thetree similarity degrees ST (TB1 , TT 1 ) = 66.7%
and ST (TB1 , TT 2 ) = 50%. Assume the threshold for the output 0.5 < τ ≤ 0.667, and thethreshold for the hit subtree T ≤ 0.667. Because
ST (TB1 , TT 1 ) = 66.7% > τ > ST (TB1 , TT 2 ) =

tT 11

tT 12

tT 21

tT 22

(b) Target document tree
Fig. 3 Problem of LAX.

0.5, the document tree pair (TB1 , TT 1 ) will be
output. Therefore, the subtree pair (tB12 , tT 12 )(SS (tB12 , tT 12 ) = 66.7% > T ) will be selected as the hit subtree by LAX. However,
the most proper subtree pair is actually the(tB12 , tT 21 ), because SS (tB12 , tT 21 ) = 100% >SS (tB12 , tT 12 ) = 66.7%.
4.2 Key Definitions for SLAX
Before we propose the improved algorithm
SLAX to solve the problem mentioned in Section 4.1, we present the following notations anddeﬁnitions.
Notation. Let SB and ST be two XML data
sources, where B denotes base and T denotes
target. Assume each document dBm ∈ SB (1 ≤m ≤ K) and dT n ∈ ST (1 ≤ n ≤ L) are parsed
into XML document trees TBm (1 ≤ m ≤ K)
and TT n (1 ≤ n ≤ L). Let TBm and TT n be
segmented into kB and kT subtrees tBmi (1 ≤i ≤ kB ) and tT nj (1 ≤ j ≤ kT ).
Definition 1 (Match Value). The matchvalue M[n] for the subtree tBmi and each target tree TT n (1 ≤ n ≤ L) is defined as the thefollowing equation.
T(SS (tBmi , tT nj ))M [n] = M axkj=0(5)

Definition 2 (Maximum Match Value).
The maximum match value MM [i] for the sub-Vol. 47

No. SIG 8(TOD 30)

SLAX : An Improved Leaf-Clustering Based Approximate XML

Algorithm SLAX {Input: XML data source SB and ST
Output: Pairs of subtrees (tB , tT )parse SB into TB ;parse ST into TT ;divide TB into K fragment trees TBm ;for (m = 1 to K) {segment TBm into kB subtrees;for (i = 1 to kB ) {MM [i] = 0;//Maximum match value for each basesubtree tBmi
divide TT into L fragment trees TT n ;for (n = 1 to L) {segment TT n into kT subtrees;
M [n]=0;//Match value for each target fragmenttree TT nfor (j = 1 to kT ) {calculate SS (tBmi , tT nj );M [n] = M ax(SS (tBmi , tT nj ), M [n]);}if(M [n] ≥ MM [i]) {MM [i] = M ax(M [n], MM [i]);N = n;//Record the index of the target fragmenttree}}
if (MM [i] ≥ T ){output(tBmi ,tT N j );}}}}Fig. 4 Algorithm SLAX.

tree tBmi is defined as following equation.
(6)
MM [i] = M axL
n=0 (M [n])Definition 3 (Matched Tree). The matchedtree TM i for each subtree tBmi is defined as thetarget tree TT n that has the maximum M [n].
Definition 4 (Matched Pair). The matchedpair Pi for the subtree tBmi is defined as thepair of subtrees that has the maximum matchvalue.
Definition 5 (Hit Pair). Given a threshold
T (0 < T ≤ 1), the matched pair Pi is a hit
pair PHi , if the maximum match value of Pi ,MM [i] ≥ T . The hit pair PHi should be output
as the final result.
4.3 Algorithm SLAXLet SB and ST be two XML data sources, andeach dBm ∈ SB and dT n ∈ ST be parsed into
XML document trees TBm and TT n . Assume
TBm and TT n are segmented into kB and kT
subtrees tBmi and tT nj . Given a user-deﬁned
threshold T , the algorithm SLAX is illustrated
by Fig. 4.

51

Example 2. For the base tree TB1 and the target ones TT 1 and TT 2 in Fig. 3, The matchedtrees TM 1 and TM 2 for the subtree TB11 and
TB12 are TT 1 and TT 2 , respectively. And thematched pairs P1 and P2 of the subtree TB11 and
TB12 are (tB11 , tT 11 ) and (tB12 , tT 21 ), respectively. Assume T < 0.667, both of the matched
P1 and P2 are the hit pairs and should be output
as the final results.
4.4 Comparison with LAX
The main diﬀerences between the improved
algorithm SLAX and the original one LAX aresummarized as follows:• Application Object The application object for LAX is to measure the approximate similarity between XML documents,
while that for SLAX is to detect the subtrees that represent the same or similar information in XML documents from diﬀerent sources, so that the XML documents
can be integrated at subtree classes.
• Join Base and Target The join base andtarget for LAX are oriented to XML documents, while those for SLAX are subtreeoriented.
• Basis for Subtree Matching In LAX,
the subtree matching must be selected fromthe pair of XML documents that has larger
tree similarity degree than the threshold.
While in SLAX, the subtree matching is directly based on the maximum match value
for the base subtree and the target one.
5. Experimental Evaluation
In our previous experiments 11) , we havecompared the performance of LAX with thetree edit distance for measuring the approximate similarity between XML documents. Because the tree edit distance is extremely timeconsuming, we only used very small bibliography XML documents; the mean size of the fragment ﬁles of SIGMOD Record 1) and DBLP 22)
we used was 4.32 KB (about 200 nodes). In
this paper, we conduct experiments to compare
SLAX with LAX by using diﬀerent types oflarge XML data. We should have compared
SLAX and LAX with the tree edit distance.
However, the tree edit distance is too timeconsuming to be applied to the large data. But
anyway, our previous experimental results haveshown that LAX is more eﬃcient and eﬀective
for measuring the approximate similarity between XML documents than the tree edit distance even for small data 11) .

52

IPSJ Transactions on Databases

In order to observe and compare how eﬀectively SLAX and LAX determine the matchedsubtree by using the maximum match value andthe tree similarity degree, respectively, we deﬁne the precision of subtree matching, P as follows.
Definition 6 (Precision of Subtree Matching). The precision of subtree matching (P )is the percentage of the number of correctly
matched subtree (Nc ) out of the total numberof subtrees (N )in the base document as the following equation.
Nc
× 100(%)(7)
P =N
We use both real bibliography and bioinformatics data that are more than 100 times largerof sizes to evaluate SLAX and LAX in the following aspects.
• How do the document size and the numberof the segmented subtrees impact the execution time of SLAX and LAX for diﬀerent
types of large XML data?
• What is the diﬀerence in the characteristic and performance for SLAX and LAX
to integrate diﬀerent types of large XMLdata?
• What is the diﬀerence in the precision ofsubtree matching for bibliography documents using the maximum match value andthe tree similarity degree, respectively?
5.1 Data Used
5.1.1 Bibliography Data
The main characteristic of the bibliography
document is that the number of leaf nodesof each segmented subtree is small. A bibliography XML document can be generally divided into a large number of subtrees representing a literature item such as an article anda book. The size of each subtree in the bibliography document is quite small. For example, the mean number of leaf nodes of ansegmented subtree in SigmodRecord.xml 1) is
only 5.8. In our experiments, we use SigmodRecord.xml (482 KB, about 20,000 nodes) and
955 fragments divided from DBLP.xml 22) . The
size of each fragment is 300 KB (about 15,000
nodes).
5.1.2 Bioinformatics Data
Comparing with the bibliography data, bioinformatics data, such as protein data, contains a
lot of information in each entry. Therefore, thesize of each segmented subtree becomes muchlarger in the bioinformatics data. For instance,
the mean number of leaf nodes of a 3 MB frag-June 2006

Table 1 Experimental environment.
CPU
MemoryOS
Programming
Environment

AMD Athlon 64 3500+ 2.20 GHz
1.0 GBMS Windows XP Professional
Sun JDK 1.4.2

Table 2 Precision of subtree mathcing forbibliography data.
LAX
SLAX

Nc
33
71

Ni
67
29

P
33%
71%

ment of uniprot sprot.xml 20) is 42.4.
Because the original protein XML documents
are too big to be loaded into the main memory, we divide the uniprot sprot.xml 20) anduniprot trembl.xml 21) into fragment ﬁles. The
size of each fragment of uniprot sprot.xml 20)
is 3 MB (about 80,000 nodes), and that of
uniprot trembl.xml 21) is 1 MB (about 25,000
nodes).
5.2 Experimental Environment
The experiments have been done under theenvironment shown in Table 1.
5.3 Experimental Results
5.3.1 Bibliography Data
For the bibliography data, we take the SigmodRecord.xml as the base document, andall the 955 fragments of DBLP.xml, named
DBLP1.xml-DBLP955.xml as the target ones.
The number of segmented subtrees of the SigmodRecord.xml is 1504, and the mean numberof those of the DBLP fragment ﬁles is 640. The
mean execution time for handling each pair of
documents by SLAX is 3.77 seconds.
We randomly sample 100 base subtrees from
SigmodRecord.xml to compose a document,
named sigmod.xml, using the same DTD as SigmodRecord.xml. Then, we join the sigmod.xml
with the 955 framents of DBLP.xml by using
the tree similarity degree and maximum matchvalue, respectively. The number of correctly
matched subtrees (Nc ), the number of incorrectly matched subtrees (Ni ) and the precisionof subtree mathcing (P ) using LAX and SLAX
are shown in Table 2.
Here we show a real example of mismatching
using LAX. We use SigmodRecord.xml as thebase document, and randomly choose 40 fragments of DBLP.xml as the target ones. Figure 5 shows the match values for the sample subtree and each fragment of DBLP.xml,
and Fig. 6 shows the source code of a sub-Vol. 47

No. SIG 8(TOD 30)

SLAX : An Improved Leaf-Clustering Based Approximate XML

Fig. 5 Match values for the sample subtree anddblp1.xml-dblp40.xml.

53

Fig. 8 Tree similarity degrees for SigmodRecord.xml
and dblp1.xml-dblp40.xml.

Fig. 6 Sample subtree from sigmod.xml.
Fig. 9 The matched subtree selected by LAX from
dblp14.xml.
Table 3 The number of subtrees and the mean
execution time.
N
TS
TL

Fig. 7 The matched subtree selected by SLAX from
dblp24.xml.

tree sampled from SigmodRecord.xml. The
matched subtree for the sample subtree is selected by SLAX from dblp24.xml because of
the maximum match value, and its source codeis shown in Fig. 7. It is evident that thematched subtree determined by SLAX represents exactly the same article as the sample
subtree. Figure 8 shows the tree similarity degrees for SigmodRecord.xml and each fragmentof DBLP.xml. Because the tree similarity degree between dblp14.xml and SigmodRecord is
the largest among the 40 fragments, the numberof hit pairs in dblp14.xml is larger than thosein dblp24.xml; that is the number of similar
subtrees in dblp14.xml is larger than that in
dblp24.xml. However, the source code in Fig. 9shows that the matched subtree determined by
LAX from dblp14.xml is not exactly the same

trembl1

trembl2

trembl3

trembl4

trembl5

324
3.53s
3.57s

349
3.61s
3.69s

389
3.70s
3.72s

414
3.74s
3.75s

327
3.55s
3.60s

article as the sample one but written by thesame authors.
5.3.2 Bioinformatics Data
In order to learn how the document
size and the number of segmented subtrees impact the excution time for SLAX
and LAX, we randomly choose 5 fragmentsof uniprot trebml.xml, named trembl1.xmltrembl5.xml, and join them with 40 fragments of uniprot sprot.xml, named sprot1.xmlsport40.xml. N , TS and TL in Table 3 indicate
the number of subtrees in trembl1-5.xml andthe mean execution time to join a pair of fragment ﬁles by SLAX and LAX, respectively.
Because the documents from TrEMBL and
Swiss-Prot do not contain exactly the same protein information, it is of diﬃculty to quantitively deﬁne the precision of subtree matchingfor the protein data without expert knowledge.
Therefore, in this paper we only conduct experiments to verify if our algorithm can ﬁnd thesimilar protein from the target fragments for a

54

IPSJ Transactions on Databases

June 2006

Fig. 10 Base subtree sampled from trembl4.xml.

Fig. 12 The Matched subtree selected by SLAX fromsprot31.xml.

Fig. 11 Match values for trembl4.xml and the
sprot1.xml-sprot40.xml.

sample protein in the base fragment.
We choose trembl4.xml as the base document and sprot1.xml-sprot40.xml as the target ones. The number of segmented subtreesof trembl4.xml is 414 and the mean numberof those of sprot1-40.xml is 387. Figure 10
shows the source code of the base subtree sampled from trembl4.xml, and Fig. 11 indicatesthe match values for the sample subtree andsprot1-40.xml. The matched subtree for the
sample one will be selected from sprot31.xml
by SLAX. Figure 12 shows the source codeof the matched subtree determined by SLAX.
From Fig. 10 and Fig. 12, we can observe thatthe matched subtree pair determined by SLAX
represents very similar proteins belonging to
the same organism. In respect of LAX, the tree
similarity degrees for trembl4.xml and sprot140.xml are shown in Fig. 13. Figure 14 shows
the source code of the matched subtree for the
sample one selected by LAX from sprot22.xml.
It is apparent that the matched subtree determined by LAX is totally a diﬀerent protein corresponding to the base one. AlthoughFig. 13 Tree similarity degree for trembl4.xml andsprot1.xml-sprot40.xml.

the matched pairs for protein data selected by
SLAX sometimes may not denote exactly thesame proteins, it is still helpful and valuable forpeople to obtain the group of proteins belonging to the same species, organisms, and so on.
5.4 Discussion and Comparison
According to the results of the experiments,
we outline the following discussions and comparisons to summarize the characteristics andthe diﬀerences of SLAX and LAX when theyhandle diﬀerent types of large XML documents.
• From Table 3 and Fig. 15, we can observethat SLAX is slightly faster than LAX. Besides, the execution time for joining a pairof documents for both SLAX and LAX increases tardily as the number of segmented
subtrees increases. With regard to theimpact of document sizes, the integrationof large documents might be faster thanVol. 47

No. SIG 8(TOD 30)

SLAX : An Improved Leaf-Clustering Based Approximate XML

Fig. 14 The Matched subtree selected by LAX fromsprot22.xml.

Fig. 15 Execution time for joining a pair ofbioinformatics fragments.

55

does not exist in the maximum peak butother peaks having the close value to the
maximum one.
• For the bibliography data, the similarity
degree of subtrees with smaller number ofleaf nodes are easier to be the same because of the smaller n1i in Eq. (1). Therefore, it may happen to get multiple subtreesthat have the same similarity degree. On
the other hand, the maximum match value
for the hit subtrees for bioinformatics data
might be small because of the large numberof leaf nodes in each subtree.
• SLAX can more precisely detect the proper
matched subtree for integrating the fragments divided from large XML documents
than LAX. For the bibliography data,
SLAX can eﬀectively detect the matchedsubtree that contains exactly the same information as the base one. The precisionof subtree matching using SLAX is twice
larger than that using LAX. For the protein data, SLAX is useful and valuable forpeople to acquire similar proteins belonging
to the same species, organisms, and so on,even the two XML documents do not contain exactly the same proteins. Therefore,
we consider that SLAX is applicable andeﬀective for integrating both large bibliography and bioinformatics data at subtree
classes.
6. Conclusions and Future Workthat of small ones. For example, the total
mean size of SigmodRecord.xml and DBLP
fragment ﬁles is about 0.8 MB and that ofthe protein fragment ﬁles is about 4.0 MB.
However, the mean time for handling theprotein data by SLAX is 3.63 seconds whilethat for processing the bibliography data is
3.77 seconds. It takes less time for SLAX
to handle the protein data, because thenumber of segmented subtrees of bibliography data is much larger than that of theprotein data.
• We can easily ﬁnd the maximum peak(maximum match value) from Fig. 5 andFig. 11 for both bibliography and bioinformatics data. While it is of diﬃculty
to discriminate the max peak from Fig. 8
and Fig. 13, because there are many peaks
that have very close tree similarity degrees
with the maximum one. Therefore, themost proper matched subtree sometimes

As more and more data are increasingly represented and exchanged by XML on
the Internet, a method that can eﬃciently
measure the approximate similarity between
XML documents for integrating multiple XMLdata sources becomes more important. We
have proposed LAX (Leaf-clustering based
Approximate XML join algorithm) in previous
work, in which the two XML document trees
are segmented into subtrees representing independent units, and the output is oriented to thepair of documents that has larger tree similarity
degree than the user-deﬁned threshold.
In this paper, we have proposed SLAX by using the maximum match value for integrating
the fragments divided from large XML documents at subtree classes. We have done experiments to evaluate SLAX, comparing with LAX,
by using both real large bibliography and bioinformatics data. Our experimental results indicate that the precision of subtree matching us-

56

IPSJ Transactions on Databases

ing SLAX is twice larger than that using LAX
for bibliography data. And SLAX is useful andvaluable for people to acquire similar proteins
belonging to the same species, organisms, andso on, even if the two XML documents do notcontain exactly the same proteins. Therefore,
We consider that SLAX performs more eﬀectively than LAX for integrating both large bibliography and bioinformatics data at subtree
classes.
Due to the limitation of the main memory,
we plan to do further experiments for evaluating LAX and SLAX by using diﬀerent types oflarge XML data stored RDBs. We are also going to improve the segmentation algorithm forhandling more complex XML data. Besides,
the semantic heterogeneity is to be taken into
account to improve the precision of our algorithms.
Acknowledgments This work was partially supported by the Grant-in-Aid for Scientiﬁc Research of MEXT Japan #16016232,
by the CREST of JST (Japan Science andTechnology Agency), and by the TokyoTech
21COE Program “Framework for Systematization and Application of Large-Scale Knowledge
Resources”.
References
1) ACM SIGMOD Record in XML. Available at
http://www.acm.org/sigmod/record/xml/
2) Arenas, M. and Libkin, L.: A Normal Formfor XML Documents, ACM Transactions on
Database Systems, Vol.29, No.1, pp.195–232(March 2004).
3) Chawathe, S. and Garacia-Molina, H.: Meaningful Change Detection in Structured Data,
Proc. ACM SIGMOD 1997, pp.26–37 (1997).
4) Chawathe, S., Tajaraman, A., Garacia-Molina,
H. and Widom, J.: Change Detection in Hierarchically Structured Information, Proc. ACM
SIGMOD 1996, pp.493–504 (1996).
5) Cobena, G., Abiteboul, S. and Marian, A.:
Detecting Changes in XML Documents, Proc.
ICDE 2002, pp.41–52 (2002).
6) Ethier, K. and Abel, S.: Freely Available
Structures: XML Document Type Deﬁnitions
You Can Use Today, Free Software Magazine,
Issue 6, pp.1–4 (July 2005).
7) Fan, W. and Libkin, L.: On XML Integrity
Constraints in the Presence of DTDs, Proc.
PODS’01, pp.114–125 (2001).
8) Garofalakis, M. and Kumar, A.: Correlating
XML data streams using tree-edit distance embeddings, Proc. PODS’03, pp.143–154 (2003).

June 2006

9) Guha, S., Jagadish, H.V., Koudas, N.,
Srivastava, D. and Yu, T.: Approximate XML
Joins, Proc. ACM SIGMOD 2002, pp.287–298(2002).
10) Guha, S., Koudas, N., Srivastava, D. and
Yu, T.: Index-Based Approximate XML Joins,
Proc. ICDE 2003, pp.708–710 (2003).
11) Liang, W. and Yokota, H.: LAX : An EﬃcientApproximate XML Join Based on Clustered
Leaf Nodes for XML Data Integration, Proc.
BNCOD 2005, Springer LNCS 3567, pp.82–97(July 2005).
12) Marian, A., Abiteboul, S., Cobena, G. andMignet, L.: Change-Centric Management ofVersions in an XML Warehouse, Proc. 27th
VLDB, pp.581–590 (2001).
13) Nierman, A. and Jagadish, H.V.: Evaluating Structural Similarity in XML Documents,
Proc. WebDB 2002, pp.61–66 (2002).
14) Selkow, S.: The Tree-to-tree Editing Problem,
Information Processing Letters, Vol.6, No.6,
pp.184–186 (Dec. 1977).
15) Swiss-Prot. http://www.ebi.ac.uk/swissprot/16) Tai, K.-C.: The Tree-to-Tree Correction Problem, J. ACM, Vol.26, No.3, pp.422–433 (1979).
17) TrEMBL. http://www.ebi.ac.uk/trembl/18) Wang, Y., DeWitt, D.J. and Cai, J.: X-Diﬀ:
An Eﬀective Change Detection Algorithm for
XML Documents, Proc. ICDE 2003, pp.519–
530 (March 2003).
19) World Wide Web Consortium (W3C). The
Document Object Model (DOM). http://www.
w3.org/DOM/
20) XML Version of Swiss-Prot. Avaibable at
ftp://www.ebi.ac.uk/pub/databases/uniprot/
current release/knowledgebase/complete/uniprot sprot.xml.gz
21) XML Version of TrEMBL. Avaibable at
ftp://www.ebi.ac.uk/pub/databases/uniprot/
current release/knowledgebase/complete/uniprot trembl.xml.gz
22) XML Version of DBLP. Available at http://
dblp.uni-trier.de/xml/
23) Zhang, K.: Algorithms for the constrained
editing distance between ordered labeled trees
and related problems, Pattern Recognition,
Vol.28, No.3, pp.463–474 (1995).
24) Zhang, K. and Shasha, D.: Simple Fast Algorithm for the Editing Distance Between Trees
and Related Problems, SIAM Journal of Computing, Vol.18, No.6, pp.1245–1262 (Dec. 1989).
25) Zhang, K. and Shasha, D.: Tree Pattern
Matching, Pattern Matching Algorithms, chapter 11. Oxford University Press (1997).

(Received September 19, 2005)(Accepted March 13, 2006)

Vol. 47

No. SIG 8(TOD 30)

SLAX : An Improved Leaf-Clustering Based Approximate XML(Editor in Charge: Hiroshi Ishikawa,
Masayoshi Aritsugi,
Kaoru Katayama,
Yutaka Kidawara,
Masashi Tsuchida)
Wenxin Liang received his
B.E. and M.E. degrees in biomedical electronic engineering fromXi’an Jiaotong University, China
in 1998 and 2001, respectively.
He is currently a Ph.D. student
at the Department of Computer
Science, Graduate School of Information Science and Engineering, Tokyo Institute of Technology, Japan. His current research interests include XML data integration and management,
XML storage, indexing, labeling and querying
techniques. He is a student member of IPSJ,DBSJ and SIGMOD-J.

57

Haruo Yokota received his
B.E., M.E., and Dr.Eng. degrees
from Tokyo Institute of Technology in 1980, 1982, and 1991,
respectively. He joined FujitsuLtd. in 1982, and was a researcher at the ICOT for theJapanese 5th Generation Computer Projectfrom 1982 to 1986, and at Fujitsu Laboratories
Ltd. from 1986 to 1992. From 1992 to 1998, he
was an associate professor in Japan Advanced
Institute of Science and Technology (JAIST).
He is currently a professor at Global Scientiﬁc Information and Computing Center, andDepartment of Computer Science in Graduate
School of Information Science and Engineering in Tokyo Institute of Technology. His current research interests include general researcharea of data engineering, information storage
systems and dependable computing. He is amember of DBSJ, IPSJ, IEICE, JSAI, IEEE,
IEEE-CS, ACM, ACM-SIGMOD, and ACMSIGARCH.