論文 / 著書情報
Article / Book Information
論題(和文)A Hybrid Approximate XML Subtree Matching MethodUsing Syntactic
Features and Word Semantics

Title(English)

A Hybrid Approximate XML Subtree Matching MethodUsing Syntactic
Features and Word Semantics

著者(和文)

梁文新, 横田治夫

Authors(English)

Wenxin Liang, Haruo Yokota

掲載誌(和文)DEIM Forum 2009論文集

Citation(English)

Proc. of DEIM Forum 2009

Vol, no, pages, ,発行日 / Pub. date2009, 3

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2009 B5-6

A Hybrid Approximate XML Subtree Matching Method
Using Syntactic Features and Word Semantics
Wenxin LIANG†,†† and Haruo YOKOTA††† CREST, Japan Science and Technology Agency
5 Sanbancho, Chiyoda-ku, Tokyo 102–0075, Japan†† Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology
2–12–1 Ookayama, Meguro-ku, Tokyo 152–8552, Japan
E-mail: wxliang@de.cs.titech.ac.jp, yokota@cs.titech.ac.jp
Abstract With the exponential increase in the amount and size of XML data on the Internet, XML subtree matching has become important for many application areas such as change detection, keyword retrieval and knowledge
discoveries over XML documents. In our previous work, we have proposed leaf-clustering based approximate XML
subtree matching methods using syntax information of both the clustered leaf nodes and the corresponding paths.
In this paper, we propose a hybrid subtree matching method, in which subtree matching is determined by using
the word semantics based on WordNet thesaurus in leaf nodes and the syntactic features in the relevant paths. We
also propose a one-pass hash join technique to reduce the additional join cost caused by the extra words expandedby the WordNet. We perform experiments to evaluate performance and matching precision and recall comparing
the hybrid method with the original syntax-based methods. The experimental results indicate that the proposed
hybrid method with one-pass hash join, comparing with the existing path-based SLAX algorithm, can eﬀectively
improve the precision and recall with about only 5% increase of the execution time for the leaf-clustering based
subtree matching.
Key words XML Subtree Matching, Syntactic Feature, Word Semantics, WordNet
Bibliography

1. Introduction
XML has increasingly become a wildly popular standard
and employed as a key technique for representing, exchanging

articletitle...

articleauthor volume title author volume title author volume

and integrating data on the Internet, because it is portable
for representing diﬀerent types of data from multiple sources.

...

articleWWW Black

20

XML Green
Joins

Recently, a large number of data, for example free online en-

7

XML Green
DBs

20

(a)

cyclopedias such as Wikipedia [10], life science data such as
Swiss-Prot [8], and bibliography data such as DBLP [12],References

are disseminated and exchanged on the Internet in the form... articles... articles... article... ... article...

articlesof XML documents. With the exponential increase in theamount and size of XML data, XML subtree matching has
become important for many application areas such as change
detection, keyword retrieval and knowledge discoveries overXML documents. However, XML subtree matching is notan easy task because XML documents from diﬀerent data

title

authors

initPage title

Web author author 7

XML
Joins

Black Whiteauthors initPage

author author 20
Green White(b)sources representing nearly or exactly the same information
may be constructed by diﬀerent structures. Besides, evenFigure 1 Example XML document trees

two XML documents contain the same information, each ofthem may have some extra information that the other does
not do.
［Example 1］ Figure 1 shows an example of two XML doc-

ument trees with diﬀerent DTDs. Although the two XML
document trees have diﬀerent structures, they represent very
similar information. Besides, each document has some infor-mation that the other does not do. For example, volume in
Figure 1 (a); and initPage in Figure 1 (b).
In previous work, we have proposed leaf-clustering basedin the next section.

3. Syntax-based Method

approximate XML subtree matching methods using syntax

In this section, we brieﬂy introduce our previously pro-features of the clustered leaf nodes [6] and the correspond-

posed syntax-based approximate XML subtree matching al-

ing paths [7]. However, focusing on the syntactic features

gorithms using syntax features of the clustered leaf nodes [6]without considering the semantic similarity between words

and the corresponding paths [7], and the indistinguishable

achieves high performance but may degrade matching preci-

matching problems occurred in the syntax-based methods.

sion and recall due to the indistinguishable matching prob-

3. 1 SLAX and Path-based SLAXlem. To solve the indistinguishable matching problem andIn [6], we have proposed the leaf-clustering based XML

achieve reasonable trade-oﬀ between performance and eﬀec-

integration methods, in which the two XML documents totiveness, in this paper we propose a hybrid subtree match-

be joined are ﬁrstly segmented into independent meaning-ing method, in which subtree matching is determined by theful subtrees [4]. Then, the subtree matching is determined

word semantic similarity using WordNet thesaurus [11] of

by SSD (Subtree Similarity Degree) as shown in the follow-

clustered leaf nodes and the syntactic features in the relevant

ing equation [5, 6], where n and nbi denote the number ofpaths. We perform experiments to evaluate the performance

matched leaf nodes and the number of leaf nodes in the baseand matching precision and recall comparing the proposed

subtree tbi , respectively.

hybrid method with the original ones, and the experimental
results indicate that the proposed method can improve thematching precision and recall but takes more execution time.
The rest of the paper is organized as follows. Section 2
brieﬂy introduces the related researches. Section 3 describes
our previously proposed syntax-based methods and the indistinguishable matching problems. In Section 4, we propose the hybrid subtree matching method and discuss the
one-pass join technique. Section 5 describes the experimental evaluation of the proposed method comparing with theoriginal methods. Finally, Section 6 concludes this paper.

2. Related WorkXML subtree matching in RDBs is often applied in thearea of change detection on XML documents [3, 9]. Wang

SSD(tbi , ttj ) =n× 100 (%)
nbi

However, focusing only on the leaf nodes sometimes causes
imprecise matching problems that may degrade the precisionand recall of subtree matching. To solve the imprecise matching problems, in [7] we have proposed path-based SLAX,in which the approximate similarity between two segmented
subtrees is determined based on the Path-based Subtree Sim（ 1）.
ilarity Degree (PSSD) which is deﬁned as follows［Deﬁnition 1］ (Path-based Subtree Similarity Degree(PSSD)) For a pair of matched subtrees TM (i), assume thenumber of matched leaves is K, the full-path based subtree
similarity degree P SSD(tbi , ttj ) is determined by Equation 2,
where P S(i) is the path similarity determined by the numberof matched tags out of the total number of tags in the path.

et al. [9] proposed X-Diﬀ, an eﬀective change detection algorithm based on an unordered tree model. However, X-

K
P SSD(tbi , ttj ) = SSD(tbi , ttj ) ×

Diﬀ cannot be applied to large-scale XML documents because of main memory limitation. Leonardi et al. [3] pro-(1)

P S(i)
K

i=1(2)

3. 2 Indistinguishable Matching Problem

posed schema-conscious approaches which can be applied

Focusing on the syntactic features without considering theto larger XML documents with better performance thansemantic similarity between words achieves high performance

X-Diﬀ. However, the schema-conscious methods need thebut may degrade matching precision and recall due to the

DTDs of the XML documents. In [6], we proposed SLAX,

indistinguishable matching problem. Figure 2 shows an ex-

a syntax-based subtree matching algorithm, which is DTD-

ample of indistinguishable matching occurred in the syntax-

independent and cost-eﬀective with focusing only on the syn-based methods. According to the deﬁnition of SSD, subtree

tax of clustered leaf nodes. However, SLAX sometimes cause

tb1 matches both target subtrees tt1 and tt2 because of theimprecise matching problems that may degrade the eﬀective-

same SSD = 33.33%; that is, the SSD cannot distinguishness of subtree matching. To solve the imprecise matchingwhich pair of subtrees are more semantically relevant only

problems, in [7] we proposed path-based SLAX, which uti-

by using the syntax information. However, since the word

lizes the syntactic features of both the path information and“WWW” is synonymous with the word “Web”, the target

the clustered leaf nodes. However, focusing on the syntactic
feature may degrade matching precision and recall due to theindistinguishable matching problem which will be described（ 1）：Note that the path-based SLAX in this paper only corresponds

to the full-path based method using path information after matchingleaf nodes proposed in [7].

tb1
articletitle author volume
WWW Black 20(a) Base subtree

title

tt1

tt2

articlearticleauthors initPage title

authors

Web authorauthor 7

XML
Joins

Black White

initPageauthor author

20Green White(b) Target subtrees

Figure 2 Example of indistinguishable matching

subtree tt1 is considered to be more semantically relevant tothe base subtree tb1 .

4. Hybrid Subtree Matching Method
4. 1 Hybrid Similarity Degree

Figure 3 Example of join process

WordNet [11] is one of most common used lexical databaseof English. Words are grouped into sets of cognitive syn-the proposed method, the similarity between two subtrees areonyms (synsets), each expressing a distinct concept. Synsets,

determined by the Hybrid Similarity Degree (HSD) which isinterlinked by means of conceptual-semantic and lexical rela-deﬁned as follows.

tions, are the general components for describing word seman-［Deﬁnition 2］ (Hybrid Similarity Degree (HSD)) For atics. We use the synsets returned by Java WordNet API [2]pair of subtrees tb and tt , assume there are m and n words

to determine the semantic similarity between the words in

wb (i) and wt (j) in the leaf nodes of tb and tt is m and n,

the leaf nodes. Given two words w1 and w2 , assume w1 andw2 contain m and n synonyms s1 (i) (1 <=i<= m) and s2 (j)is determined by Equation 3, where P S(k) and K are the

（ 2）
(1 <
= j <
= n) from the synsets of WordNet , the semantic

the hybrid similarity degree between tb and tt , HSD(tb , tt )same as those in Deﬁnition 1.

msimilarity between the two words S(w1 , w2 ) can be determined by the following equation, where σ (0 < σ <= 1) is a

HSD(tb , tt ) =user-deﬁned constant（ 3）.

4. 2 One-pass Join

S(w1 , w2 ) =i=1

M ax{S(wb (i), wt (j))}×
m

K

P S(k)(3)K

k=1

In order to reduce the the additional join cost caused byσ,

if any s1 (i) = s2 (j)0,otherwise

the extra words expanded by the WordNet, we propose aone-pass hash join technique instead of joining each pair ofIn order to solve the indistinguishable matching problem,

base and target subtrees one by one. In the one-pass hash

we propose a hybrid method using both the syntactic featuresjoin, the words and their corresponding synonyms in the leaf

and the word semantics. We ﬁrst use WordNet thesaurus tonodes of each base subtree are stored into a relation table Bi

determine the semantic similarity between leaf nodes, andand those in the leaf nodes of all the target subtrees together

then consider the syntactic features in the relevant paths. In

with their IDs are stored into a relation table T . During thejoin process, once a join base table Bi is built into memory（ 2）：Note that if there are no synonyms returned from WordNet,by a hash function, the join table T containing all the tar-

s1 = w1 and s2 = w2 .

get subtree information can be one-pass probed to achieve（ 3）：For the sake of simplicity, we set σ = 1 in this paper.

high-speed subtree matching.

Table 1 Experimental environment
CPUIntel Core 2 Processor E6850 3.0 GHz

Memory2.0 GB

Hard Disk

Seagate ST336607LC 37GB

OS

Linux 2.6.9

DBMS

PostgreSQL 8.1.3

Java

Sun JDK 1.6.0

Lexical Database

WordNet 2.1

Java APIMIT JWI 2.1.5

Figure 3 illustrates the process of joining base subtree
tb1 with target ones tt1 and tt2 in Figure 2. Firstly, thesynonyms of the words in the leaf nodes of tb1 , tt1 andtt2 are obtained from the synsets of WordNet, and they

Figure 4 Time for subtree matching

are stored together with the original words into two relational tables B1 and T (Table T also stores the subtreeof the two documents are 1504 and 698, and the number of

ID information), respectively.

Next, the two tables arecorrect answer is 142. In order to evaluate the eﬀectivenesshash joined by the condition that B1 .Syn = T.Syn. Fi-of subtree matching, we deﬁne precision and recall as follows.

nally, the matched subtree for the base subtree tb1 can be［Deﬁnition 3］ (Precision) The precision of subtree match-

determined based on Equation (3) using the join resultsing (P) is the percentage of the number of correctly selected

sorted by T.Id.

hit subtrees (Ns ) out of the total number of hit subtrees

In this example, according to Equation(1) and (3), SSD(tb1 , tt1 ) = SSD(tb1 , tt2 ) = 33.3%, while
HSD(tb1 , tt1 ) = 66.7% > HSD(tb1 , tt2 ) = 22.2%.

Thismeans the hybrid method can eﬀectively solve the indistin-(Nh ).
Ns
× 100 (%)
Nh

P=

(4)

guishable matching problem. Besides, since HSD(tb1 , tt1 ) =［Deﬁnition 4］ (Recall) The recall of subtree matching (R)

66.7% > P SSD(tb1 , tt2 ) = SSD(tb1 , tt1 ) = 33.3%, the hy-

is the percentage of the number of correctly selected hit sub-brid method is more eﬀective to evaluate the semantic simi-

trees (Ns ) out of the total number of correct answer(Nc ).

larity between subtrees than the syntax-based methods.

5. Experiments

R=

Ns
× 100 (%)
Nc

(5)

Figure 4 shows the execution time using SLAX, pathbased SLAX (PS for short), the hybrid method using tra-5. 1 Experimental Setup
The experiments were performed under the environment

ditional join (HB normal for short), and the hybrid method

shown in Table 1. We used the XML version of SIGMOD

using one-pass hash join (HB for short). Figure 5 and Fig-

Record [1], named sigmod.xml (482KB, about 20,000 nodes),ure 6 show the precision and recall of subtree matching using

and we segmented the XML version of DBLP [12] into

SLAX, PS and HB methods. According to the experimental

955 fragment documents, named dblp1∼955.xml (300KB

results, we can make the following discussions:each, about 15,000 nodes). We parsed the sigmod.xml anddblp290.xml into relational tables and then segmented them（ 4）

into independent meaningful subtrees .

•Comparing with the PS method, the HB normal

method increases 138.30% of execution time on the average,
because the extra words expanded by the WordNet increases

5. 2 Experimental Results

the number of comparison in the join process. While, theAfter the XML documents are stored and segmented into

hybrid method with one-pass hash join only increases 5.29%

independent meaningful subtrees, we used the original algo-of execution time on the average, which indicates that using

rithm SLAX, the path-based SLAX, and the proposed hybrid

the one-pass hash join can eﬀectively reduce the join cost

method to execute the subtree matching for the sigmod.xml

even the number of the words to be compared becomes muchand dblp290.xml with four diﬀerent matching threshold fromlarger due to the utilization of the WordNet thesaurus.

0.1 to 0.4. The lexical database and Java API used in the•

Comparing with SLAX, the precision increases 19.68%

hybrid method are WordNet 2.1 [11] and MIT Java Wordnet

and 20.37% on the average when using PS and HB, respec-

Interface JWI 2.1.5 [2]. The number of segmented subtrees

tively. Figure 5 shows that HB is superior to PS when thematching threshold is greater than 0.2. However, PS achieves（ 4）：Refer to Reference [4] for the detailed data schema and subtree

slightly better precision when the matching threshold is lesssegmentation algorithms.

than 0.2, because using the word semantics in HB generates

word semantics in leaf nodes and the syntactic features in
the relevant paths, to solve the indistinguishable matchingproblem in syntax-based approximate XML subtree matching algorithms. We also proposed a one-pass hash join technique to reduce the additional join cost caused by the extra
words expanded by the WordNet.
We performed experiments to evaluate the trade-oﬀ between performance and matching precision and recall comparing the proposed hybrid method with the original ones,
and the experimental results indicate that the proposed hybrid method with one-pass hash join, comparing with thepath-based SLAX algorithm, can eﬀectively improve the preFigure 5 Precision of subtree matchingcision and recall with about only 5% increase of the execution
time for the leaf-clustering based subtree matching, particularly when the matching threshold becomes larger.

Acknowledgment
This work was partially supported by CREST of JST(Japan Science and Technology Agency), and by the Grantin-Aid for Scientiﬁc Research of MEXT Japan #19024028.

References

Figure 6 Recall of subtree matching（ 5）larger number of hit subtrees than PS does.

•

Comparing with SLAX, the recall increases 2.09%

and 4.93% when using PS and HB, respectively. The hybrid method achieves better recall than the SLAX and PS
methods, particularly when the matching threshold becomeslarger than 0.2.
From the above results, we can learn that the proposed
hybrid method with one-pass hash join, comparing with thepath-based SLAX algorithm, can eﬀectively improve the precision and recall with about only 5% increase of the execution
time for the leaf-clustering based subtree matching, particularly when the matching threshold becomes larger.

6. Conclusions
In this paper, we proposed a hybrid XML subtree matching
method, in which subtree matching is determined by using（ 5）：Another reason is that the XML documents used in our experi-ments contain many computer terms, “XML” for example, that are notincluded in the WordNet database. Acturally, in the future we plan
to conduct further evaluation on the eﬀectiveness of using WordNetby more experiments using multiple kinds of XML data.

[1] ACM SIGMOD Record in XML.
Available at
http://www.acm.org/sigmod/record/xml/.
[2] MIT Java WordNet Interface.
Available at
http://projects.csail.mit.edu/jwi/.
[3] Erwin Leonardi and Sourav S. Bhowmick. Detecting
Changes on Unordered XML Documents Using Relational Databases: A Schema-conscious Approach. In
Proc. of CIKM, pages 509–516, 2005.
[4] W. Liang, X. Ouyang, and H. Yokota. An XML Subtree Segmentation Method Based on Syntactic Segmentation Rate. In Proc. of ADSS, pages 551–558,
2007.
[5] W. Liang and H. Yokota. LAX : An Eﬃcient Approximate XML Join Based on Clustered Leaf Nodes for
XML Data Integration. In Proc. of BNCOD, pages
82–97, 2005.
[6] W. Liang and H. Yokota. SLAX : An Improved LeafClustering Based Approximate XML Join Algorithm
for Integrating XML Data at Subtree Classes. IPSJ
Trans. on Databases, 47(SIG8(TOD30)):47–57, 2006.
[7] Wenxin Liang and Haruo Yokota. Exploiting Path Information for Syntax-based XML Subtree Matching in
RDBs. In Proc. of WAIM, pages 105–112, 2008.
[8] Swiss-Prot. http://www.ebi.ac.uk/swissprot/.
[9] Y. Wang, D. J. DeWitt, and J. Cai. X-Diﬀ: An Effective Change Detection Algorithm for XML Documents. In Proc. of ICDE, pages 519–530, Match 2003.
[10] Free Encyclopedia: Wikipedia. http://wikipedia.org/.
[11] WordNet. http://wordnetweb.princeton.edu/.
[12] XML Version of DBLP. Available at http://dblp.unitrier.de/xml/.