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.
1.1
Given two heterogeneous ontologies O1 and O2, a matching is made up of a set of correspondences 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 similarity 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 Ontologies
WordNet 3 1 2 3 1 2 NBJLM uses a new matching strategy that considers literal similarity measure and ontology structure similarity, simultaneously. We obtain the following formula: Sim(ID1; ID2) =
Sim literal(ID1; ID2) + (1 )
Sim struct(ID1; ID2) where Sim literal(ID1; ID2) is the literal concept similarity measure, Sim struct(ID1; ID2) 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.
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 Phrase p
Add hypernym and hyponym S1
S2 S1’
S2’ a=b
W1 S1 S2 a>b
W1 S1 S1 a<b
W1 S2 WordNet
S3 S3’
S4
S4’ W2 S3 S3 d>e
W3 S4
S5 S5’ d=e
W3 S4 S5 S4 S5 d<e
W3 S5
A S1 S2 S3 S4 S5
B S1 S3 S4 S5 S1’’ a
S2’’ b S3’’ c S4’’ d S5’’ e include the least Synsets, to describe the concept of a node ID with the help of WordNet. 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: 7) It can be found that Synset S2 existing in A but not in B is uncorrelated to the concept of phrase p. 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.
Method of calculation of structural similarity 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 C of two nodes c1 and c2. In fact, C is a mapping pair(c10; c20) got from the matching results of literal concepts, where c10 is the ancestral node of c1 and c20 is the ancestral node of c2. Secondly, calculate the semantic distance between c1 and c2 through C. Thirdly, do iterative calculation that search the common ancestor C of c10 and c20 until C is the virtual common node. Finally, add depth and density of nodes into the calculation. The formula is:
Sim struct(ID1; ID2) = Sim Com ancestor(c1; c2)
Where Com ancestor(c1; c2) returns the common ancestor pair of c1 and c2, and
Dis(c1; c2) is the semantic distance, e(c1) and d(c1) are the density and depth of
node[
Where wt(c; x) is the weight of edge(c; x), pn(c) is the set of nodes which are
on the path from node c to the common ancestor node, p(x) is the parent node of x,
IC(x)is interest degree[
There is something important to pay attention to, which makes the algorithm more efficiency:
O1:ID-1 a b c k
O2:ID-2' – 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 (O1 : ID 2; O2 : ID 20) and (O1 : ID 2; O2 : ID 40) got from results of literal concept matching are candidates for structural matching, but in fact (O1 : ID 2; O2 : ID 20) is the best mapping. When comparing the node O1 : ID 6 and node O2 : ID 60, if only search their nearest common ancestor, we will get a pair of nodes, O1 : ID 2 and O2 : ID 4. However, it is not the best mapping pair (we have known that the pair of O1 : ID 2 and O2 : ID 20 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 (O1 : ID 1; O2 : ID 10) and (O1 : ID 1; O2 : ID 20) have the same structural similarity, and the values of their literal similarity calculations are both 3=4 as shown in fig. 3, where a; b; c; d; e and k are Synsets, then the literal interest degree is needed to judge which the better matching object of O1 : ID 1 from O2 : ID 10 and O2 : ID 20 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 (O1 : ID 1; O2 : ID 10) is n1 got from k, simultaneously, the maximal literal interest degree of (O1 : ID 1; O2 : ID 10) is n2 got from e, and n1 > n2, we can draw the conclusion: (O1 : ID 1; O2 : ID 10) should be the best mapping pair because O1 : ID 1 is more interested in Synset k. – 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.
New Thread_1
...
Hash O1
New Thread_N
Read O1 WordNet For O1 Read O2 WordNet
For O2 Synchrony
Return Literal Concept &
Structure Matching Main Thread
New Thread_1
...
New Thread_N 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 O1 file and then look up the Synsets of all the node IDs of O1 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 O1, meanwhile we use the main thread to read O2 file and look up the Synsets of all the node IDs of O2. 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
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
The version of NBJLM for OAEI 2010 can be downloaded from our website: http : ==www:brsbox:com=OAEI 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
NBJLM alignment results for OAEI can be found at http : ==www:brsbox:com=OAEI 2010. 2
In this section, we describe the results of NBJLM algorithm against the Anatomy ontologies 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 obtained precision equal to 92.0% and recall equal to 80.3%. The runtime was 2 minutes. 3
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
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.