Many existing ontology matching tools are not well scalable. In this paper, we present the Malasco system, which serves as a framework for reusing existing, non-scalable matching systems on large-scale ontologies. The results achieved with di erent combinations of partitioning and matching tools are discussed, and optimization techniques are examined. It is shown that the loss of result quality when matching with partitioned data can be reduced to less than 5% compared to matching with unpartitioned data.
The need for matching large-scale ontologies arises in di erent elds. In electronic
business, several large ontologies representing business standards are in use [
To the best of our knowledge, there are only three works which explicitly
address the scalability issue: The schema matching system COMA++ [
The business pair of only be processed by COMA++ and Falcon-AO. The larger medical pair could not be processed by any of the tools examined. Most of the tools su ered from a lack of memory. These experiments show that matching large ontologies is a severe problem with many of the tools that are currently available. 3
The system introduced in this paper is called Malasco (Matching large scale ontologies). It allows matching large-scale ontologies by rst partitioning the input ontologies. The actual matching is then carried out on the smaller partitions. 3.1
This approach has also been implemented in COMA++ and Falcon-AO. Unlike those systems, our implementation follows a more modular design, which allows the use of di erent existing systems both for partitioning and for matching the partitions. This approach has several advantages: { Existing matching and partioning tools can easily be reused. This lowers the e ort of setting up a matching solution and o ers the possibility to bene t from future developments without having to modify the system. { Di erent matching tools provide results of various quality, depending on the nature of the input ontologies. Therefore, building a system that can work with di erent matching tools is a promising approach for creating a versatile tool. { From an academical point of view, the approach allows experiments on different combinations of partitioning and matching tools. 3.2
As a simple partitioning approach, we implemented a naive baseline algorithm
which iterates over the RDF sentences [
The Malasco system has been evaluated in two respects: the ability to process large-scale ontologies, and the quality of the matching results achieved. 4.1
To demonstrate that our system is capable of matching large-scale ontologies, we used the test ontologies and test environment described in section 2. As an example, we used the baseline algorithm with a maximum partition size of 5,000 statements and the INRIA matching system. Our system could process both pairs; the largest amount of time { more than 100 times longer than the rest of the process { was consumed by the pairwise matching of partitions. 4.2
While it is obvious that element-based matching algorithms can be run on partitions of the input ontologies with unchanging results (given a covering partitioning), most matching systems are structure-based and will thus produce di erent (and probably worse) results on partitioned data. To evaluate how big the loss of quality is when working on partitioned data, we ran the example matching tools both on unpartitioned and on partitioned ontologies and compared the results. Since the matching tools examined can only work on smaller-scale ontologies, such a comparison is only possible on smaller-scale data sets.
Six pairs of ontologies of a size between 600 and 2,000 statements were used
for evaluation. For partitioning, we used two variants of the baseline algorithm
(with 250 and 500 statements as a maximum), two variants of the islands
algorithm (with 50 and 100 classes per island as a maximum), the "-connections
algorithm1, and the unpartitioned ontologies for comparison. For pairwise matching
of the partitions, we used INRIA [
To evaluate the results, we calculated recall, precision, and F-measure. While the recall value achieved on partitioned data is as high as (and in some cases even slightly higher than) the result on unpartitioned data, the precision value is less than 50% than that achieved on unpartitioned data, caused by a very high number of false positives. 4.3
To achieve better results, in particular better precision values, we tested two optimization approaches. The rst one is motivated by the insight that structurebased matching approaches use information on neighboring elements. For partioned ontologies, those are missing for elements on the border of a partition. Hence, for the rst optimization approach, we added the direct neighbors for each concept contained in a partition, thus creating overlapping partitions. The matching is then performed on the overlapping partitions. Mapping elements found between the neighboring elements are discarded, because the matching algorithm only has partial information about those elements.
When using overlapping partitions, it can be observed that using
overlapping partitions causes a signi cant improvement of the precision value (the loss
1 For the "-connections algorithm, various problems can be observed [
The second approach to improve our system's results' quality is the use of a
lower threshold. As most matching system provide a con dence parameter with
each mapping element, a lower threshold can be employed to discard all elements
with a con dence value below that threshold in order to improve the results [
To determine an optimal lower threshold , we calculated precision, recall, and F-measure for threshold values between 0 and 1 and determined the average optimal (w.r.t. F-measure) threshold values for each partitioning algorithm, including the unpartitioned case for comparison.
Thresholding the results leads to a signi cant improvements in precision and F-measure. Fig. 1 shows the results using the matching system FOAM2. The improvement is stronger than using overlapping partitions, more than 95% of the F-measure achieved on unpartitioned data can be reached (even up to 99% for INRIA). Applying a lter which is optimal for a given partitioning technique leads to almost the same results, thus, the choice for an actual partitioning algorithm is of marginal e ect.
Using the thresholding optimization is less costly than using overlapping partitions: the matching system does not have to work on larger partitions, and the runtime complexity of applying the threshold is only linear in the number of results. Combining both overlapping partitions and thresholding leads only to 2 The results with INRIA were in most of the cases comparable to those achieved with
FOAM and are therefore not shown separately. minimal improvements (less than 5%) compared to thresholding alone. Since using overlapping partitions is rather costly, thresholding alone is the more approriate approach in most usage scenarios. 5
In this paper, we have presented the Malasco framework which allows using existing matching tools for matching large-scale ontologies. Its modular architecture allows for using arbitrary partitioning and matching tools, including domain-speci c tools for particular matching tasks.
In our evaluation, we have shown that our system is actually capable of matching large ontologies, that the choice of a particular partitioning algorithm is only of minor importance, and that the quality deviation compared to the results which would be achieved on the unpartitioned ontologies (given a matcher that could process them) can be reduced to less than 5%.
The author would like to thank the members of the e-business integration group at Hochschule Darmstadt and the members of the knowledge engineering group at TU Darmstadt for their valuable and helpful remarks.