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.