Matching Large Ontologies Based on Reduction Anchors

1 Introduction

Recent years have seen an increasing use of large ontologies in various areas such as machine translation, e-commerce, digital library, and life science. Since building and maintaining large ontologies may be distributed and autonomous, large ontologies can also be heterogeneous. Ontology matching is a plausible solution to the heterogeneity problem. However, large ontology matching (LOM) is a challenge due to the high time complexity and space complexity. First, matching process requires a large amount of memory. This may cause the matching system to crash by the out of memory error. Second, most LOM methods are O(n2 × t) time complexity (n represents the number of concepts), i.e. it needs n2 times similarity calculations and each similarity calculation has O(t) complexity. This paper focuses on the time complexity in the LOM problem.

Most existing ontology matching systems are unable to deal with the LOM problem. The Ontology Alignment Evaluation Initiative (OAEI 1 ) results in past years showed that few systems could deal with LOM tasks. In OAEI2007, only 2 of all 18 systems finished 4 LOM tasks: anatomy, food, environment, and library. In OAEI2008, only 2 of all 13 systems finished 4 LOM tasks: anatomy, fao, mldirectory, and library, and only 1 system finished the vlcr task.

1 http://oaei.ontologymatching.org/

Divide-and-conquer strategy is a feasible solution to reduce the time complexity in LOM by partitioning a large ontology into small modules. However, it has two limitations. First, most existing ontology partitioning approaches cannot control the size of modules [Hu and Qu2006,Hu et al.2008]. Consequently, many too small or too large modules, which are inappropriate for matching, may be generated. Second, partitioning ontologies into modules may lead to the loss of useful semantic information on the boundary elements. As a result, the quality of ontology matching may be degraded.

In this paper, we propose a reduction anchors based approach for matching large ontologies. Compared to existing work, the proposed approach has the following advantages. First, it does not need to partition ontologies but keeps the high performance as the divide-and-conquer approaches have. Second, it is indeed a general LOM framework, in which most existing matching techniques could be used. The main contribution of this paper is that we introduce two types of reduction anchors to cut down the number of pairs for which a similarity measure must be computed during ontology matching. On the one hand, if two concepts have a high similarity, we leverage the concept hierarchy to skip subsequent matching between sub-concepts of one concept and super-concepts of the other concept. On the other hand, if two concepts have a low similarity, we leverage the locality phenomenon of matching to skip subsequent matching between one concept and the neighbors of the other concept. The former is called a positive reduction anchor and the latter is called a negative reduction anchor. Our experimental results show that the proposed approach is very effective for matching large ontologies.

2 RelatedWork

The LOM problem has been concerned by both academic researchers and industrial engineers. For example, people integrated common large ontologies for machine translation [Hovy1998], discovered mappings between Web directories for information retrieval [Massmann and Rahm2008], and matched biology and medical ontologies [Zhang et al.2007, Mork and Bernstein2004]. This paper classifies existing LOM solutions into three types: quick-similaritycalculation (QSC) methods, parallel processing (PP) methods, and divide-and-conquer (DC) methods.

QSC methods attempt to reduce the time complexity in each similarity calculation, namely, the factor t in O(n2 × t). To this end, they often use simple but quick matchers such as literal-based and structure-based matcher. However, previous literature shows that, when matching large ontologies, QSC methods have a high time complexity [Mork and Bernstein2004]. In OAEI2007, some systems with QSC methods had not any advantages both in running time and the quality of matching results. Indeed, QSC methods are unable to deal with LOM for the following two reasons. First, quick matchers only use limited information that would cause low-quality results. Second, since n2 is a large number, reducing factor t has little influence on the matching performance.

PP methods employ the parallel strategy to deal with the similarity calculation [Mao2008]. The parallel processing idea is very simple and easy to be implemented. However, it needs expensive hardware resources to set up the parallel computing environment. More importantly, the matching performance improvement is limited.

DC methods attempt to reduce the factor n2 in O(n2 × t). The divide-and-conquer strategy partitions a large ontology into k modules or blocks to reduce the time complexity to O( n2 k × t). The improvement of performance is determined by the number of modules. Modular ontology is a popular way to partition large ontologies. However, existing modular ontology methods focus on the correctness and completeness of logics but cannot control the size of modules [Hu et al.2008], i.e., they would generate too large or too small modules. For example, a modularization algorithm will generate the large module with 15254 concepts for NCI ontology and will fail for GALEN ontology [Grau et al.2007].

Malasco [Paulheim2008] and Falcon-AO [Hu et al.2008] are two well-known LOM systems based on the DC method. Malasco employs partitioning algorithms and existing matching tools to match large ontologies. It uses three ontology partitioning algorithms: naive algorithm based on RDF sentences, structure-Based algorithm [Stuckenschmidt and Klein2004], and ontology modularity based on ε - connection [Grau et al.2006]. Falcon-AO proposes a structure-based partitioning algorithm to divide ontology elements into a set of small clusters, then constructs blocks by assigning RDF sentences to clusters. We notice that the structure-based partitioning algorithm in Falcon-AO can flexibly control the sizes of modules.

However, DC methods suffer from the contradiction between semantic completeness and information loss. More specifically, after partitioning, ontology elements near boundaries of modules are possible to lose useful semantic information. The more modules we have, the more information will be lost. This may degrade the quality of ontology matching. In Malasco, Paulheim realizes this problem and hence uses overlapping partitions to compensate such information loss. Paulheim claims that the overlapping partitions could limit the loss of precision less than 20% [Paulheim2008]. However, he also points out that overlapping partitions cause the matching phase running up to four times as long as nonoverlapping partitions.

3 Reduction Anchors

During matching large ontologies, we have two interesting observations: (1) A large ontology is often composed of concept hierarchies organized by is-a or part-of properties, and a correct alignment should not be inconsistent with such hierarchies; (2) An alignment between two large ontologies has locality, i.e., most elements of region Di in ontology O1 will match the elements of region Dj in ontology O2. The two observations provide the new perspective for finding the efficient LOM solution.

In Fig. 1(a), according to the first observation, if ai matches bp or bq, it will have a direct benefit: the subsequent similarity calculations between sub-concepts(/superconcepts) of ai and super-concepts(/sub-concepts) of bp or bq can be skipped. In this paper, we call such concepts like bp or bq the positive reduction anchors about ai, which employ the ontology hierarchy feature to reduce the time complexity in LOM. The positive reduction anchor is defined as follows.

Definition 1 (Positive Reduction Anchor (P-Anchor))

Given a concept ai in ontology O1, let the similarities between ai and concepts b1, b2, ..., bn in ontology O2 are Si1, Si2, ..., Sin, respectively. If Sij is larger than the predefined threshold ptV alue, the concept pair (ai, bj) is a positive reduction anchor, and all positive reduction anchors about ai are denoted by PA(ai) = {bj |Sij > ptV alue}.

It is clear that positive reduction anchors are symmetrical, i.e. if bp ∈ PA(ai), then ai ∈ PA(bp). ptV alue is a larger value in [0, 1].

(a) Positive Reduction Anchor

(b) Negative Reduction Anchor

Figure 1: Reduction anchors in large ontology matching

Fig. 1(b) shows the locality phenomenon in LOM, where Di represents a region in the ontology. Most elements in D0 are matched to the elements in D1. Suppose ai in D0 does not match bx in D2. According to the second observation, we can infer that the neighbors of ai do not match bx too. As a result, we can skip the subsequent similarity calculations between the neighbors of ai and bx, which will also reduce the times of similarity calculations. In this paper, we call such concepts like bx the negative reduction anchors about ai, which employ locality of matching to reduce the time complexity. The negative reduction anchor is defined as follows.

Definition 2 (Negative Reduction Anchor (N-Anchor))

Given a concept ai in ontology O1, let the similarity values between ai and concepts b1, b2, ..., bn in ontology O2 are Si1, Si2, ..., Sin, respectively. If Sij is smaller than the predefined threshold ntV alue, the concept pair (ai, bj) is a negative reduction anchor, and all negative reduction anchors about ai are denoted by NA(ai) = {bj |Sij < ntV alue}.

It is clear that negative reduction anchors are also symmetrical. ntV alue is usually a small value in [0, 1].

Based on positive and negative anchors, ontology mathcing process can skip many similairity calculations, which will significantly reduce the time complexity. Since P-Anchors and N-Anchors cannot be identified in advance, we hence dynamically generate them during ontology matching.

4 Large OntologyMatching Algorithms

4.1 LOM-P: Large OntologyMatching Algorithm Based on P-Anchors

Let PS(ai), the positive reduction set of ai, be all the ignorable similarity calculations predicted by PA(ai). If

|PA(ai)| > 0, we select the top-k P-Anchors with maximum similarities. Let PS(ai|bj) be the positive reduction set about a P-Anchor (ai, bj).

If PA(ai) = {bp}, then PS(ai) = [sub(ai) ⊗ sup(bp)] ∪ [sup(ai) ⊗ sub(bp)]. Here, sup() and sub() represent the super-concepts and sub-concepts respectively, and ⊗ denotes the Cartesian product.

If PA(ai) = {bq, br}, then PS(ai|br) = [sub(ai) ⊗ sup(br)] ∪ [sup(ai) ⊗ sub(br)]. Let mid(bq, br) be the middle concepts on the hierarchy path from bq to br. Since sup(br) = mid(br, bq)∪sup(bq), the above formula can be rewritten as:

Similarly, we obtain:

Therefore,

Let lub(br, bq) and glb(br, bq) be the least upper bound and the greatest lower bound for br and bq, respectively. The above formula can be simplified as follow:

The above analyses can be extended to the general case: given PA(ai) = {b1, b2, ..., bk}, the corresponding reduction set can be calculated by:

Formula (1) indicates that smaller top-k will generate larger PS(ai). In our implementation, top-k is assigned a value from 1 to 4.

The total positive reduction set during matching is:

The positive reduction set is generated dynamically and consists of two parts: (1) Invalid positive reduction set contains all similarity calculations have been computed. Therefore, it is useless for matching; (2) Valid positive reduction set contains all similarity calculations to be computed but can be skipped in matching. Therefore, only valid positive reduction set can improve the performance.

The order of similarity calculations will affect the size of the valid positive reduction set. The ideal order can be determined by following theorem.

Theorem 1 When the order of similarity calculations can divide the hierarchy path L into parts with equal length continually, the P-Anchors can generate the maximum valid positive reduction set with |L| ∗ (|L| - 2) size.

The proof is omitted for the limitation of space. According to theorem 1, when a path with |L| length generates the maximum positive reduction set, one of the order of similarity calculations is L2 , L4 , 3L 4 , L8 , 3L 8 , 5L 8 , 7L 8 , ..., and it will divide the path into equal lengths continually: |L| 2 , |L| 4 , |L| 8 , ....

Algorithm 1 is the large ontology matching algorithm based on P-Anchors (LOM-P). Here, LOMP-Algorithm() is the main function, ComputerSim() matches elements on the hierarchy path recursively, and GetPAnchors() obtains top-k P-Anchors.

Algorithm 1: LOM-P algorithm

Input: ontology O1, ontology O2 Output: matching results 1 Function LOMP Algorithm(O1, O2) 2 begin 3 foreach Li ∈ O1 do 4 ComputeSim(Li) 5 end 6 end 7 Function ComputeSim(L = (a1, a2, ..., an)) 8 begin 9 PA←GetPAnchors( n2 ) 10 PS ←PredictNewPS(PA) 11 ComputeSim(La = (a1, ..., a( n2 -1))) 12 ComputeSim(Lb = (a( n2 +1), ..., an)) 13 if |L| ≤ 1 then 14 return 15 end 16 end 17 Function GetPAnchors(ai) 18 begin 19 foreach bj ∈ O2 do 20 if (ai, bj) ∈ PS then 21 continue 22 end 23 Sim(ai, bj ) ← Compute(ai, bj ) 24 if Sim(ai, bj) > ptV alue then 25 PACandi ← PACandi ∪ bj 26 end 27 end 28 PA←MaxTopk(PACandi) 29 end

The time complexity of LOM-P algorithm is analyzed as follows. Given two matched ontologies, if all concepts are on a hierarchy path, the matching process can generate n(n-2) size valid positive reduction set, and it just needs 2n similarity calculations, i.e., the algorithm has the best time complexity O(2n). However, such ideal case almost does not exist in real world. Suppose there are m hierarchy paths, then the average depth of the ontology is ¯ d = nm . Consequently, we can derive the time complexity of Algorithm 1 is O((1 - 1m )n2 ) = O((1 - ¯ dn )n2 ). It means that LOM-P algorithm can improve the matching performance when the ontologies have large average depths.

4.2 LOM-N: Large OntologyMatching Algorithm Based on N-Anchors

N-Anchors are also able to predict ignorable similarity calculations. The set of all ignorable similarity calculations predicted by N-Anchors are called the negative reduction set. Let Nb(ai) = {ax|d(ax, ai) <= nScale} be the neighbors with nScale distance to ai. Therefore, the negative reduction set generated by ai is:

According to formula (3), NA(ai) will be propagated to neighbors of ai. Such propagation will lead to low credible negative reduction set because it will improve the risk of missing right similarity calculations. Fig. 2. interprets the potential risk. Let NA(ai) = Ns+Np and NA(aj) = Np+Nq. If we first calculate the similarities about ai, then aj will get NA(ai). Therefore, we will skip the similarity calculations between aj and Ns, which would miss correct alignments like (aj, bx)(bx ∈ Ns). Therefore, Ns is a potential risk for similarity calculations about aj .

To reduce such risk, we introduce three constraints on the negative reduction set.

Constraint 1: All N-Anchors must be obtained in similarity calculating. This means that N-Anchors propagated from neighbors cannot be propagated again. In Fig. 2, NA(aj) consists of two parts: Np is propagated from ai and Nq is obtained in calculating similarity about aj. Only Nq can be propagated to other neighbors.

Constraint 2: All N-Anchors of ai can only be propagated to the neighbors in the semantic subgraph of ai. We call this constraint the SSG constraint. Constraint 2 further restricts that N-Anchors can only be propagated to neighbors with close semantic relations to ai.

Constraint 3: All N-Anchors of ai can be propagated only if the description document of ai contains more than t items. we call this constraint the SDD constraint. It means that if an element lacks of enough literal information in matching, its N-Anchors may be incorrect and cannot be propagated. In the implementation, we set t = 8.

Algorithm 2: LOM-N algorithm

The order of similarity calculations would also influence the size of negative reduction set. In order to generate the maximum valid negative reduction set, the elements with more neighbors should be calculated first during matching.

Algorithm 2 is the large ontology matching algorithm based on P-Anchors (LOM-P). All concepts are sorted by their degrees (line 2). If a similarity s is smaller than ntV alue and satisfies three constraints (line 9), a N-Anchor (line 10) is used to get the negative reduction set (line 12). The valid negative reduction set is obtained after refined (line 13). The time complexity of the algorithm is O((1 - wλ)n2 ), where w is the average degree and λ is determined by ntV alue and constraints. The bigger w and λ, the higher performance the algorithm has.

4.3 LOM-Hybrid: Hybrid Large Ontology Matching Algorithm

We use a hybrid algorithm, called LOM-Hybrid, to combine the LOM-P and LOM-N algorithms to obtain as large valid reduction set as possible. The LOM-Hybrid algorithm will prefer the matching order of LOM-N algorithm for two reasons: (1) Since the average depth of a real ontology is often small, LOM-P may not have the ideal high performance. (2) LOM-N algorithm first calculates the elements with large degree, it can be benefit for the LOM-P algorithm. Therefore, the LOM-Hybrid algorithm is mainly based on the framework of the LOM-N algorithm, in which the LOM-P algorithm is embedded. LOM-Hybrid can generate the valid positive reduction set and valid negative reduction set. Theoretically, the time complexity of LOM-Hybrid is between the complexity of LOM-N and the complexity of LOM-P. Indeed, it is very close to LOM-N. The LOM-Hybrid algorithm is omitted here for the space limitation.

5 Experimental Evaluation

5.1 Data sets

Two data sets are used in the experiments:

• Dataset1 consists of five middle scale ontology pairs (russia12, russiaAB, russiaCD, tourismAB, and sport), which are selected from FOAM 2 . These ontologies have 103-474 concepts and 22-100 properties, and will be used to examine the correctness of our algorithms.
• Dataset2 is the real large scale ontology set in OAEI2008, i.e. Anatomy, Fao, and Library. These ontologies have 2000-30000 concepts, and will be used to examine the performance of our algorithms.

5.2 Experiments for examining the algorithms

Besides Precision, Recall, and F1-Measure, we also introduce the Loss to measure the quality loss in LOM algorithms:

where Fgold is the F1-measure of a general ontology matching (GOM) algorithm provided by the matching system Lily 3 , and Fget is the F1-measure of our LOM algorithms.

As shown in Table 1, we have following observations: (1) Three LOM algorithms perform well on middle ontologies.

2 http://www.aifb.uni-karlsruhe.de/WBS/meh/foam/ontologies.htm

3 http://cse.seu.edu.cn/people/pwang/lily.htm

(2) LOM-P, LOM-N and LOM-Hybrid have similar performance, which can be generally sorted by: LOM-P≥LOMHybrid≥LOM-N. (3) Compared with GOM algorithm, three LOM algorithms have a certain quality loss. The average Loss of LOM-P, LOM-N and LOM-Hybrid are 0.4%, 4.8% and 4.4%, respectively. We set LOM-Hybrid as the standard LOM algorithm in remaining experiments, because it not only combines other two algorithms, but also has a close running time to LOM-N.

We also compare the LOM-Hybrid with other matching system using DC method. We select Falcon-AO as the comparing system, whose matching method called PBM. As shown in Fig. 3, LOM-Hybrid has a similar performance to PBM.

5.3 Real large ontology matching experiments

Here we present results of our LOM algorithms on three LOM tasks (Anatomy, Fao, and Library) in OAEI2008.

Anatomy task requires matching two ontologies with 2700 and 3300 concepts. There are 13 systems that participate in the anatomy task, but only few systems use the special large ontology matching method. The TaxoMap uses the PBM algorithm of Falcon-AO. We employ the Recall+ [Caracciolo et al.2008] to measure how many non trivial correct alignments can be found. From Table 2, we can see that: (1) LOM-Hybrid can also perform well in Anatomy task. Indeed, it outperforms than some systems using background knowledge. (2) LOM-Hybrid and Falcon-AO have similar performance, which are better than TaxoMap. (3) The running time of LOM-Hybrid is 13 minutes. It indicates that our LOM algorithms have similar running time to other systems using DCmethods. (4) Our method and Taxomap have a high Recall+, indicating that they have the ability to discover the difficult alignments.

Library task contains two ontologies with 5000 and 35000 concepts. Fao contains several ontologies with 2000 to 10000 concepts. As Fig. 4 shows, our method can discover the alignments for the two tasks.

5.4 Performance experiments

There is a need to analyze the influence of key parameters to our algorithms. Here we use a new metric G called benefit rate to measure how much a LOM algorithm can improve the performance: G = N n1×n2 , where N is the size of total reduction set, n1 and n2 represent the number of concepts in two ontologies. The larger G is, the fewer times of similarity calculations and the higher efficiency of the algorithm has. Although we use Dataset1 to perform the following experiments, it should be noted that similar conclusions can be obtained from other datasets.

top-k is a key parameter in LOM-P. We need to know the influence of different top-k values to the quality of results and efficiency. Our experimental results show that there is a small variation of matching results when top-k changes from 1 to 4. This result can be explained that most elements only have very few P-Anchors. Since ontologies in Dataset1 have short hierarchy pathes, LOM-P just gets about 5% benefit rate.

LOM-N algorithm has four important parameters: ntV alue, nScale, SDD constraint and SSG constraint. We evaluate these parameters on the TourismAB of Dataset1.

Fig. 5 shows the relation of ntV alue to F1-Measure on different nScale. Fig. 6 shows the relation of benefit rate to ntV alue under different nScale. We observe that: (1) ntV alue has a significant effect on matching quality and efficiency, i.e., larger ntV alue will lead to lower matching quality, meanwhile, it also causes higher benefit rate. (2) nScale also affects the matching quality and efficiency. As nScale increases, matching quality will decrease, but the benefit rate will increase. Results also show that ntV alue < 0.02 and nScale = 2 will lead to a good matching quality and benefit rate. Fig. 7 and Fig. 8 show the influences of SDD and SSG on matching quality and benefit rate. The line with rectangle represents the results without any constraint. We can see that: (1) Under three constraints, the matching quality will increase, but the benefit rate decreases. (2) SSG constraint has a higher influence on matching quality and benefit rate.

Figure 8: SDD - SSG - benefit rate

6 Conclusion

This paper proposes a new efficient large ontology matching method based on reduction anchors. Reduction anchors are used to predict the ignorable similarity calculations in matching. Our experimental results show that the proposed method is effective for matching large ontologies.

Acknowledgments

The work is supported by the NSF of China (61003156 and 90818027), the National High Technology Research and Development of China (863 Program) (2009AA01Z147), and the Major State Basic Research Development Program of China (973 Program) (2009CB320703)