Since the high time and space complexity, most existing ontology matching systems are not well scalable to solve the large ontology matching problem. Moreover, the popular divide-and-conquer matching solution faces two disadvantages: First, partitioning ontology is a complicate process; Second, it will lead to loss of semantic information during matching. To avoid these drawbacks, this paper presents an e cient large ontology matching system Lily-LOM, which uses a non-partitioned method. Lily-LOM is based on two kinds of reduction anchors, i.e. positive and negative reduction anchors, to reduce the time complexity problem. Some empirical strategies for reducing the space complexity are also discussed. The experiments show that Lily-LOM is e ective.
Since high time and space complexity, most ontology matching systems cannot deal with large ontology matching (LOM) problem. First, matching process requires a large amount of memory space, which would cause the system to crash due to the out of memory error. The space complexity of a matching system usually is O(n2). Second, most ontology matching algorithms are O(n2) time complexity, i.e. it needs n2 times similarity calculations.
Divide-and-conquer strategy is a feasible solution for LOM problem. However, it also has two main issues to be resolved. First, we notice that some ontology partitioning approach cannot control the size of blocks, which may be too small or too large for matching. Second, the ontology partitioning idea also would cause another considerable issue, namely, the partitioning would make the elements on the boundaries of blocks lose some semantic information, that would in turn a ect the quality of nal matching results.
This paper presents Lily-LOM, a system for matching large ontologies, which is based on a non-partitioned method. Compared with the existing work, LilyLOM has two distinct advantages: First, it needs not to partition large ontologies but it also has the high performance. Second, it is a general solution for LOM problem, namely, it can adopt most existing matching techniques.
During matching large ontologies, we notice two interesting facts: (
In Fig. 1. (a), if high similarity values exist between ai and bp or bq, we can decide that ai matches bp or bq. This decision will bring a direct bene t: the subsequent similarity calculations between sub-concepts(/super-concepts) of ai and super-concepts(/sub-concepts) of bp or bq can be skipped. This paper calls such concept pairs like (ai; bp) the positive reduction anchors(P-Anchors), which employ ontology hierarchy feature to reduce the time complexity in LOM.
O1 ai
O2 bp br bq bx bs
O1
D0 ai
O2
D1 D2 bx (a) Positive Reduction Anchor
(b) Negative Reduction Anchor sup(lub(b1; :::; bk))] [ [sup(ai) sub(glb(b1; :::; bk))]
We can prove that when the order of similarity calculations can divide the hierarchy path L into equal parts continually, the P-Anchors can generate the Lily-LOM: An E cient System for Matching Large Ontologies maximum valid positive reduction set with jLj (jLj 2) size [1]. It means the algorithm has the best time complexity O(2n). Generally, the algorithm has O((1 nd )n2) time complexity, where d is the average depth of the ontology.
N-Anchors can also predict the ignorable similarity calculations, which are called the positive reduction set. If (ai; bj ) is a N-Anchor, we can predict that neighbors of ai are also irrelevant to bj . The set of all ignorable similarity calculations predicted by this way are called the negative reduction set.
Let N A(ai) refer to the N-Anchors about ai, the neighbors with nScale distance to ai constitute a set N b(ai) = faxjd(ax; ai) <= nScaleg, the negative reduction set generated by ai is:N S(ai) = N A(ai) N b(ai). The time complexity of the algorithm is O( n2), where is in [0; 1] and is determined by size of negative reduction set. 3
Besides the time complexity, the space complexity is another challenge in LOM. We present some empirical methods for handling the space complexity problem, and it may be useful for other matching systems. The number of elements in large ontology is large, so we should avoid allocating a n n similarity matrix. Considering the similarity matrix is a typical sparse matrix, it can adopt the compression techniques to replace it. It usually compresses a similarity matrix into several MBs. In our LOM algorithms, the size of reduction set will become bigger and bigger, which takes a large amount of space. We rst replace the two dimension reduction set with one dimension style, then merge the continuous number of elements as a link. Memory space resource is valuable in LOM, so if a variable or a data structure is unused, we should free its space immediately. This principle will reduce the possibility of out of memory error. 4
All algorithms proposed in this paper are implemented in ontology matching system Lily-LOM. More information about Lily can be found at http://cse.seu.edu .cn/people/pwang/lily.htm.
We get some matching results on several real large ontologies by participating in OAEI1. Here we present the results of our LOM algorithms on three LOM tasks (Anatomy, F ao, and Library) in OAEI2008.
From 2007 to 2008 years, there are 13 systems participated in the anatomy task, but only three systems: Lily, Falcon-AO, and TaxoMap, used the special large ontology matching method. Falcon-AO proposed a divide-and-conquer method called PBM algorithm. TaxoMap uses the PBM algorithm, so it is a re-implement of PBM. We measure quality of the results with the classic F1measure, and use Recall+ [2] to measure how many non trivial correct alignments can be found.
Table 1 shows the results of three LOM systems. According to the results,
we have four conclusions: (
The results of Lily on the Library and Fao tasks are showed as Fig. 2, which also demonstrates that it can discover some alignments in the two tasks. 5
This paper present a system Lily-LOM, which proposes a new large ontology matching method based on reduction anchors. The reduction anchors are useful to predict the ignorable similarity calculations during matching, that can reduce the high time complexity problem.
This research is supported by the National Natural Science Foundation of China (61003156).