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

A Path-sequence Based Method for Solving the One-to-multiple
Matching Problem in Leaf-Clustering Based Approximate XML Join
Algorithms

著者(和文)

梁 文新, 横田 治夫

Authors(English)

Wenxin LIANG, Haruo YOKOTA

掲載誌(和文)DEWS2006 論文集

Citation(English)

Proc. of DEWS2006

Vol, no, pages

Vol. , No. , pp. 4A-i10

発行日 / Pub. date

2006, 3

URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2006 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2006 4A-i10

A Path-sequence Based Method
for Solving the One-to-multiple Matching Problem
in Leaf-Clustering Based Approximate XML Join Algorithms
Wenxin LIANG† and Haruo YOKOTA††,†† Department of Computer Science, Graduate School of Information Science and Engineering,Tokyo Institute of Technology
2–12–1 Ookayama, Meguro-ku, Tokyo 152–8552, Japan†† Global Scientific Information and Computing Center, Tokyo Institute of Technology
2–12–1 Ookayama, Meguro-ku, Tokyo 152–8550, Japan
Abstract In previous work, we have proposed approximate XML join algorithms based on the clustered leaf
nodes for measuring the approximate similarity between XML documents and integrating them at the subtree
classes. However, in a join loop, one base subtree may infrequently happen to be matched with multiple target
ones. In this paper, we propose a path-sequence based method to solve the one-to-multiple matching problem inleaf-clustering based approximate XML join algorithms. In our method, each path sequence from the top node
to the matched leaf in the base and target subtree is extracted, and the most similar target subtree for the baseone is determined by the path-sequence based subtree similarity degree. We conduct experiments to evaluate ourmethod by using both real bibliography and bioinformatics XML documents. The experimental results show that
our method can effectively solve the one-to-multiple matching problem for both bibliography and bioinformatics
XML data, and hence improve the precision of the leaf-clustering based approximate XML join algorithms.
Key words XML, Semi-structured data, Information Integrationturally different, they represent very similar information. In

1. Introduction

addition, both of the two document trees have some infor-

XML has become a widely important standard for data
representation and exchange on the World Wide Web. Re-

mation what the other does not do. For example, volume in
Figure 1 (a); and initPage in Figure 1 (b).

cently, a large number of data, for example bioinformatics

In previous work [11, 12], we have proposed leaf-clustering

data such as TrEMBL [18] and Swiss-Prot [16], and bibliogra-

based approximate XML join algorithms for measuring thephy data such as ACM SIGMOD Record [1] and DBLP [23],approximate similarity between XML documents and inte-

are published and shared by XML on the Internet. How-grating them at subtree classes. However, in a join loop,

ever, XML documents from different data sources may con-a one-to-multiple matching problem might occasionally oc-

vey nearly or exactly the same information but may be dif-

cur for a base subtree; that is one base subtree may hap-ferent on structures. Besides, even the two XML documents

pen to be matched with multiple target ones. Although therepresent the same information, each of them may have some

one-to-multiple matching problem occurs very infrequently,

extra information what the other does not do.

it still affects the precision of the leaf-clustering based ap-

A well formed XML document can be parsed into an ordered labeled tree [20].

The Document Type Descriptor(DTD) is regarded as an effective tool for detecting the struc-proximate XML join algorithm. Therefore, how to select themost proper matched target subtree for the base one in thecase of one-to-multiple matching becomes a critical issue.

tural information from XML documents [2, 6, 10, 14]. How-In this paper, we propose a path-sequence based method

ever, even if XML documents have the same DTDs, they may

to solve the one-to-multiple matching problem. In the pro-not be constructed by identical tree structures because of

posed method, each path sequence from the top node to thethe repeating and optional elements and attributes [8, 9, 14].

matched leaf in the base and target subtree is extracted, andFigure 1 shows an example of two XML document trees withthe most similar target subtree for the base one is determineddifferent DTDs. Although the two document trees are struc-by the path-sequence based subtree similarity degree. We

tb1
Bibliography

article...

articletitle

author

XML

Max

...

articlebook

volume title

authorvolumetitle

editoreditor

XML
Joins

Mary

10

XML DBs Max

Smith

20

title

authorvolume

XML

Max

20



(a) Base subtree
(a)
tt1

tt2

articlearticleReferences
articlesarticle... ...

article

title

authors

initPagetitle

authors

initPageXMLauthor author

145

XML
Joins

author author

20





Max



Mary

Jane

title

XML

Max



one-to-multiple matching and the precision of matching forthe proposed algorithm comparing with those for the originalone. The experimental results show that the path-sequencebased method can effectively decrease the occurrence rate of
one-to-multiple matching for both bibliography and bioinformatics XML data, and hence improve the precision of theleaf-clustering based approximate XML join algorithms.
The remainder of the paper is organized as follows. Section 2. states the problem of one-to-multiple matching. In
Section 3., we propose the path-sequence based method. Section 4. conducts experiments using both real bibliography
and bioinformatics data and discusses the experimental results. In Section 5., we briefly introduce the related workand our previous proposed algorithms. Finally, Section 6.
concludes this paper.

2. One-to-multiple Matching Problem
In the leaf-clustering based approximate XML join algorithms [11, 12], the two XML documents to be joined aresegmented into subtrees representing independent informa（ 注 1）
tion units. Then, the subtree matching is determined by

the subtree similarity degree which is defined as follows.
［ Definition 1 ］ (Subtree Similarity Degree (SSD)) For

a base subtree tbi and a target one ttj , the subtree similarity
degree between them, SSD(tbi , ttj ) is defined by Equation（ 注 1）：The details of the segmentation algorithm are available in [11].



authors

title

initPage

XML author author
Joins

Jane

Mary

20

Max

(b) Matched target subtrees

Figure 1 Example XML document trees

formatics XML documents to compare the occurrence rate of

initPageauthor author 145
Max

(b)

conduct experiments using both real bibliography and bioin-

authors

Figure 2 One-to-multiple matching problem(1) as the percentage of the number of matched leaf nodes(the pair of leaf nodes that has the same PCDATA value) outof the number of leaf nodes in the base subtree tbi , where n
and nbi denote the number of matched leaf nodes and thenumber of leaf nodes in the base subtree tbi .
SSD(tbi , ttj ) =n× 100 (%)
nbi

(1)

However, for a base subtree, a one-to-multiple matchingproblem may infrequently occur as stated as follows.
［ Problem 1 ］ (One-to-multiple Matching) For a basesubtree tbi , if there are two or more target subtrees ttj having
the same subtree similarity degree with tbi , the base subtree
tbi will be matched with those target subtrees in one joinloop.
［ Example 1 ］ Figure 2 shows a base subtree tb1 and two tar-

get ones tt1 and tt2 segmented from the document trees in
Figure 1. The matched leaves for (tb1 , tt1 ) are XML and Max,
while those for (tb1 , tt2 ) are Max and 20. However, according to Definition 1, SSD(tb1 , tt1 ) = SSD(tb1 , tt2 ) = 66.7%.
That means both tt1 and tt2 will be matched with tb1 becauseof the same subtree similarity degree.
Therefore, how to select the most similar one from themultiple matched target subtrees becomes a critical issue.

3. Path-sequence Based Method
In Section 2., we have discussed the one-to-multiple matching problem in the leaf-clustering based approximate XML
join algorithms. In this section, we propose a path-sequencebased method to solve this one-to-multiple matching problem.

tb1

tt1

articlearticle3. 1 Key Definition
title

authorvolume

XML

Max

20



Let Tb and Tt be two XML document trees (b denotes base,and t denotes target). Assume Tb and Tt are segmented into
kb and kt subtrees tbi (1 <=i<
= kb ) and ttj (1 <=j<
= kt ), respec-XMLauthor author 145
Max

tively. Before we treat of the path-sequence based method,
we present the following key definitions.

initPageauthors

title

Jane

(a) Path sequence for (tb1 , tt1 )［ Definition 2 ］ (Matched Leaf ) For each pair of base sub-

tb1

tt2

articlearticletree tbi and target one ttj , the matched leaf LM (i) is the pairof leaf nodes lbi and ltj that has the same PCDATA value.
［ Definition 3 ］ (Matched Subtree) In the ith join loop,

title

authorvolume

XML

Max

20





authors

title

initPagethe matched subtree TM (i) is the pair of subtrees tbi and ttj
that has the maximum subtree similarity degree.
［ Definition 4 ］ (Path Sequence) For a pair of matched

XML author author
Joins
Mary

subtrees TM (i), a path sequence P (i) is defined as the path

20

Max

(b) Path sequence for (tb1 , tt2 )from the root node to the matched leaf LM (i) in the base or

Figure 3 Path sequence for the base and target subtree

target subtree.
For the matched subtrees (tb1 , tt1 ) and (tb1 , tt2 ) in Figure 2, the path sequences for them are shown by the dashedas shown by the dashed lines in Figure 3 (a).

lines in Figure 3. The similarity between the path sequences

ing to the Equation (2), the path-sequence similarity de-for each pair of matched leaves is determined based on thegree between Pb (1) and Pt (1), P SD(1) =path-sequence similarity degree.

100%.

3
3

Accord-× 100% =Similarly, the path-sequence similarity degree be-［ Definition 5 ］ (Path-sequence Similarity Degree (PSD)) tween Pb (2) = {“article”, “author”, “M ax”} and Pt (2) ={“article”, “authors”, “author”, “M ax”}, P SD(2) is also
For a pair of matched leaves L (i), the path-sequence simM

ilarity degree P SD(i) is defined by the following equation,

100%. Therefore, the path-sequence based subtree similarity

where N denotes the number of nodes in the base path se-degree for tb1 and tt1 , P SSD(tb1 , tt1 ) = 100%+100%
×66.7% =2

quence that have the same labels (non-leaf nodes) or values

66.7%. For the second matched subtree TM (2), Figure 3 (b)(leaf nodes) with those in the target path sequence, and Nbi

shows the path sequences for tb1 and tt2 . We can similarly fig-

denotes the total number of nodes in the base path sequence.

ure out the path-sequence based subtree similarity degree forN
P SD(i) =× 100 (%)
Nbi

(2)

Then, the similarity between the matched subtrees canbe determined by calculating the path-sequence based subtree

tb1 and tt2 , P SSD(tb1 , tt2 ) = 100%+66.7%
× 66.7% = 55.6%.
2
Because P SSD(tb1 , tt1 ) = 66.7% > P SSD(tb1 , tt2 ) = 55.6%,
the matched target subtree tt1 is considered to be more similar with the base subtree tb1 .
When one base subtree is matched with multiple target

similarity degree.
［ Definition 6 ］ (Path-sequence based Subtree Simi-

subtrees, the most proper matched subtree pair can be de-larity Degree (PSSD)) For a pair of matched subtrees

termined based on the path-sequence similarity degree. The

TM (i), assume the number of matched leaves is K, the path-details of the path-sequence based algorithm is illustrated bysequence based subtree similarity degree P SSD(tbi , ttj ) is

Algorithm PathSeq shown in Figure 4.

determined by the following equation.

4. ExperimentPK
P SSD(tbi , ttj ) =P SD(i)i=1
× SSD(tbi , ttj )K(3)

3. 2 Algorithm PathSeq

In this section, we conduct experiments using both bibliography and bioinformatics data to observe how often the［ Example 2 ］ For the base subtree tb1 and target ones tt1

one-to-multiple matching occurs in the original algorithms

and tt2 in Figure 2. The matched subtree pairs are TM (1) =and how effectively the proposed method solves this prob-(tb1 , tt1 ), and TM (2) = (tb1 , tt2 ). For the first matched sub-lem.

tree TM (1), the matched leaves are LM (1) = “XM L” and4. 1 Experimental Environment

LM (2) = “M ax”. Then, the base path sequence for LM (1),

Our experiments have been done under the environment

Pb (1) = {“article”, “title”, “XM L”}, and the target path sequence path for LM (1), Pt (1) = {“article”, “title”, “XM L”}

shown in Table 1.

one-to-multiple matching, we define precision of matching as

Algorithm PathSeq {Input: pairs of matched subtrees (tbi , ttj )follows.

Output: pair of matched subtrees［ Definition 8 ］ (Precision of Matching) The precision of

max = 0;matching (P) is the percentage of the number of correctly

output = null;

selected subtrees (Nc ) out of the number of total multiple

for each pair of matched subtrees (tbi , ttj ) {matched subtrees (Nm ) using the original algorithm as thefor each pair of matched leaves LM (i) {following equation.

calculate P SD(i);}P=

calculate P SSD(tbi , ttj );if (P SSD(tbi , ttj ) >= M ax) {Nc
× 100 (%)Nm

(5)

Table 3 and Table 5 show the occurrence rate of one-to-max = P SSD(tbi , ttj );multiple matching for the six pairs of bibliography and bioin-

output = (tbi , ttj );formatics documents, where NO and NP denote the num-}

ber of multiple matched subtrees in the base document by}

the original algorithms and by the path-sequence based algo-

return output;

rithm, respectively, and RO and RP indicate the occurrence}

rate of one-to-multiple matching in the original algorithms

Figure 4 Path-sequence based Algorithm

and in the path-sequence based algorithm, respectively. Ta-

Table 1 Experimental Environment
CPUIntel Pentium 4 (2.80GHz)

Memory1.0 GBOS

MS Windows XP Professionalble 4 and Table 6 show the precision of matching for the six
pairs of bibliography and bioinformatics documents, where
NcO and NcP denote the number of correctly matched subtrees using the original algorithms and the path-sequence

Programming
Environment

based algorithm, respectively, and PO and PP indicate the

Sun JDK 1.4.2

precision of matching for the original algorithms and thepath-sequence based algorithm, respectively.

4. 2 Data Used
For bibliography data, we use six fragment documents of

Figure 5 and Figure 7 indicate the differences of the oc-

DBLP.xml [23], named dblp1-6.xml, 600KB per document

currence rates of one-to-multiple matching in the original(about 30,000 nodes), as the base documents, and the XML

algorithms and the path-sequence based algorithm for theversion of SIGMOD Record [1], named sigmod.xml, 482KB

six pairs of bibliography and bioinformatics documents, re-(about 20,000 nodes), as the target one. And for bioinformat-

spectively. Figure 6 and Figure 8 show the differences of

ics data, we use six fragment documents of uniprot sprot.xml

the precision of matching for the original algorithms and the[21], named sprot1-6.xml, 3MB per document (about 30,000

path-sequence based algorithm for the six pairs of bibliogra-

nodes), as the base documents, and a fragment document

phy and bioinformatics documents, respectively.

of uniprot trembl.xml [22], named trembl.xml, 1MB (about［ Example 3 ］ Figure 9 shows the real source codes of a base

25,000 nodes), as the target one. The number of segmented

subtree tb1 in dblp1.xml and two matched target subtrees

subtrees in each document is shown in Table 2.

tt1 and tt2 for it in sigmod.xml.

According to Equation

4. 3 Result and Discussion(1), the subtree similarity degrees for the both matched

We join the six pairs of bibliography and bioinformatics

subtrees, SSD(tb1 , tt1 ) = SSD(tb1 , tt2 ) =2
10× 100% =XML documents and observe the occurrence rate of one-to-20%.

multiple matching in the original algorithms and the pro-quences in tb1 are Pb (1) ={ “article”, “author”, “C. J.

posed algorithm, respectively. The occurrence rate of one-Date”} and Pb (2) = {“article”, “number”, “1”}, and the

to-multiple matching is defined as follows.

corresponding path sequences in tt1 are Pt (1) ={“article”,［ Definition 7 ］ (Occurrence Rate of One-to-multiple“authors”,

matching) The occurrence rate of one-to-multiple match-{“article”, “initP age”, “1”}. Therefore, the path-sequenceing (R) is the percentage of the number of multiple matchedsimilarity degrees for (Pb (1), Pt (1)) and (Pb (2), Pt (2)),

subtrees (N ) out of the number of total subtrees in the base

P SD(1) =N× 100 (%)
Nb

“author”,

3
3

(4)

“C. J. Date”} and Pt (2)× 100% = 100%, and P SD(2) =100% = 66.7%.

document (Nb ) as the following equation.
R=

For the matched subtrees (tb1 , tt1 ), the path se-

=

2
3

×

According to Equation (3), the path-sequence based subtree similarity degrees for tb1 and tt1 ,P SSD(tb1 , tt1 ) = 100%+66.7%
× 20% = 16.7%. Similarly,
2

In order to observe how effectively the path-sequence im-

the path-sequence based subtree similarity degree for tb1 andproves the precision of subtree matching in the situation of

tt2 , P SSD(tb1 , tt2 ) = 100%+100%
× 20% = 20%. Because2Table 2 Number of subtrees in each document
NN

sigmod

dblp1

dblp2

dblp3

dblp4

dblp5

dblp6

1504

1599

1451

1538

1584

1680

1474

tremblsprot1

sprot2sprot3sprot4sprot5sprot6

396

335

337

324

309

350

360

Table 3 Occurrence rate of one-to-multiple matching for bibliography data

P SSD(tb1 , tt1 ) = 16.7% < P SSD(tb1 , tt2 ) = 20%, the pathsequence based method will select tt2 as the final matchedtarget subtree which is exactly the same article as the base

NO

NP

RO

dblp1 × sigmod

1530.94% 0.19%

dblp2 × sigmod

900.62% 0.00%

dblp3 × sigmod

800.52% 0.00%

dblp4 × sigmod

1641.01% 0.25%

dblp5 × sigmod

28

51.67% 0.30%

dblp6 × sigmod

000.00% 0.00%

Mean value

subtree tb1 as shown in Figure 9.
According to the experimental results, we can draw theRP

12.67 2.00 0.79% 0.12%

Table 4 Precision of matching for bibliography data

following conclusions:

NcO

NcP

PO

PP

For both bibliography and bioinformatics data, thedblp1 × sigmod

6

13

40%

86.70%

mean occurrence rates of one-to-multiple matching are less

dblp2 × sigmod

4944.40%

100%

dblp3 × sigmod

3

8

37.5%

100%

dblp4 × sigmod

51331.25% 81.25%

dblp5 × sigmod

72525.00% 89.30%

dblp6 × sigmod--

Mean value

5.0

13.6

•

than 2% in the original algorithms. Namely, the one-tomultiple matching in the original algorithms does not frequently occur. However, even for the infrequent occurrenceof one-to-multiple matching, it can still reduce the overall--

36.00% 91.00%

precision of the leaf-clustering based approximate XML join
algorithms.
•

Table 5 Occurrence rate of one-to-multiple matching for bioinformatics data

The mean occurrence rate of one-to-multiple matching

NO

NP

RO

sprot1 × trembl

101

2.99% 0.30%

sprot2 × trembl

72

2.08% 0.59%

sprot3 × trembl

50

1.54% 0.00%

for bioinformatics data because each subtree of the bioinfor-

sprot4 × trembl

000.00% 0.00%

matics document contains much more information than thatsprot5 × trembl

60

1.71% 0.00%

of bibliography document does.

sprot6 × trembl

123

3.33% 0.83%

in the original algorithm for bioinformatics data is 1.94%.
It is larger than that for bibliography data, 0.79%. Thatmeans the one-to-multiple matching occurs more frequently•

Mean value

For bibliography documents, the mean occurrence rate

RP6.67 1.00 1.94% 0.29%

of one-to-multiple matching decreases from 0.79% to 0.12%
Table 6 Precision of matching for bioinformatics data

by using the path-sequence based method. And for bioinformatics documents, the mean occurrence rate of one-tomultiple matching reduces from 1.94% to 0.29%. Thus, the

NcO

NcP

sprot1 × trembl

4940.00% 90.00%

POPP

sprot2 × trembl

2

528.57% 71.43%

mean occurrence rate of one-to-multiple matching using the

sprot3 × trembl

1

5

20.00%

path-sequence based method is less than one sixth of that us-

sprot4 × trembl

-

-

-

-

ing the original algorithms for both bibliography and bioin-

sprot5 × trembl

2

633.33%

100%

formatics documents.

sprot6 × trembl

3

925.00% 75.00%

Mean value

2.4

6.8

29.38% 87.29%•

The mean precision of matching increases from 36.00%

100%

to 91.00% by using the path-sequence based method for bibliography documents, and it increases from 29.83% to 87.29%

There is considerable previous work on measuring the edit

for bioinformatics documents. Therefore, the mean preci-

distance between ordered labeled trees [3–5, 7, 13, 15, 17, 19,sion of matching for the path-sequence based method be-

24–26]. The edit distance between two ordered labeled trees

comes about three times larger than that for the originalis defined as the minimum cost edit operations (insertions,algorithms.

deletions and changes) required to transform one tree to an-

5. Related and Previous Workother [26]. The tree edit distance is recognized as an traditional metric for measuring the structural similarity between

A well formed XML document can be parsed into an or-

XML documents [7, 8, 14]. However, the computational costdered labeled tree [20]. The tree structure is constructed byof the tree edit distance is extremely expensive; in the worst

the nesting of its elements, and the node labels record thecase, it is an O(n4 ) operation for the XML documents of size

contents of the elements by element tags, attribute names,n.

attribute values and PCDATA values.

In order to avoid the expensive tree edit distance operation

Precision of matching

Occurrence rate of oneto-multiple matching

2.00%
1.50%
1.00%
0.50%
0.00%





1



2
3
4
5
6
Bibliography document pair

Original algorithm

100%
80%


60%
40%
20%
0%

mean
value

Path-sequence based algorithm




1



2
3
5
6
Bioinformatics document pair

Original algorithm

mean
value

Path-sequence based algorithm

Figure 5 Occurrence rate of one-to-multiple matching for bibliFigure 8 Precision of matching matching for bioinformatics doc-

ography documents

Precision of matchinguments

100%



80%
60%
40%
20%
0%





1

2
3
4
5
Bibliography document pair

mean
value

(a) Base subtree tb1 in dblp1.xml

Original algorithm Path-sequence based algorithm

Occurrence rate of oneto-multiple matching

Figure 6 Precision of matching for bibliography documents

3.50%
3.00%
2.50%
2.00%
1.50%
1.00%
0.50%
0.00%



<article mdate="2002-01-03" key="journals/sigmod/Date82"><ee>db/journals/sigmod/Date82.html</ee><author>C. J. Date</author><title>A Formal Definition of the relational Model.</title><pages>18-29</pages><cdrom>sigmodR/13-1/P018.pdf</cdrom><year>1982</year><volume>13</volume><journal>SIGMOD Record</journal><number>1</number><url>db/journals/sigmod/sigmod13.html#Date82</url></article><article><title>Some Principles of Good Language Design (withespecial reference to the design of database languages).</title><initPage>1</initPage><endPage>7</endPage><authors><author position="00">C. J. Date</author></authors></article>(b) Matched target subtree tt1 in sigmod.xml




1
2
3
4
5
6
Bioinformatics document pair

mean
value

<article><title>A Formal Definition of the relational Model.</title><initPage>18</initPage><endPage>29</endPage><authors><author position="00">C. J. Date</author></authors></article>

Original algorithm Path-sequence based algorithm(c) Matched target subtree tt2 in sigmod.xml

Figure 7 Occurrence rate of one-to-multiple matching for bioinformatics documents

as much as possible, S. Guha, et al. proposed the lower andupper bound as inexpensive filters for the tree edit distance
operation [8]. However, when the upper bound is greaterthan the threshold distance τ and at the same time the lower
bound is less than τ , the tree edit distance still can not be
avoided.
In [11, 12], we have proposed leaf-clustering based approximate XML join algorithms for measuring the approximate
similarity between XML documents and integrating them at
subtree classes. Our previous experimental results show that

Figure 9 Source codes for a base subtree and two matched target
subtrees from dblp1.xml × sigmod.xml

the leaf-clustering based approximate XML join algorithms
perform more efficiently for computing the approximate similarity between XML documents than the tree edit distancedoes. In the worst case, they are O(n2 ) operations for the
XML documents of size n. Besides, the previous proposed
algorithms can effectively integrate the XML documents containing similar information from different sources at subtree
classes.

6. Conclusion
In previous work, we have proposed leaf-clustering based[4]

approximate XML join algorithms for measuring the approximate similarity between XML documents and integratingthem at subtree classes. However, in a join loop, a oneto-multiple matching problem may occasionally occur fora base subtree. Namely, one base subtree may happen to

[5]

[6]

be matched with multiple target ones. Even the infrequent
one-to-multiple matching may degrade the precision of the[7]

subtree matching. Therefore, an effective method for determining the most similar target subtree for the base one[8]

to overcome the one-to-multiple problem becomes important
for leaf-clustering based approximate XML join algorithms.

[9]

In this paper, we have proposed a path-sequence based
method to solve the one-to-multiple matching problem in[10]

leaf-clustering based approximate XML join algorithms. In
our method, each path sequence from the top node to thematched leaf in the base and target subtree is extracted, and[11]

the most similar target subtree for the base one is determined by the path-sequence based subtree similarity degree.
We have done experiments using both real bibliography and[12]bioinformatics XML documents to compare the occurrence
rate of one-to-multiple matching and the precision of matching for the proposed algorithm comparing with those for the[13]

original one. The experimental results show that the mean
occurrence rate of one-to-multiple matching using the path-[14]

sequence based method is less than one sixth of that using theoriginal algorithms, and the mean precision of matching forthe path-sequence based method becomes about three times
larger than that for the original algorithms. Therefore, we
consider that our method can effectively decrease the occurrence rate of one-to-multiple matching for both bibliography
and bioinformatics data, and hence improve the precise of

[15]
[16]
[17]
[18]
[19]

the leaf-clustering based approximate XML join algorithms.
[20]

Acknowledgement
We thank Dr. Toshiyuki Amagasa from Tsukuba Univer-[21]

sity for his helpful comments. This work is partially supported by the Grant-in-Aid for Scientific Research of MEXT

[22]

Japan #16016232, by CREST of JST (Japan Science andTechnology Agency), and by the TokyoTech 21COE Program “Framework for Systematization and Application of
Large-Scale Knowledge Resources”.
文

[23]
[24]

献

[1] ACM SIGMOD Record in XML. Available at
http://www.acm.org/sigmod/record/xml/[2] M. Arenas and L. Libkin. A Normal Form for XML Documents. ACM Transactions on Database Systems, 29(1):195232, March 2004.
[3] S. Chawathe and H. Garacia-Molina. Meaningful Change

[25]

[26]

Detection in Structured Data. In Proc. of ACM SIGMOD
1997, pages 26-37, 1997.
S. Chawathe, A. Tajaraman, H. Garacia-Molina and J.
Widom. Change Detection in Hierarchically Structured Information. In Proc. of ACM SIGMOD 1996, pages 493-504,
1996.
G. Cobena, S. Abiteboul and A. Marian. Detecting Changes
in XML Documents. In Proc. of ICDE 2002, pages 41-52,
2002.
W. Fan and L. Libkin. On XML Integrity Constraints in
the Presence of DTDs. In Proc. of PODS’01, pages 114125, 2001.
M. Garofalakis and A. Kumar. Correlating XML data
streams using tree-edit distance embeddings. In Proc of
PODS’03, page 143-154, 2003.
S. Guha, H.V. Jagadish, N. Koudas, D. Srivastava and T.
Yu. Approximate XML Joins. In Proc. of ACM SIGMOD
2002, pages 287-298, 2002.
S. Guha, N. Koudas, D. Srivastava and T. Yu. Index-BasedApproximate XML Joins. In Proc. of ICDE 2003, pages
708-710, 2003.
K. Ethier and S. Abel, Freely Available Structures: XML
Document Type Definitions You Can Use Today, Free Software Magazine, Issue 6, pages 1-4, July 2005.
W. Liang and H. Yokota. LAX : An Efficient Approximate
XML Join Based on Clustered Leaf Nodes for XML Data Integration. In Proc. of BNCOD 2005, LNCS 3567, Springer,
pages 82-97, July 2005.
W. Liang and H. Yokota. SLAX : An Improved LeafClustering Based Approximate XML Join Algorithm for
XML Data Integration at Subtree Classes. In Proc. of DBWeb 2005, IPSJ Symposium Series, 2005(16):41-48, November 2005.
A. Marian, S. Abiteboul, G. Cobena and L. Mignet. ChangeCentric Management of Versions in an XML Warehouse. In
Proc. of 27th VLDB, pages 581-590, 2001.
A. Nierman and H. V. Jagadish. Evaluating Structural Similarity in XML Documents. In Proc. of WebDB 2002, pages
61-66, 2002.
S. Selkow. The Tree-to-tree Editing Problem. Information
Processing Letters, 6(6):184-186, December 1977.
Swiss-Prot. http://www.ebi.ac.uk/swissprot/.
Kuo-Chung Tai. The Tree-to-Tree Correction Problem.
Journal of the ACM, 26(3): 422-433, 1979.
TrEMBL. http://www.ebi.ac.uk/trembl/.
Y. Wang, D. J. DeWitt and J. Cai. X-Diff: An Effective
Change Detection Algorithm for XML Documents. In Proc.
of ICDE 2003, pages 519-530, March 2003.
World Wide Web Consortium (W3C). The Document Object Model (DOM). http://www.w3.org/DOM/.
XML Version of Swiss-Prot. Avaibable at
ftp://www.ebi.ac.uk/pub/databases/uniprot/current
release/knowledgebase/complete/uniprot sprot.xml.gz
XML Version of TrEMBL. Avaibable at
ftp://www.ebi.ac.uk/pub/databases/uniprot/current
release/knowledgebase/complete/uniprot trembl.xml.gz
XML Version of DBLP. Available at http://dblp.unitrier.de/xml/.
K. Zhang. Algorithms for the constrained editing distance
between ordered labeled trees and related problems. Pattern
Recognition, 28(3):463-474, 1995.
K. Zhang and D. Shasha. Simple Fast Algorithm for the
Editing Distance Between Trees and Related Problems.
SIAM Journal of Computing, 18(6):1245-1262, December
1989.
K. Zhang and D. Shasha. Tree Pattern Matching. Pattern
Matching Algorithms, chapter 11. Oxford University Press,
1997.