=Paper= {{Paper |id=None |storemode=property |title=Results of NBJLM for OAEI 2010 |pdfUrl=https://ceur-ws.org/Vol-689/oaei10_paper10.pdf |volume=Vol-689 |dblpUrl=https://dblp.org/rec/conf/semweb/WangWL10 }} ==Results of NBJLM for OAEI 2010== https://ceur-ws.org/Vol-689/oaei10_paper10.pdf

Results of NBJLM for OAEI 2010

Song Wang1,2 , Gang Wang1 and Xiaoguang Liu1
1
College of Information Technical Science, Nankai University Nankai-Baidu Joint Lab,
Weijin Road 94, Tianjin, China
2
Military Transportation University, The Equipment support Department, Tianjin, China
jackws66@yahoo.com

Abstract. This paper presents the results obtained by NBJLM (Nankai Baidu
Joint Lab Matcher) for its first participation to OAEI 2010. The research of
ontology-based similarity calculation among concepts has already been a hot is-
sue. NBJLM is an hybrid ontology alignment method that considers both simi-
larity of literal concept and semantic structure. Simultaneously, how to accelerate
matching has been mentioned in this paper and the experimental results show the
remarkable improvement of matching speed. In OAEI 2010, NBJLM submitted
the result for one alignment task: anatomy.

1 Presentation of NBJLM
In recent years, Ontology matching is mainly used in ontology integration, ontology
merging, and ontology reusing. Many approaches to ontology matching have been pro-
posed over the years, references[1][5][3] make full use of information, probability and
statistics theory, however, they have limited ability to distinguish semantic differences,
and the similarity calculation methods are not perfect. Besides, references[2][4][7][8]
have considered various factors, but they do not take into account how to avoid unneces-
sary calculation to shorten computing time in mapping large-scale ontologies. NBJLM
is a multiple strategy dynamic ontology matching system implemented in java. It con-
siders both the literal concept and ontology structure that includes node depth, node
density and semantic distance.

1.1 State, purpose, general statement
Given two heterogeneous ontologies O1 and O2, a matching is made up of a set of cor-
respondences between pairs of node IDs belonging to O1 and O2, respectively. NBJLM
is designed to find out relations of equivalence and subsumption between entities, i.e.
classes and properties, issued from two ontologies. Our approach makes use of the
matching strategy that considers literal similarity measure and ontology structure sim-
ilarity measure. The core contributions of NBJLM is described as followed: Firstly, it
uses Hash mapping algorithm to improve efficiency of calculation. Secondly, it takes a
full analysis of a number of issues to be considered in structure matching, which makes
the algorithm works better, and the matching results are more accurate and efficient. As
demonstrated by the experimental results, our method can greatly cut the running time,
meanwhile, precise matching results can be obtained.
Heterogeneous Literal Similarity
Ontologies 1 1
2 4
WordNet 2
3
7 5
4 3

Match Results Structure Similarity

1 1
2 2
3 3

Fig. 1. Procedure of the matching of heterogeneous ontologies.

1.2 Specific techniques used for Anatomy Track
NBJLM uses a new matching strategy that considers literal similarity measure and on-
tology structure similarity, simultaneously. We obtain the following formula:

𝑆𝑖𝑚(𝐼𝐷1, 𝐼𝐷2) = 𝜃 × 𝑆𝑖𝑚 𝑙𝑖𝑡𝑒𝑟𝑎𝑙(𝐼𝐷1, 𝐼𝐷2) + (1 − 𝜃) × 𝑆𝑖𝑚 𝑠𝑡𝑟𝑢𝑐𝑡(𝐼𝐷1, 𝐼𝐷2)

where 𝑆𝑖𝑚 𝑙𝑖𝑡𝑒𝑟𝑎𝑙(𝐼𝐷1, 𝐼𝐷2) is the literal concept similarity measure, 𝑆𝑖𝑚 𝑠𝑡𝑟𝑢-
𝑐𝑡(𝐼𝐷1, 𝐼𝐷2) is the structural similarity measure, and 𝜃 (0 < 𝜃 < 1) is paramater to
control how much literal and ontology structure contribute to the ontologies matching
respectively. Firstly, the measure of literal similarity is a preliminary matching. It takes
account of polysemy and synonym of a word, by transforming the word into a semantic
collection using WordNet. Then we can get the preliminary matching results that is se-
mantic mapping rather than spelling mapping of words. Secondly, based on the literal
matching results, the measure of ontology structure similarity is calculated through the
relation between hypernym and hyponym of a word, considering distance of edges, and
depth and density of node in the hierarchy of ontology. With the final combination of
the two values, and with adjustment of the parameter, we could obtain more reasonable
matching results. The procedure is shown in Fig. 1.

An optimized algorithm for concept sets retrieving If look up a word in Word-
Net, we can get one or more Synsets (defined by WordNet). For one thing each Synset
is a concept set of the words which have the same meaning. For another a word may
have several meanings, therefore, each Synset can be used to express one concept of
the word. The concept of a node ID in the hierarchy of ontology may be described by
several phrases, which are composed of words. That means the concept of the node ID
could be described by several Synsets. If we deal with all the Synsets in matching, re-
dundant computation will be inevitable. Therefore, this paper proposes a strategy that
obtain the set of Synsets, which are the most similar to the concept of the phrase while
Phrase p W1 W2 W3

WordNet A
S1
S1 S2 S3 S4 S5 S2
S3
Add hypernym and hyponym S4
S5

S1’ S2’ S3’ S4’ S5’

S1’’ a S2’’ b S3’’ c S4’’ d S5’’ e
a=b a>b ae d=e d 𝑏, 𝑑 = 𝑒 (c has no comparable object), the Synsets of 𝑤1,
𝑤2 and 𝑤3 are (𝑆1), (𝑆3) and (𝑆4, 𝑆5), respectively.
6) Get the union set of (𝑆1), (𝑆3) and (𝑆4, 𝑆5), 𝐵(𝑆1, 𝑆3, 𝑆4, 𝑆5), which denotes
the concept of phrase p.
7) It can be found that Synset 𝑆2 existing in 𝐴 but not in 𝐵 is uncorrelated to the
concept of phrase 𝑝. Therefore, the redundancy can be filtered out by our optimized
algorithm. Besides, as increasing in the number of words of phrase, the optimization
of the algorithm could be more obvious. Since the matching of nodes in the ontolo-
gies is based on the matching of Synsets, the reduction of Synsets, which denote the
concepts of nodes in the ontology, will inevitably lead to the reduction of irrelevant
semantic mappings and greatly reduce the amount of calculation.

Method of calculation of structural similarity The calculation of structural similar-
ity involves semantic distance with weight, information content, depth and density of
node. In order to tackle two ontologies conveniently, we add a virtual common root
node which connects two ontologies. So the model could be changed from two inde-
pendent ontologies to a large ontology, which facilitates the matching. The process of
matching is described as follow: firstly, search the common ancestor 𝐶 of two nodes
𝑐1 and 𝑐2. In fact, 𝐶 is a mapping pair(𝑐1′ , 𝑐2′ ) got from the matching results of lit-
eral concepts, where 𝑐1′ is the ancestral node of 𝑐1 and 𝑐2′ is the ancestral node of 𝑐2.
Secondly, calculate the semantic distance between 𝑐1 and 𝑐2 through 𝐶. Thirdly, do
iterative calculation that search the common ancestor 𝐶 of 𝑐1′ and 𝑐2′ until 𝐶 is the
virtual common node. Finally, add depth and density of nodes into the calculation. The
formula is:
( ) 𝛼𝑘
𝑆𝑖𝑚 𝑠𝑡𝑟𝑢𝑐𝑡(𝐼𝐷1, 𝐼𝐷2) = 𝑆𝑖𝑚 𝐶𝑜𝑚 𝑎𝑛𝑐𝑒𝑠𝑡𝑜𝑟(𝑐1, 𝑐2) × +
𝑘 + 𝐷𝑖𝑠(𝑐1, 𝑐2)
( 𝑒(𝑐1) + 𝑒(𝑐2) ) 𝛾 ( 𝑑(𝑐1) 𝑑(𝑐2) )
𝛽 𝜂 + (1 − 𝜂) × + +
2 2 𝑑(𝑐1) + 1 𝑑(𝑐2) + 1
Where 𝐶𝑜𝑚 𝑎𝑛𝑐𝑒𝑠𝑡𝑜𝑟(𝑐1, 𝑐2) returns the common ancestor pair of 𝑐1 and 𝑐2, and
𝐷𝑖𝑠(𝑐1, 𝑐2) is the semantic distance, 𝑒(𝑐1) and 𝑑(𝑐1) are the density and depth of
node[7]. The parameters 𝑘(𝑘 > 0), 𝜂(0 < 𝜂 < 1), 𝛼, 𝛽 and 𝛾 (𝛼 + 𝛽 + 𝛾 = 1) control
how much semantic distance, depth, density contribute to the calculation of structural
similarity respectively.
∑ ( ) ∑ ( )
𝐷𝑖𝑠(𝑐1, 𝑐2) = 𝑤𝑡 𝑥, 𝑝(𝑥) + 𝑤𝑡 𝑝(𝑥), 𝑥
𝑥∈𝑝𝑛(𝑐1) 𝑥∈𝑝𝑛(𝑐2)

𝑤𝑡(𝑐, 𝑥) = 𝐿𝑠(𝑐, 𝑥) × 𝑇 (𝑐, 𝑥)
∩
( ) 𝑃 (𝑐 𝑥)
𝐿𝑠(𝑐, 𝑥) = − log 𝑃 (𝑐∣𝑥) = − log = 𝐼𝐶(𝑐) − 𝐼𝐶(𝑥)
𝑃 (𝑥)
Where 𝑤𝑡(𝑐, 𝑥) is the weight of 𝑒𝑑𝑔𝑒(𝑐, 𝑥), 𝑝𝑛(𝑐) is the set of nodes which are
on the path from node 𝑐 to the common ancestor node, 𝑝(𝑥) is the parent node of 𝑥,
𝐼𝐶(𝑥)is interest degree[6], 𝐿𝑠(𝑐, 𝑥) is the difference of the information content values
between a child node and its parent, and 𝑇 (𝑐, 𝑥) is the link relation factor.
There is something important to pay attention to, which makes the algorithm more
efficiency:
abdk O2:ID-1'

O1:ID-1 abck

abce O2:ID-2'

Fig. 3. Literal concept mapping of one to many

– This approach searches all the ancestor nodes of two nodes to be matched, and
select the best matching path. If only search the nearest common ancestor node, the
result may be wrong. For example: owing to the situation of one to many mappings
in the matching results of literal concepts, it may occur that the mappings (𝑂1 :
𝐼𝐷 − 2, 𝑂2 : 𝐼𝐷 − 2′ ) and (𝑂1 : 𝐼𝐷 − 2, 𝑂2 : 𝐼𝐷 − 4′ ) got from results
of literal concept matching are candidates for structural matching, but in fact (𝑂1 :
𝐼𝐷 − 2, 𝑂2 : 𝐼𝐷 − 2′ ) is the best mapping. When comparing the node 𝑂1 : 𝐼𝐷 − 6
and node 𝑂2 : 𝐼𝐷 − 6′ , if only search their nearest common ancestor, we will get
a pair of nodes, 𝑂1 : 𝐼𝐷 − 2 and 𝑂2 : 𝐼𝐷 − 4. However, it is not the best mapping
pair (we have known that the pair of 𝑂1 : 𝐼𝐷 − 2 and 𝑂2 : 𝐼𝐷 − 2′ is the best). To
avoid this, we need to traverse all the common ancestors of nodes rather than the
nearest. Then compare the iterative results and choose the best.
– Involve the literal interest degree. For instance, when we find mapping pairs (𝑂1 :
𝐼𝐷 − 1, 𝑂2 : 𝐼𝐷 − 1′ ) and (𝑂1 : 𝐼𝐷 − 1, 𝑂2 : 𝐼𝐷 − 2′ ) have the same struc-
tural similarity, and the values of their literal similarity calculations are both 3/4 as
shown in fig. 3, where 𝑎, 𝑏, 𝑐, 𝑑, 𝑒 and 𝑘 are Synsets, then the literal interest degree is
needed to judge which the better matching object of 𝑂1 : 𝐼𝐷−1 from 𝑂2 : 𝐼𝐷−1′
and 𝑂2 : 𝐼𝐷 − 2′ is: the less frequency of a Synset occurs in the ontology is, the
more it contributes to the meaning of the node. So we calculate all the literal interest
degrees of the common Synsets in each mapping pair using the formula metioned
in Definition 4. And compare the maximal literal interest degrees of all the mapping
pairs, then the max is the best matching because they contain the common Synset
whose meaning is closer to concept of the phrase. To suppose the maximal literal
interest degree of (𝑂1 : 𝐼𝐷 − 1, 𝑂2 : 𝐼𝐷 − 1′ ) is 𝑛1 got from 𝑘, simultaneously,
the maximal literal interest degree of (𝑂1 : 𝐼𝐷 − 1, 𝑂2 : 𝐼𝐷 − 1′ ) is 𝑛2 got from
𝑒, and 𝑛1 > 𝑛2, we can draw the conclusion: (𝑂1 : 𝐼𝐷 − 1, 𝑂2 : 𝐼𝐷 − 1′ ) should
be the best mapping pair because 𝑂1 : 𝐼𝐷 − 1 is more interested in Synset 𝑘.
– At last calculate the factors of density and depth of node. Because in each iteration
the value of semantic distance should be multiplied by similarity of the common
ancestor node which is smaller than 1, it will surely lead to the similarity of child
nodes smaller than those of their ancestor nodes. This is contradictory to the role of
depth and density calculation, because the nodes which have greater values of depth
and density will have the larger value of similarity. Therefore, we must calculate the
depth and density of node out of the procedure of calculation of semantic distance
and iterations.
Main Thread

Read O1

New Thread_1
WordNet
... For O1
Return
New Thread_N

Read O2
Literal Concept &
Structure Matching
Hash O1

WordNet
For O2

Main Thread
New Thread_1
Synchrony ...
New Thread_N

Fig. 4. Parallelization of the algorithm implemented by multi-threads

Parallelization of the algorithm NBJLM uses parallel algorithm to accelerate the
process of matching. Fig. 4 shows the task partitioning. Firstly, we use the main thread
to read 𝑂1 file and then look up the Synsets of all the node IDs of 𝑂1 in the WordNet.
The reason of use only one thread is that this stage contains only IO operations which
can not benefit from parallel execution and WordNet does not provide thread-safe APIs.
Secondly, another multi-threads are launched to calculate hash values of node IDs’
Synsets of 𝑂1, meanwhile we use the main thread to read 𝑂2 file and look up the
Synsets of all the node IDs of 𝑂2. And these tasks could be run in parallel because
one part is CPU operation, and another is IO operation. Finally, we synchronize all the
threads, and then use them to calculate the literal concepts similarity and the structure
similarity.

1.3 Adaptations made for the evaluation
This year, NBJLM has first taken part in OAEI. Therefore, in OAEI 2010 NBJLM used
the match to compute the alignments for one track(anatomy). In order to assure the
matching process is fully automated, all parameters are configured automatically with
a strategy. No specific adaptations have been made.

1.4 Link to the system and parameters file
The version of NBJLM for OAEI 2010 can be downloaded from our website: ℎ𝑡𝑡𝑝 :
//𝑤𝑤𝑤.𝑏𝑟𝑠𝑏𝑜𝑥.𝑐𝑜𝑚/𝑂𝐴𝐸𝐼2010. The parameter file is also included in the NBJLM.zip
file. I recommend readers to read the readme.txt file first. The file includes the necessary
description and parameters as well in brief.

1.5 Link to the set of provided alignments (in align format)

NBJLM alignment results for OAEI can be found at
ℎ𝑡𝑡𝑝 : //𝑤𝑤𝑤.𝑏𝑟𝑠𝑏𝑜𝑥.𝑐𝑜𝑚/𝑂𝐴𝐸𝐼2010.

2 Results

In this section, we describe the results of NBJLM algorithm against the Anatomy on-
tologies provided by the OAEI 2010 campaign. In this test, the real world cases of
anatomy for Adult Mouse Anatomy (2744 classes) and NCI Thesaurus (3304 classes)
for human anatomy are included. This year we have participated in task#1 for the first
time. Experiments were done on a computer with 1.8GHz AMDAthlon dual-core CPU
and 2GB DDR2 RAM memory.

2.1 anatomy

Subtrack#1 In this subtrack, participants are asked to maximize F-measure. NBJLM
used a threshold equal to 0.8 and obtained an F-measure equal to 85.8%. NBJLM ob-
tained precision equal to 92.0% and recall equal to 80.3%. The runtime was 2 minutes.

3 General comments

3.1 Comments on the results

– Strengths NBJLM deals with ontology from two different views and combines
results of every step in sequential way. If the ontologies have regular literals and
hierarchical structures, NBJLM can achieve satisfactory alignments. And the way
of minimizing the comparisons between entities, which leads to enhance running
efficiency.
– Weaknesses NBJLM depends on the literal concept results to calculate structural
similarity. So if the literals of concept missed, NBJLM will get bad results.

3.2 Discussions on the way to improve the proposed system

1) To enrich the semantic dictionaries because WordNet which is not a professional
dictionary cannot obtain more comprehensive semantic concepts.
2) To take into account all concepts properties instead of only the hierarchicals ones.
4 Conclusion

This paper reports our first participation in OAEI campaign. We present the alignment
process of NBJLM and describe the specific techniques for ontology matching. The
method based on heterogeneous ontologies combines the calculations of literal con-
cept and ontology structure and pays more attention to computational efficiency. The
strengths and the weaknesses of our proposed approach are summarized and the pos-
sible improvement will be made for the system in the future. We propose a brand new
algorithm to match ontologies.

References
1. E. Agirre and G. Rigau. A proposal for word sense disambiguation using conceptual distance.
AMSTERDAM STUDIES IN THE THEORY AND HISTORY OF LINGUISTIC SCIENCE SE-
RIES 4, pages 161–172, 1997.
2. Y. Jean-Mary, E. Shironoshita, and M. Kabuka. Ontology matching with semantic verification.
Web Semantics: Science, Services and Agents on the World Wide Web, page 235C251, 2009.
3. Y. Li, D. McLean, Z. Bandar, J. O’Shea, and K. Crockett. Sentence similarity based on se-
mantic nets and corpus statistics. IEEE Transactions on Knowledge and Data Engineering,
18(8):1138–1150, 2006.
4. M. A. Q. Muhammad Fahad. Similarity Computation by Ontology Merging System: DKP-
OM. Computer, Control and Communication, pages 17–18, February 2009.
5. P. Resnik et al. Using information content to evaluate semantic similarity in a taxonomy. In
International Joint Conference on Artificial Intelligence, volume 14, pages 448–453. Citeseer,
1995.
6. S. Ross. A first course in probability. New York, 1994.
7. J. Sevilla, V. Segura, A. Podhorski, E. Guruceaga, J. Mato, L. Martinez-Cruz, F. Corrales,
and A. Rubio. Correlation between gene expression and GO semantic similarity. IEEE/ACM
Transactions on Computational Biology and Bioinformatics (TCBB), 2(4):338, 2005.
8. J. Tang, J. Li, B. Liang, X. Huang, Y. Li, and K. Wang. Using Bayesian decision for ontology
mapping. Journal of Web Semantics: Science, Services and Agents on the WorldWideWeb,
pages 243–262, 2006.