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 issue. NBJLM is an hybrid ontology alignment method that considers both similarity 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.
Structure Similarity Match Results
NBJLM uses a new matching strategy that considers literal similarity measure and ontology structure similarity, simultaneously. We obtain the following formula:
where ( 1, 2) is the literal concept similarity measure, -
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 semantic 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, redundant 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 Fig. 2. Get the optimal Synsets to describe the concept of a phrase include the least Synsets, to describe the concept of a node ID with the help of Word-Net. So the unnecessary computation work could be reduced. Fig. 2 describes a simple example that how to tackle a phrase to get the optimal Synsets:
1) Obtain the Synsets of all the words 1, 2 and 3 from phrase got from a node of 1(or 2) by WordNet, respectively, ( 1, 2), ( 3) and ( 4, 5). 2) Get the union set of all the Synsets, ( 1, 2, 3, 4, 5), which denotes the concept of phrase p and includes the most Synsets. 3) Add the semantic environment (hypernym and hyponym of the Synset) to Synset.
Then we get 1 ′ , 2 ′ , 3 ′ , 4 ′ and 5 ′ . 4) Intersect ( 1, 2, 3, 4, 5) with 1 ′ , 2 ′ , 3 ′ , 4 ′ and 5 ′ , separately, resulting in 1 ′′ , 2 ′′ , 3 ′′ , 4 ′′ and 5 ′′ . And the numbers of elements of the intersections are , , , and . Meanwhile, establish correspondences between 1 and 1 ′′ , 2 and 2 ′′ , 3 and 3 ′′ , 4 and 4 ′′ , 5 and 5 ′′ . The purpose of doing intersections is to find correlation between semantic environment of a Synset and the concept of phrase p. The larger number of the intersection's elements is, the more similar relationship between them is. 5) Compare the numbers of intersections' elements mentioned at step 4, which are generated from the same word. And select the Synset of each word, associated with the result of intersection which has the larger number of elements. For example, on the assumption that > , = (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 ontologies 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.
The calculation of structural similarity 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 independent 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 literal 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 into the calculation. The formula is:
( 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.
)
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: -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 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 structural 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:
) 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. Parallelization of the algorithm NBJLM uses parallel algorithm to accelerate the process of matching. Fig. 4 shows the task partitioning. 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.
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.
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.
In this section, we describe the results of NBJLM algorithm against the Anatomy ontologies provided by the OAEI 2010 campaign. 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.
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 obtained precision equal to 92.0% and recall equal to 80.3%. The runtime was 2 minutes.
3 General comments
-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. 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 concept and ontology structure and pays more attention to computational efficiency. The strengths and the weaknesses of our proposed approach are summarized and the possible improvement will be made for the system in the future. We propose a brand new algorithm to match ontologies.