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

XML Documents searching combining structure and keywords
similarities

著者(和文)

渡辺 陽介, 横田 治夫

Authors(English)

Apichaya Auvattanasombat, Yousuke Watanabe, Haruo Yokota

出典(和文)

情報処理学会研究報告, Vol. 2013-DBS-157, No. 14, pp. 1-6

Citation(English)

IPSJ SIG Technical Reports, Vol. 2013-DBS-157, No. 14, pp. 1-6

発行日 / Pub. date2013, 7

権利情報 / 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.2013-DBS-157 No.14
Vol.2013-IFAT-111 No.14
2013/7/23

IPSJ SIG Technical Report

XML Documents Searching Combining Structure andKeywords Similarities
Apichaya Auvattanasombat1,2,a)Yousuke Watanabe1,b)Haruo Yokota1,c)

Abstract: In recent years, XML has been increasingly become an emerging standard and widely used in many applications. For example, office documents which are more and more popular used at this time, are also stored in multiple
parts of XML archive formats. It is known that the structure and content of XML files play different roles dependingon kind of documents. Therefore, achievement similarity search of an XML file should base on both structure andcontent. In previous work, LAX+ is an algorithm for reckoning a similarity value from structure and contents of XML
files in the office documents. However, since LAX+ used exactly matching method between corresponding leaves,
similar words in the leaf-nodes are considered as different. To solve the problem, we propose to combine LAX+ withkeyword similarity in leaf-nodes. We use docx, xlsx and pptx file formats as experimental data set. The evaluationshows that our approach can be used to improve the precision and recall.
Keywords: XML Similarity, OOXML, Keyword Similarity, Document Search

1. Introduction
Over the past years, the Extensible Markup Language (XML)has been established as a major means for information management. It has been broadly utilized for complex data representation and many applications, because it can represent different
kinds of data from multiple sources. Therefore, more and more
information are published and exchanged by XML. Demands forsearching XML documents become increasing and complicated.
Moreover, Microsoft Office Document format [1] is also basedon XML file format and the amount of office document is still
increasing on the Internet. As an application of XML searching, our research group has been developing a system named SOS(Structure-based Office document Search) [12] which finds office
documents being similar to a given query document. To provide
relevant search results to users, we need a method to calculate
similarity of XML trees precisely.
Since, the content and the structure of XML trees play different
roles and importance depending on kind and purpose of the document. So, a suitable solution for XML searching should consider
both structure and content of XML trees. Hence, we propose
the method which combining structure-based similarity with thecontent-based similarity.
This research can be divided into two parts; first we developed
KLAX, a method to measure a similarity value between a pair of
XML trees. KLAX is an improvement of our previous method
LAX+ [12] by use a keyword similarity to match leaf nodes
1
2

a)
b)
c)

Tokyo Institute of Technology, 2–12–1 Meguro, Tokyo 152–8552, Japan
Chulalongkorn University, 254 Phayathai Road, Pathumwan, Bangkok,
10260, Thailand
auvattanasombat.a.aa@m.titech.ac.jp
watanabe@de.cs.titech.ac.jp
yokota@cs.titech.ac.jpⓒ 2013 Information Processing Society of Japanof subtrees in XML trees. Second, we propose LAX&KEY, amethod to calculate the similarity between XML trees by utilizing both structure and content. LAX&KEY separately computes
structure-based similarity from LAX+ and content-based similarity from keywords, then combines with weighting.
We apply KLAX and LAX&KEY to our SOS system insteadof LAX+ to improve its precision. In our experimental evaluation, we use docx, xlsx and pptx file formats as experimental data
set to investigate effects of our approach.
The remaining part of this paper is organized as follows: Section 2 introduces related work. Section 3 explains an OOXML
document format. Section 4 overviews Structure-based Office
document Search (SOS) and LAX+, and Section 5 explain our
proposed methods. Section 6 shows our experimental results.
Section 7 concludes this paper and mentions future research issues.

2. Related work
There are several search engines which have difference purposes and processes [2], [3], [4]. Recently, there are many kindsof documents and the quantity is increasing in high rate due to theinformation period. So, searching and clustering of those documents have become the issue that we need to solve. Since there
are many kinds of documents which are depend on their structures and using purposes, the search engine should be different tobe proper with them. For XML tree is also need specification forsearch engine.
We have various methods to measure XML similarity values[5], [7], [8], [9], [10]. The important factors that should be considered for the performance of the method are computational costand precision. Some are popularly used because they are fast andsome give high precision. LAX [11] and LAX+ [12] are algo-1Vol.2013-DBS-157 No.14
Vol.2013-IFAT-111 No.14
2013/7/23

IPSJ SIG Technical Report

A cutting point is a node (element) to divide a XML tree into
subtrees. For each node x in the XML tree, we apply the following formula to decide which node is most suitable to bea cutting point.
w x = |children(x)| × dαx

Fig. 1

Structure of OOXML

rithms to calculate similarity values of XML trees by comparing
leaf nodes from their subtrees with low computational cost andhigh precision. Then, SOS [12] is the method for measuring thesimilarity values for OOXML documents from LAX+. In this paper, we modified LAX+ to improve the precision of the result andalso applied our propose methods to SOS.

3. Office Open XML (OOXML or OpenXML)OOXML file format [1] is a zipped, XML-based file format
developed by Microsoft. We can reach internal XML files by extracting the zip archive. This file format can be used to represent
electronic office documents. There are formats for word processing documents, spreadsheets and presentations as well as specificformats for material such as mathematical formulae, graphics,
bibliographies etc.
OOXML documents are stored in Open Packaging Convention(OPC) packages, which are zip files containing XML and otherdata, along with a specification of the relationship between them.
Depending on the type of the document, the packages have different internal directory structures and names. An OOXML document consists of multiple Parts, and each Part consists of one ormore XML files. Figure 1 shows a structure of a docx file when
it has been extracted.

4. An Overview of Previous Methods
Here, we introduce our previous work [12]. We have been developing SOS system for OOXML similarity search. It has tocalculate similarities between sets of XML files in OOXML documents. LAX+ is our previous method to calculate similarity of
XML trees. Firstly, we explain LAX+ and SOS in Section 4.1
and Section 4.2, then we describe the problem of LAX+ in Section 4.3.
4.1 LAX+
LAX+ is an algorithm to calculate similarity values between
two XML trees. From a pair of XML trees ( fbase , ftarget ), it returns
S xml ( fbase , ftarget ). LAX+ is an symmetric similarity measure, so
S xml ( fbase , ftarget ) is equal to S xml ( ftarget , fbase ).
The procedure of LAX+ to calculate a similarity value between
a pair of XML trees is as follow:( 1 ) Decomposing an XML tree to subtrees by choosing a cutting point:ⓒ 2013 Information Processing Society of Japan(1)|children(x)| is the number of x’s child nodes, d x is the maximum depth from node x to leaf nodes, and α is a weightparameter. fbase is decomposed into a set of subtrees T base ={tu }, and ftarget is also decomposed into T target = {tv }.
( 2 ) Calculating similarity values between subtrees:
We make a pair of subtrees (tu , tv ) from base’s subtrees andtarget’s subtrees. Similarity values between subtrees are derived by the following formula.
S sub (tu , tv ) = |Matched Lea f (tu , tv )|(2)

Matched Lea f (tu , tv ) expresses a subset of leaf nodes in tu ,whose element exactly matches one or more leaf nodes in
tv . “Match” means strings (PCDATA) in leaf nodes are completely same.
( 3 ) Calculating a similarity value between two XML trees byderiving from similarity values of subtree pairs:
S xml ( fbase , ftarget ) is a LAX+’s similarity value between
XML trees fbase and ftarget . It is defined by the following
formula.
S xml ( fbase , ftarget )= min(

P

tu ∈T base maxtv ∈T target (S sub (tu , tv ))|Lea f ( fbase )|P
max
tu ∈T base (S sub (tu , tv ))tv ∈T target,|Lea f ( ftarget )|)(3)

4.2 Structure-Based Office Document Search(SOS): Styleand Structure Similarity Measure
Since an OOXML document consists of multiple Parts with
one or more XML files, comparing only one pair of XML files is
not enough. SOS is a method for calculating similarity between
sets of XML files from OOXML documents considered hierarchyof parts and XML files.
We suppose oq is an OOXML document being a query file ofsimilarity search and oi (1 ≥ i ≥ n) is an OOXML document in a
database. As we describe in Section 3, each OOXML document
oi consists of a set of Parts Pi = {pi j |1 ≤ j ≤ Ji }. And each Parts
pi j consists of a set of XML files Fi j = { fi jk |1 ≤ k ≤ Ki j }. oq also
includes a set of Parts Pq and sets of XML files Fq j . The procedure to calculate a similarity value between a pair of OOXML
documents in SOS is as follow.
( 1 ) Calculating similarity values between XML files:
By matching file names, we make a pair of XML files( fq jk , fi jk ) from the j-th Parts of both OOXML documents
oq and oi . We calculate a similarity value for each pair
S xml ( fq jk , fi jk ). The S xml value is derived by LAX+ and our
proposed methods. LAX+ is explained in Section 4.1.
2

Vol.2013-DBS-157 No.14
Vol.2013-IFAT-111 No.14
2013/7/23

IPSJ SIG Technical Report

Fig. 2

An example of LAX+’s problem( 2 ) Calculating similarity values between Parts by aggregating multiple S xml values:
S parts (pq j , pi j ) is a similarity value for the j-th parts by thefollowing formula.
P
fq jk ∈Fq j , fi jk ∈Fi j S xml ( fq jk , fi jk )S part (pq j , pi j ) =(4)
max(|Fq j |, |Fi j |)( 3 ) Calculating a similarity value between OOXML documents by aggregating multiple S parts values:
S oo (oq , oi ) is a similarity value of a pair of OOXML documents (oq , oi ), and it is obtained by the following formula.
Xwj
S oo (oq , oi ) =( P|P | × S part (pq j , pi j )) (5)qpq j ∈Pq ,pi j ∈Pi
l=1 wlWhen w j is a weight parameter for jth Parts
Fig. 3

4.3 Problem of LAX+ at Leaf Node Similarity Measure
In LAX+, when it compares the leaf node of subtrees-pair, it
has used the exactly same matching method between the contents
in two leaf nodes as in Formula 2. That means the similarity score
between two leaf nodes can be only 0 or 1 even though the content in target leaf node has some common words or almost all aresame with the content in base leaf node.
For instance, as in Figure 2 if using LAX+ to compare these
two subtrees, the overall score will be 0. In spite of, the content
in leaf nodes are very close to each other. This example showsthat LAX+’s score is insufficient in some cases.

5. KLAX and LAX&KEY (Proposed methods)
To solve the problem introduced in Section 4.3, we used keyword similarity method for comparing leaf nodes of subtree. We
propose KLAX (Keyword LAX+) extending the LAX+ process
in Section 5.2. Moreover, we also propose another way to indicate the similarity between XML trees. LAX&KEY is describedin Section 5.3.
5.1 Keyword Extraction and keyword-based similarity
Figure 3 illustrates how to extract keywords. First, we choose
keywords by assort only the content of the file. The content means
the text that readers (human) can read when open an OOXML
documents excluding tags and attributes of each tag. Then, separate the content into words and roughly assign Part of speech(POS) [17], [18] for each word. After that, pick only “Noun”ⓒ 2013 Information Processing Society of Japan

Procedure of how to choose keywords

words (including proper noun and others that cannot determine
its POS) to be represent keywords for each files. Last, comparing
each file (or leaf node) using these keywords to measure the similarity. The similarity score is defined by the following formula.
S keyword ( fbase , ftarget ) =|MatchKeyword( fbase , ftarget )|max(|Kbase |, |Ktarget |)(6)

 |MatchKeyword( fbase , ftarget )| is the number of keywords
from base file’s content that matching with the keywords intarget file’s content.
 |Kbase | is the number of keywords in base file’s content.
 |Ktarget | is the number of keywords in target file’s content.
5.2 KLAXKLAX is an algorithm to measure the XML similarity which isextended from LAX+ by utilizing keyword similarity to measure
the leaf nodes of subtrees similarity instead of the rigid matching of LAX+. When we compute a similarity value between leaf
nodes, we considered tags, attributes and attribute’s values separately from the content. First, we compare tags, attributes andattribute’s values of leaf-node-pair. If they are all same it get firstγ score, then compare content with keyword-based similarity by
Formula 6. So, the overall score for KLAX is derived by following formula.

3

Vol.2013-DBS-157 No.14
Vol.2013-IFAT-111 No.14
2013/7/23

IPSJ SIG Technical Report

6. Experiment Evaluation
In this section, we held two experiments and for each can beseparated into two parts. First experiment, we compare LAX+
with our new proposed methods to show that our proposals give
better result in precision and recall for calculation similarityof single pair of XML files. Second, we compare the original SOS (using LAX+) with improved SOS (using KLAX andLAX&KEY) to investigate the precision and recall of measuring
a similarity between OOXML documents (multiple sets of XML
files). Figure 5 is the experiment data for our experiments below.
Fig. 4Comparison between LAX+ and KLAX to calculate the similarity
between leaf nodes of subtrees

S K lea f (lu , lv )
if tags are not same
0
=


γ + ((1 − γ) · S keyword (lu , lv )) otherwise(7)

We have used γ = 0.5 in this research. When (lu , lv ) is leafnode-pairs on a subtree-pair (tu , tv ).
Therefore, in KLAX Formula 2 in the second step of LAX+ is
replaced by the following formula.
P
S sub (tu , tv ) =lu ∈Lea f (tu ) maxlv ∈Lea f (tv ) (S K lea f (lu , lv ))min(|Lea f (tu )|, |Lea f (tv )|)(8)

When |Lea f (tu )| and |Lea f (tv )| stand for the number of leaf
nodes in subtree tu and tv respectively.
Figure 4 shows the difference between using LAX+ and KLAX
when they calculate the similarity between Subtree1 and Subtree2. The remaining part to compute the similarity between
XML files is same as LAX+.
5.3 LAX&KEY
Due to the different roles between XML structure and the content of files, the document similarity should be a combinationof the structure similarity value and the content similarity values. LAX&KEY calculates LAX+ similarity and keyword similarity separately. Then, it combines two scores together in order to reckon the overall similarity score. The similarity score of
LAX&KEY is defined by following formula.
S LAX&KEY ( fbase , ftarget )= β · S xml ( fbase , ftarget ) + (1 − β) · S keyword ( fbase , ftarget ) (9) S xml ( fbase , ftarget ) is the LAX+ score between base file( fbase )and target file( ftarget ) S keyword ( fbase , ftarget ) is the keyword similarity score between
base file( fbase ) and target file( ftarget ) β is a weight parameter to control influences of LAX+ andkeyword similarity. (β ∈ (0, 1))
In additional, we also used this purpose with SOS to find thesimilarity between OOXML documents and the similarity score
for SOS with LAX&KEY is derived by combining the SOS scorewith the keyword-based similarity score which is shown in Formula 6. We have join both score by using Formula 9 above.
ⓒ 2013 Information Processing Society of Japan

Fig. 5Experiment Data

6.1 Comparison of LAX+ with KLAX and LAX&KEY
In this experiment, we extracted the XML files from pptx files
and docx files, for pptx files we used “slide1.xml” which includes
style information and content data of the first slide and docx files
we used “document.xml” which is the main part of any word documents to calculate the similarity value between XML files foreach kind of documents. Therefore, the procedure of this experiment is as follows.
( 1 ) From a set of pptx and docx files, we choose one file as aquery file oq . Then, the remaining files are target of similarity search.
( 2 ) For each query file and target files, we choose “slide1.xml”
for pptx files and “document.xml” for docx files. Then, we
calculate a similarity value between XML files.
( 3 ) We rank the target files based on its similarity values andchooses the file whose similarity values are greater than thethreshold θ. Then, we compare the result with an answer set
corresponding to the query file, and get precision and recall;precision and recall are defined as follows.
Number Retrieved Relevant
Number T otal Retrieved
Number Retrieved Relevant
Recall =Number Possible Relevant

Precision =

(10)
(11)

( 4 ) We iterate step 1, 2, 3 for each file in an experimental data tocompute average values of precision and recall.
6.1.1 LAX+ vs. KLAX
We show a precision-recall graph of LAX+ and KLAX in Figure 6 for pptx file type and Figure 7 for docx file type. The
horizontal axis expresses recall values and the vertical axis expresses precision values. From the result, KLAX is better that
LAX+ in precision at the same recall value. Since KLAX used
the keyword-based similarity to match leaf nodes between subtrees which is more flexible than LAX+’s, the similarity scores of4Vol.2013-DBS-157 No.14
Vol.2013-IFAT-111 No.14
2013/7/23

IPSJ SIG Technical Report

Fig. 6

Precision-recall graph of LAX+ and KLAX on pptx files

Fig. 7

Precision-recall graph of LAX+ and KLAX on docx files

Fig. 9Precision-recall graph of LAX+ and LAX&KEY on docx files

Fig. 10

Precision-recall graph of SOS and KLAX on pptx files

Fig. 11 Precision-recall graph of SOS and KLAX on docx files

Fig. 8Precision-recall graph of LAX+ and LAX&KEY on pptx files

KLAX are higher in most cases especially for alike files. Thus,
the similarity score by KLAX is more than LAX+ for each incase of similar files pair.
6.1.2 LAX+ vs. LAX&KEY
In this experiment, we have varied the β values from 0.01 to
0.99 to explore the properly β that gives the best result in precision and recall for each document type which are 0.50 and 0.35
for pptx and docx respectively. We show a precision-recall graphof LAX+ and LAX&KEY in Figure 8 for pptx file type and Figure 9 for docx file type. From above result, LAX&KEY is betterthat LAX+ in precision at the same recall value. Due to the factthat XML file has two considerable parts which are structure andcontent of file, consideration of both should get more accuracy inresult.
ⓒ 2013 Information Processing Society of Japan

6.2 Applying KLAX and LAX&KEY to SOS
6.2.1 SOS with KLAXIn this experiment, we compare SOS using LAX+ and SOS
using KLAX to verify whether KLAX can be improves SOS in
precision and recall. We show precision-recall graphs of SOS
with LAX+ and SOS with KLAX for pptx, docx and xlsx file
type in Figure 10, 11, 12 respectively. From above result, SOS
with KLAX is better than SOS with LAX+ in precision at thesame recall value for pptx and docx file type. In case of xlsx
files, the keyword similarity might not very significant to calculate the similarity value between them. Due to the purpose of
xlsx files which often include many numbers or IDs and almost
not composed of words or keywords, keyword-based similarity is
not much influential in this document type.
6.2.2 SOS with LAX&KEY
In this experiment, we also varied the β values from 0.01 to
0.99 to explore the properly β that gives the best result in preci5

Vol.2013-DBS-157 No.14
Vol.2013-IFAT-111 No.14
2013/7/23

IPSJ SIG Technical Report

Fig. 15 Precision-recall graph of SOS and LAX&KEY on xlsx files

Fig. 12 Precision-recall graph of SOS and KLAX on xlsx files

LAX&KEY gives obviously better result than LAX+. Since, theresult of xlsx files is a bit ambiguously, we plan to do further
experiments for evaluating KLAX and LAX&KEY for OOXML
similarity by using different weight for each Part of OOXML documents. Moreover, the keyword-based similarity also can be improved such as POS tagger, procedure to choosing the words andothers.
References[1]Fig. 13

Precision-recall graph of SOS and LAX&KEY on pptx files

[2]
[3]
[4]
[5]
[6]
[7]
[8]

Fig. 14

Precision-recall graph of SOS and LAX&KEY on docx files[9]sion and recall for each document type which are 0.50, 0.40 and
0.50 for pptx, docx and xlsx respectively. We show a precisionrecall graph of SOS with LAX+ and SOS with LAX&KEY in for
pptx, docx and xlsx file type in Figure 13, 14, 15 respectively.
From the result graph, SOS with LAX&KEY is better than SOS
with LAX+ in precision at the same recall value for all type of
OOXML documents in the experiment.

7. Conclusion and Future Work
This paper describes the problem of LAX+ to calculate similarity value between XML trees which is the leaf node matching method is rigid, and affects the similarity value to be low.
Therefore, we solved the problem with a keyword similarity
method called KLAX which extends LAX+ advantages and also
propose LAX&KEY to be an alternative way to calculate thesimilarity values of XML files and OOXML documents. After that, we applied the KLAX to SOS instead of LAX+, andcombining LAX&KEY with SOS in our experiments. SOS withKLAX gives slightly bettet result especially for xlsx files whileⓒ 2013 Information Processing Society of Japan

[10]
[11]
[12]

[13]
[14]
[15]
[16]
[17]
[18]

ECMA-376 4th edition,
http://www.ecma-international.org/publications/standards/Ecma376.htm
Windows Search,
http://www.microsoft.com/japan/windows/desktopsearch/default.mspx
Mac OS X Spotlight,
http://support.apple.com/kb/HT2531“What file types can Google index?”,
http://support.google.com/webmasters/bin/answer.py?answer=35287
J.Tekli, R.Chbeir and K.Yetongnon, “An overview on XML similarity:
Background, current trends and future directions”, Computer Science
Review, Vol. 3, No. 3, pp. 151–173, 2009.
J. Pokorny, J. Vávra and V. Snásel, “A Renewed Matrix Model for
XML Data”, Proc. International Conference on Intelligent Systems
Design and Applications (ISDA2008), pp. 549–556, 2008.
K. C. Tai, “The Tree-to-Tree Correction Problem”, Journal of the Association for Computing Machinery, Vol. 26, No. 3, pp. 422–433,
1979.
E. D. Demaine, S. Mozes, B. Rossman and O. Weimann, “An Optimal Decomposition Algorithm for Tree Edit Distance”, ACM Trans.
Algorithms, Vol. 6, No. 1, pp.2:1–2:19, 2009.
D. Buttler, “A Short Survey of Document Structure Similarity Algorithms”, Proc. International Conference on Internal Computing, pp.3–
9, 2004.
S. Helmer, “Measuring the Structural Similarity of Semistructured
Documents Using Entropy”, Proc. International Conference on Very
Large Databases (VLDB2007), pp.1022–1032, 2007.
W. Liang and H. Yokota, “LAX: An Efficient Approximate XML Join
Based on Clustered Leaf Nodes for XML Data Integration”, Proc. BNCOD, Springer LNCS 3567, pp. 82–97, 2005.
Y. Watanabe, H. Kamigaito and H. Yokota, “Similarity Search for Office XML Documents Based on Style and Structure Data”, International Journal of Web Information Systems, Emerald Group Publishing, Vol. 9, Issue 2, pp. 100–116, June, 2013.
W. Viyanon, S. K. Madria and S. S. Bhowmick, “XML data integration based on content and structure similarity using keys”, Proc. On
the Move to Meaningful Internet Systems (OTM2008), 2008.
T. Tran, R. Nayak and P. Bruza, “Combining Structure and Content
Similarities for XML Documents Clustering”, Proc. Australasian Data
Mining Conference (AusDM’ 08), 2008.
L. Zhang, Z. Li, Q. Chen and N. Li, “Structure and Content Similarity for Clustering XML Documents”, Proc. WAIM 2010 Workshops,
LNCS 6185, pp. 116–124, 2010.
J. Tekli, R. Chbeir and K. Yetongnon, “A Hybrid Approach for XML
Similarily” Proc. SOFSEM 2007, LNCS 4362, pp. 738–795, 2007.
Stanford Log-linear Part-Of-Speech Tagger.
http://nlp.stanford.edu/software/tagger.shtml
Part Of Speech Tagging PHP/ir.
http://phpir.com/part-of-speech-tagging

6