Jens Lehmann

Prateek Jain

Jérôme David

Jérôme Euzenat

François Scharffe

Cássia Trojahn

Dos Santos

Keywords: Alignment API, Ontology matching, Ontology alignment, Alignment management, Alignment evaluation, Alignment language, EDOAL, Ontowrap, OntoSim

Alignments represent correspondences between entities of two ontologies. They are produced from the ontologies by ontology matchers. In order for matchers to exchange alignments and for applications to manipulate matchers and alignments, a minimal agreement is necessary. The Alignment API provides abstractions for the notions of network of ontologies, alignments and correspondences as well as building blocks for manipulating them, such as matchers, evaluators, renderers and parsers. We recall the building blocks of this API and present here the version 4 of the Alignment API through some of its new features: ontology proxys, the expressive alignment language EDOAL and evaluation primitives.

Motivation

Using ontologies is the privileged way to achieve interoperability among heterogeneous systems within the semantic web. However, as ontologies are not necessarily compatible, they may in turn need to be reconciled. Ontology reconciliation often requires to find the correspondences between entities, e.g., classes, objects, properties, occurring in these ontologies.

Alignments are sets of correspondences between elements of two ontologies [START_REF] Euzenat | Ontology matching[END_REF]. They are generated by hand or by ontology matchers and they can be used for merging ontologies, transforming queries or linking data sets. During their life cycle, alignments may be written in files and further read, applied various thresholds, merged together and finally transformed into a more operational format.

Considering ontology alignments as first class citizens has several benefits: 1 Partial support provided by European Network of Excellence Knowledge web (FP6-IST-507482).

* Corresponding author. E-mail: Jerome.Euzenat@inria.fr -from a semantic web point of view, as it is possible to dynamically find and reuse existing alignments; -from a software engineering point of view, as alignments can be passed from a program to another; -from an ontology engineering and management point of view, as they will evolve together with the ontology life cycle.

In order for alignments produced by any means to be treated uniformly and for matchers and applications to consume and produce such alignments, we designed a Java API for alignments: the Alignment API [START_REF] Euzenat | An API for ontology alignment[END_REF].

The Alignment API is a set of abstractions for expressing, accessing and sharing ontology alignments. Its reference implementation provides a minimal implementation of this interface. It aims at facilitating the development of tools manipulating alignments and calling matchers. It is also a way for matcher developers to deliver alignments in a well-supported framework.

We describe in this paper the version 4.0 of the Alignment API which has been deeply enhanced since its first version in 2003. We emphasise those new fea-0000-0000/11/$00.00 c 2011 -IOS Press and the authors. All rights reserved tures which were not available for [START_REF] Euzenat | An API for ontology alignment[END_REF]. After describing the API itself ( §2), we describe more precisely areas of major enhancement, such as the abstraction from ontologies and concrete measures ( §3), the development of an expressive alignment language ( §4) and the evaluation of alignments ( §5).

The Alignment API in a nutshell

The Alignment API itself is a reduced set of Java interfaces. The most important parts of the API are the representation interfaces which provide access to information about the API elements. These interfaces are first presented before considering the process interface and the reference implementation of the API.

Representation classes

The Alignment API offers four main representational classes whose structure is represented in Figure 1.

OntologyNetwork is a container for a set of ontologies and a set of alignments. It makes it easy to retrieve alignments tied to an ontology as well as to manipulate them as a network, i.e., traversing them, closing them, etc.

Alignment is the main class of the API. An Alignment is mostly made of a set of Cells and metadata about the alignment, such as the aligned ontologies, the alignment arity, provenance metadata, and any other metadata that can be tied to an alignment.

Cell represents a correspondence: it relates two entities with a Relation. The entities may be any identified element of an Ontology (see §3) or any construct from the expressive EDOAL language (see §4). In addition, Cell supports any type of additional metadata (including confidence values).

Relation represents the relation between two entities. The set and type of relations are extensible in the Alignment API and its implementation.

These classes provide access to the information in instances. They also provide local methods for manipulating this information: adding correspondences to alignments, cutting correspondences under a confidence threshold, etc.

An RDF vocabulary and an RDF/XML format, corresponding to the Alignment class, can be used for serialising alignments.

Processing

In addition to being a storage structure, the Alignment API provides a minimal processing structure, which can be used by applications for manipulating and consuming alignments. We present its most important classes:

AlignmentProcess is the interface for all matchers.

Matching two ontologies is achieved in two steps: creating an instance of an Alignment implementing AlignmentProcess and initialising it with two Ontology instances, then calling the align() method. This method takes two arguments: an initial Alignment which may be considered by the matcher and a Property object providing parameters for the matcher.

Evaluator is the interface for alignment evaluators which compare a first Alignment which may be taken as the reference and a second Alignment (see §5).

AlignmentVisitor or Renderer is the interface for defining Alignment visitors which can output alignments in different formats, when calling the render() method of Alignment. These operations are presented in Figure 2. vides, for each class of the API, a basic implementation and offers the following services:

API implementation

-Storing, finding, and sharing alignments; -Piping matching algorithms (improving an existing alignment); -Manipulating alignments (trimming under a threshold, merging, inverting, and hardening); -Generating processing output (transformations, axioms, rules); -Comparing alignments (finding differences). Thus, to quickly instantiate the API, it is sufficient to refine this basic implementation. This will take advantage of all the services already implemented in the base implementation. It is also possible to define completely new implementations of the API. The benefit of this is that such an implementation could still be used by the tools which rely on the Alignment API.

The API implementation also provides more precise implementations. They must be considered as examples, such as simple concrete matching methods (e.g., StringDistAlignment and all derivates of DistanceAlignment), or as fully implemented utilities, such as the provided Renderers or Evaluators. More precisely, the Alignment API implementation comes with:

a base implementation of the interfaces with many useful facilities; -a library of sample matchers; -a library of renderers (for RDF, XSLT, SWRL, OWL, C-OWL, SEKT Mapping Language, SKOS, HTML); -a library of evaluators (see §5); -a library of wrappers for several ontology APIs (see §3);

Finally, the API implementation provides tools for manipulating alignments, such as the batch utilities described in §5 or the AlignmentParser which can parse an RDF file in the Alignment format, or the EDOAL extension of this format (see §4), and return the corresponding Alignment.

Abstract support for ontologies and distances

The implementation of the Alignment API relies on two external abstractions that we describe below:

Ontowrap provides uniform access to part of ontology APIs useful for matchers; OntoSim provides various distance and similarity measures. It relies on Ontowrap.

Ontowrap

There are many different APIs for ontologies. Even if the Alignment API is independent from these APIs, it is often convenient to interact with them, in particular when one wants to match ontologies. For that purpose, we have designed the Ontowrap API which encapsulates interactions with ontology APIs. The architecture of Ontowrap has been designed to be easily extensible to other ontology APIs.

The Ontowrap package defines the abstract factory

OntologyFactory which is used for generating ontologies. Depending on the level of interaction needed with the ontologies, the factory may provide three levels of ontology interfaces, each one extending the previous one:

Ontology simply provides information about an ontology: its URI, its URL and eventually its knowledge representation formalism (OWL, SKOS, etc.). Since, this interface does not assume that the ontology has been loaded, it does not offer access to the information about entities (classes, properties, individuals).

LoadedOntology provides access to an ontology that has been loaded in main memory. However, the interaction with the API is still limited. It allows for retrieving the entities and provides their type (class, property, individual), URI, labels and comments. This interface is easy to implement and applies to ontologies as well as to "lightweight" ontologies, such as unstructured thesauri.

HeavyLoadedOntology offers a broader access to an ontology by obtaining the relations between entities (subsumption and other properties), the classes of individuals, and the domain and range of properties.

For each major ontology API, a concrete factory and at least one Ontology, LoadedOntology or HeavyLoadedOntology implementation is provided.

Ontowrap offers implementations for the major ontology APIs: OWL-API [START_REF] Bechhofer | Cooking the semantic web with the OWL API[END_REF], Jena OWL API [START_REF] Carroll | Jena: implementing the semantic web recommendations[END_REF], the SKOS API [START_REF] Jupp | A flexible API and editor for SKOS[END_REF], and our own SKOSLite loader.

The HeavyLoadedOntology interface

One problem with HeavyLoadedOntology implementations is that the various APIs do not return the same set of entities to a seemingly same question. For instance, consider the getSuperClasses(aClass) method. It is a simple method which returns the superclasses of a class. But there are many ways of defining these superclasses:

-Direct superclasses, those superclasses which have no other superclass as subclass (classes part of the transitive reduction of the superclass relation). -Named superclasses, i.e., only those which are identified by a URI (in the OWL model, any restriction is a class and can be a superclass). -Asserted superclasses, i.e., those classes which have been explicitly asserted to be superclasses in the ontology description.

As Figure 3 shows, these three dimensions are orthogonal, i.e., one can pick up any combination of these three modalities and provide a different answer to the question. In addition, they can be refined:

-Named superclasses can be restricted to Local superclasses, i.e., those which are defined in the same name space as the ontology. -Unasserted superclasses can be taken within those superclasses that can be obtained by limited reasoning methods like Inherited superclasses obtained only by transitive closure computation. -Unnamed superclasses may be restricted to those Mentioned in the ontology (a property restriction appearing explicitly in the ontology) or to any of such restrictions, their number can be infinite.

To deal with this heterogeneity, the methods querying relations between entities take these 3 dimensions as parameters and Ontowrap will try to satisfy them as far as possible. It also includes the getCapabilities(direct, asserted, named) method to check beforehand if the API meets the requirements of the application and to raise an exception if this is not the case.

OntoSim

OntoSim is an API dedicated to the computation of similarities between ontologies and ontology entities. It provides measures used for matching ontologies and supports the development of new measures. In particular, it provides methods for aggregating similarity matrices:

aggregation schemes allowing for summarising a set of values in a single one; -extractors for selecting a subset of values in a matrix according to several strategies: maximum weight graph matching, Hausdorff, average linkage, etc.

It also comes with a set of distances (string, objects, collections) and a wrapper for the secondstring package [START_REF] Cohen | A comparison of string metrics for matching names and records[END_REF].

EDOAL: an expressive alignment language

The basic Alignment API implementation [START_REF] Euzenat | An API for ontology alignment[END_REF] originally linked only named entities. This is not sufficient when one wants to express relations between groups of such entities. This is especially a problem if the ontology language is not very expressive, e.g., thesauri languages.

The EDOAL language (Expressive and Declarative Ontology Alignment Language) extends the Alignment format in order to capture more precisely correspondences between heterogeneous ontological entities [START_REF] Euzenat | Expressive alignment language and implementation[END_REF]. To achieve this, EDOAL includes a set of constructors and operators to be used for expressing the entities in the Alignment format.

For example, let us consider two ontologies: v(in) having a concept Bordeaux and w(ine) having a concept Wine. While a simple subsumption correspondence between the two concepts, Bordeaux ≤ Wine, is valid and can be expressed in the initial Alignment format, a more precise correspondence would consider only those wines whose terroir is located in the "Aquitaine" region: Wine ∧ hasTerroir•locatedIn = "Aquitaine" ≥ Bordeaux (see Figure 4). This language seems to be heavily related to OWL and indeed it has many features of it. One of the main reason for not simply adopting OWL was to not commit to a particular ontology language. Moreover, there are various differences which made us preserve an OWL-like syntax while not simply adopting OWL itself:

-EDOAL is less than OWL: it does not allow for defining new named entities, which is arguably one of the main features of OWL. -EDOAL is more related to a rule language than to OWL by introducing variables within expressions, which are used for defining constraints and transformations. Moreover, the relation in correspondences has to be independent from the ontology language, although it is possible to render it with OWL relations, such as owl:subClassOf. -EDOAL contains additional constructions for expressing data transformation.

However, we tried to keep it as close as possible to OWL. Indeed, EDOAL is largely inspired by constraints provided in description logics or in the OWL language. It allows for grouping the basic named entities found in ontologies (classes and properties) with classical boolean operators (disjunction, conjunction, complement) or property construction operators (inverse, composition, reflexive, transitive and symmetric closures) and constraints (through domain, range, cardinality and value restrictions). The syntax corresponding to the example of Figure 4 Moreover, EDOAL is also able to express transformations, e.g., unit transformations, between entities. For that purpose, correspondences may contain transformation elements and EDOAL allows for defining variables used to denote parts of the matched entities in transformations.

Although, there are few matchers able to generate such elaborate alignments, the need to represent them for the purpose of complex manipulation, e.g., linked data link generation, is increasing. First attempts towards complex ontology matching [START_REF] Ritze | A pattern-based ontology matching approach for detecting complex correspondences[END_REF] use a refinement step to go from equivalence or subsumption matches to more complex correspondences. The work on alignment patterns [START_REF] Scharffe | Correspondence patterns for ontology mediation[END_REF] also uses EDOAL to solve ontology mismatches.

EDOAL support is still under development in the Alignment API 4.0: there is no specific evaluator and only RDF and OWL renderers are available.

Evaluating alignments

The Alignment API provides support for alignment evaluation. Such an evaluation is usually carried out by comparing the alignments provided by matchers with a reference alignment. The quality of the alignment can be assessed with the help of some measure.

The most commonly used and understood measures are precision (true positive/retrieved) and recall (true positive/expected) which have been adapted for ontology matching by considering alignments as mere sets of correspondences.

The Alignment API defines the Evaluator interface for evaluation purposes. This interface specifies the eval() method that runs the evaluation between two alignments. It is then possible to access the results of this evaluation through specific accessors or by printing results.

The implementation of the API provides a Basic-Evaluator, which can be used as a basis for specific evaluators and a GraphEvaluator whose result is not a number but a curve. Several Evaluator implementations are available with the API:

PRecEvaluator implements the classical precision/recall evaluation as well as the derived measures (Fmeasure, fallout, overall) [START_REF] Do | Comparison of schema matching evaluations[END_REF].

SymMeanEvaluator implements a weighted symmetric difference between the entities that are in one alignment and those common to both alignments (missing correspondences count for 0., others weight 1. complemented by the difference between their strengths). This is a measure of the similarity of two alignments. The result is split between the kinds of entity considered (class/property/individual).

ExtPRecEvaluator implements relaxed precision and recall as defined in [START_REF] Ehrig | Relaxed precision and recall for ontology matching[END_REF]. They replace the count of true positive by a similarity measure between the two alignments which may count a correspondence as not fully incorrect when it is close to an expected correspondence but not identical. This provides higher values for precision and recall based on the proximity of obtained results with expected results. This class provides three flavours of relaxed measures: symmetric, effortbased and oriented. The symmetric measure considers how far two matched classes are in the hierarchy; the effort-based measure tries to weight the effort required to correct an erroneous correspondence; and the oriented measure considers the way incorrect correspondences affect the correctness of a particular task to be carried out with the alignment.

SemPRecEvaluator implements semantic precision and recall as defined in [START_REF] Euzenat | Semantic precision and recall for ontology alignment evaluation[END_REF] based on the Pellet rea-soner [START_REF] Sirin | Pellet: a practical OWL-DL reasoner[END_REF] (or any OWLReasoner implementation). Instead of syntactically comparing correspondences, this measure checks if each correspondence of one alignment is entailed by the other one. This is useful because returned alignments may have a different form than the reference alignment and yet be equivalent to it.

The Alignment API implementation offers a set of services for carrying out evaluation based on the AlignmentProcess and Evaluator classes. The Group-Align class allows for batch matching of pairs of ontologies. From a directory containing a set of subdirectories, each one containing a pair of ontologies, it will run a particular matcher and deliver an alignment in each directory. This is useful when matching many pairs of ontologies for evaluation purpose.

A corresponding utility (GroupEval) implements batch evaluations. When the reference alignment is in the same directory structure, GroupEval iterates each subdirectory and evaluates the alignments using an Evaluator implementation. It can do this in parallel for the results of several matchers. The output can be provided as comma-separated value, HTML or LaTeX tables.

For plotting, the GenPlot class generates various outputs from such a directory structure. It can output precision/recall graphs (see Figure 5) as gnu-plot files and generates a corresponding Latex file or Google chart API HTML. It can also display other types of graphs, such as Receiver Operating Characteristic (ROC) curves.

These evaluation facilities are largely used within the Ontology Alignment Evaluation Initiative (OAEI) 1yearly evaluation campaigns both by organisers and participants. The Alignment format is used as the result format for OAEI.

Related systems

The Alignment API aims at providing only the basic support for matching and alignment manipulation. It is not a matcher nor an alignment editor. But, we welcome, and would facilitate as much as possible, interface implementation as well as any other embeddings. We have developed a NeOn Alignment plug-in based on the API and it is being integrated within Mondeca's Intelligent topic manager (ITM) tool. There exist tools similar to the Alignment API, but they usually have a different focus.

Several systems have been created as toolboxes for matchers. Their emphasis is rather on supporting matching in an integrated environment rather than on the alignment representation and its sharing over tools. There are "model management" tools like COMA++ [START_REF] Do | COMA -a system for flexible combination of schema matching approaches[END_REF] or ontology managers, such as Protégé in which the Prompt suite [START_REF] Noy | The PROMPT suite: interactive tools for ontology merging and mapping[END_REF] is available. These systems generally come with a rich library of techniques and graphical interfaces for assembling matchers out of these techniques. This is typically what the Alignment API does not offer. These systems do not put the emphasis on sharing the alignments out of their environments like the Alignment API.

A system closer to the Alignment API is FOAM [START_REF] Ehrig | Ontology alignment: bridging the semantic gap, Semantic web and beyond: computing for human experience[END_REF] whose development has been discontinued. For sharing and evaluating alignments, FOAM was relying on the Alignment API. Recently, [START_REF] Van Der Meij | A web-based repository service for vocabularies and alignments in the cultural heritage domain[END_REF] has taken inspiration from the Alignment API in order to share alignments between terminologies.

Finally, Silk [START_REF] Bizer | Silk -a link discovery framework for the web of data[END_REF] is a system similar in spirit but with a different target. Its goal is to express instance matchers in a declarative way. This is not that far from what we would like to do with EDOAL transformations, but SILK goes further in providing distance computation mechanisms within its language.

So, the main advantage of the Alignment API over these systems is to be a standalone and portable library for sharing alignments.

Availability, limitations and impact

The Alignment API is distributed under the LGPL license since December 2003. It can be found at http://alignapi.gforge.inria.fr together with ample online documentation. It is bundled with all required libraries for being immediately usable and tutorials are available for a quick start.

The Alignment API is constantly maintained (20 stable releases since 2003 and continuous source access in our svn server). Over the years, many individuals have contributed to the improvement of the API and are credited from our Credit page.

The Alignment API has encountered a wide diffusion testified by numerous tools using it (we counted more than 30 tools with published papers mentioning the use of the API2 ). Several tools are based directly on the API since it offers a wide range of implemented constructs to start with; other tools simply use the Alignment format as input/output. The Alignment API is used in the Ontology Alignment Evaluation Initiative (OAEI) for data and result processing.

We have embedded the Alignment API within several external tools, such as the NeOn toolkit and our Alignment server (bundled with the API). The Alignment server offers access to the Alignment API through a variety of means including browser interface and web service interface (REST and SOAP).

As far as scalability is concerned, our experience shows that the API implementation itself carries little overhead: it is able to handle alignments of tens of thousands of terms (from large thesauri) with no slow down. We have not investigated more scalability issues because there are hardly larger ontologies at the moment. However, the API is used as well for dealing with instances. Although this is possible, this has never been the primary purpose of this API. It may be more adequate to use a specific tool based directly on secondary memory storage and indexing for dealing with instances and dropping that support from the API.

The interface between instance matching and ontology matching is certainly one of the major limitation of the Alignment API because it has not been designed for dealing with instances. In the near future, we would like to define a clean link with data link generators, like Silk, without giving up our specificity as ontology alignment manager.

Among the planned developments, the issue that will most likely lead to version 5 is the better integration of theoretical developments genericising the relations and confidence to algebra of relations [START_REF] Euzenat | Algebras of ontology alignment relations[END_REF] and ordered structures. It would also be fruitful to better support reasoning with alignments and ontologies.

Conclusion

Alignment representation and manipulation in standard ways are needed in several important areas of the semantic web. We have designed and implemented the Alignment API for addressing this need.

The Alignment API is both an API for representing alignments and for developing, integrating and composing matchers. It comes with a Java implementation which has been used in many developments and provides examples and basic tools for manipulating alignments. It is used by several teams around the world which testify for its usability and usefulness.

The API is gradually improved incorporating bug fixes, extensions (like new standard evaluators and renderers), new features and new components, such as the abstract support for ontology and distances or the EDOAL alignment language which have been presented here.

Fig. 1 .

 1 Fig. 1. Relations between the main classes of the Alignment API and the classes of Ontowrap (Ontology). Only the main attributes and methods are presented.

Fig. 3 .

 3 Fig. 3. The dimensions considered by HeavyLoadedOntology provide for 24 different ways to query sub-/super-classes.

Fig. 4 .

 4 Fig. 4. Restriction on an attribute path value.

Fig. 5 .

 5 Fig.5. Precision/recall graphs for benchmarks. The results given by the participants are cut under a threshold necessary for achieving n% recall and the corresponding precision is computed (values under the bar are mean average precision).

  is:

	<al:Cell rdf:about="bordeauxMap">
	<al:entity1>
	<ed:Class rdf:about="&v;Bordeaux"/>
	</al:entity1>
	<al:entity2>
	<ed:Class>
	<ed:and rdf:parseType="Collection">
	<ed:Class rdf:about="&w;Wine"/>
	<ed:AttributeValueRestriction>
	<ed:onAttribute>
	<ed:Relation>
	<ed:compose rdf:parseType="Collection">
	<ed:Relation rdf:about="&w;hasTerroir"/>
	<ed:Relation rdf:about="≺locatedIn"/>
	</ed:compose>
	</ed:Relation>
	</ed:onAttribute>
	<ed:comparator rdf:resource="&xsd;equals"/>
	<ed:value>
	<ed:Instance rdf:about="&w;Aquitaine"/>
	</ed:value>
	</ed:AttributeValueRestriction>
	</ed:and>
	</ed:Class>
	</al:entity2>
	<al:measure
	rdf:datatype='&xsd;float'>1.</al:measure>
	<al:relation>SubsumedBy</al:relation>
	</al:Cell>

http://oaei.ontologymatching.org

See http://alignapi.gforge.inria.fr/impl. html for reference.


Jérôme Euzenat
email: jerome.euzenat@inria.fr

Alfio Ferrara
email: ferrara@dico.unimi.it

Willem Robert Van Hage

Laura Hollink
email: l.hollink@tudelft.nl

Christian Meilicke

Andriy Nikolov
email: a.nikolov@open.ac.uk

Pavel Shvaiko

Heiner Stuckenschmidt

Ondřej Šváb-Zamazal
email: ondrej.zamazal@vse.cz

Cássia Trojahn
email: cassia.trojahn@inria.fr

Final results of the Ontology Alignment Evaluation Initiative 2011 ⋆

Ontology matching consists of finding correspondences between semantically related entities of two ontologies. OAEI campaigns aim at comparing ontology matching systems on precisely defined test cases. These test cases can use ontologies of different nature (from simple directories to expressive OWL ontologies) and use different modalities, e.g., blind evaluation, open evaluation, consensus. OAEI-2011 builds over previous campaigns by having 4 tracks with 6 test cases followed by 18 participants. Since 2010, the campaign has been using a new evaluation modality which provides more automation to the evaluation. In particular, this year it allowed to compare run time across systems. This paper is an overall presentation of the OAEI 2011 campaign.

Introduction

The Ontology Alignment Evaluation Initiative 1 (OAEI) is a coordinated international initiative, which organizes the evaluation of the increasing number of ontology matching systems [10; 8; 15]. The main goal of OAEI is to compare systems and algorithms on the same basis and to allow anyone for drawing conclusions about the best matching strategies. Our ambition is that, from such evaluations, tool developers can improve their systems.

Two first events were organized in 2004: (i) the Information Interpretation and Integration Conference (I3CON) held at the NIST Performance Metrics for Intelligent Systems (PerMIS) workshop and (ii) the Ontology Alignment Contest held at the Evaluation of Ontology-based Tools (EON) workshop of the annual International Semantic Web Conference (ISWC) [START_REF]Proc. of the Workshop on Evaluation of Ontology-based Tools (EON) collocated with ISWC[END_REF]. Then, a unique OAEI campaign occurred in 2005 at the workshop on Integrating Ontologies held in conjunction with the International Conference on Knowledge Capture (K-Cap) [START_REF]Proc. of the K-Cap Workshop on Integrating Ontologies[END_REF]. Starting from 2006 through 2010 the OAEI campaigns were held at the Ontology Matching workshops collocated with ISWC [9; 7; 2; 5 ; 6]. Finally in 2011, the OAEI results were presented again at the Ontology Matching workshop collocated with ISWC, in Bonn, Germany 2 .

Since last year, we have been promoting an environment for automatically processing evaluations ( §2.2), which were developed within the SEALS (Semantic Evaluation At Large Scale) project 3 . This project aims at providing a software infrastructure for automatically executing evaluations, and evaluation campaigns for typical semantic web tools, including ontology matching. Several OAEI data sets were evaluated under the SEALS modality. This provides a more uniform evaluation setting.

This paper serves as a synthesis to the 2011 evaluation campaign and as an introduction to the results provided in the papers of the participants. The remainder of the paper is organized as follows. In Section 2, we present the overall evaluation methodology that has been used. Sections 3-6 discuss the settings and the results of each of the test cases. Section 7 overviews lessons learned from the campaign. Finally, Section 8 outlines future plans and Section 9 concludes the paper.

General methodology

We first present the test cases proposed this year to the OAEI participants ( §2.1). Then, we discuss the resources used by participants to test their systems and the execution environment used for running the tools ( §2.2). Next, we describe the steps of the OAEI campaign ( §2.3-2.5) and report on the general execution of the campaign ( §2.6).

Tracks and test cases

This year's campaign consisted of 4 tracks gathering 6 data sets and different evaluation modalities:

The benchmark track ( §3): Like in previous campaigns, a systematic benchmark series have been proposed. The goal of this benchmark series is to identify the areas in which each matching algorithm is strong or weak. The test is based on one particular ontology dedicated to the very narrow domain of bibliography and a number of alternative ontologies of the same domain for which reference alignments are provided. This year, we used new systematically generated benchmarks, based on other ontologies than the bibliographic one. The expressive ontologies track offers real world ontologies using OWL modeling capabilities: Anatomy ( §4): The anatomy real world case is about matching the Adult Mouse Anatomy (2744 classes) and a part of the NCI Thesaurus (3304 classes) describing the human anatomy. Conference ( §5): The goal of the conference task is to find all correct correspondences within a collection of ontologies describing the domain of organizing conferences (the domain being well understandable for every researcher). Additionally, 'interesting correspondences' are also welcome. Results were evaluated automatically against reference alignments and by using logical reasoning techniques. Oriented alignments: This track focused on the evaluation of alignments that contain other relations than equivalences. It provides two data sets of real ontologies taken from a) Academia (alterations of ontologies from the OAEI benchmark series), b) Course catalogs (alterations of ontologies concerning courses in the universities of Cornell and Washington). The alterations aim to introduce additional subsumption correspondences between classes that cannot be inferred via reasoning. Model matching: This data set compares model matching tools from the Model-Driven Engineering (MDE) community on ontologies. The test cases are available in two formats: OWL and Ecore. The models to be matched have been automatically derived from a model-based repository. Instance matching ( §6): The goal of the instance matching track is to evaluate the performance of different tools on the task of matching RDF individuals which originate from different sources but describe the same real-world entity. Instance matching is organized in two sub-tasks:

Data interlinking (DI) This year the Data interlinking track focused on retrieving New York Times (NYT) interlinks with DBPedia, Freebase and Geonames. The NYT data set includes 4 data subsets: persons, locations, organizations and descriptors that should be matched to themselves to detect duplicates, and to DBPedia, Freebase and Geonames. Only Geonames has links to the Locations data set of NYT. OWL data track (IIMB): The synthetic OWL data track is focused on (i) providing an evaluation data set for various kinds of data transformations, including value transformations, structural transformations, and logical transformations;

(ii) covering a wide spectrum of possible techniques and tools. To this end, the IIMB benchmark is generated by starting from an initial OWL knowledge base that is transformed into a set of modified knowledge bases by applying several automatic transformations of data. Participants are requested to find the correct correspondences among individuals of the first knowledge base and individuals of the others.

Table 1 summarizes the variation in the results expected from the tests under consideration.

test formalism relations confidence modalities language SEALS benchmarks OWL This year we had to cancel the Oriented alignments and Model matching tracks which have not had enough participation. We preserved the IIMB track with only one participant, especially because the participant was not tied to the organizers and participated in the other tracks as well.

= [0 1] open EN √ anatomy OWL = [0 1] open EN √ conference OWL-DL =, <= [0 1] blind+open EN √ di RDF = [0 1] open EN iimb RDF = [0 1] open EN

The SEALS platform

In 2010, participants of the Benchmark, Anatomy and Conference tracks were asked for the first time to use the SEALS evaluation services: they had to wrap their tools as web services and the tools were executed on the machines of the tool developers [START_REF] Trojahn Dos Santos | Automating OAEI campaigns (first report)[END_REF].

In 2011, tool developers had to implement a simple interface and to wrap their tools in a predefined way including all required libraries and resources. A tutorial for tool wrapping was provided to the participants. This tutorial described how to wrap a tool and how to use a simple client to run a full evaluation locally. After local tests had been conducted successfully, the wrapped tool was uploaded for a test on the SEALS portal 4 . Consequently it was executed on the SEALS platform by the organisers in a semi-automated way. This approach allowed to measure runtime and ensured the reproducibility of the results for the first time in the history of OAEI. As a side effect, this approach ensures also that a tool is executed with the same settings for all of the three tracks. This was already requested by the organizers in the past years. However, this rule was sometimes ignored by participants.

Preparatory phase

Ontologies to be matched and (where applicable) reference alignments have been provided in advance during the period between May 30 th and June 27 th , 2011. This gave potential participants the occasion to send observations, bug corrections, remarks and other test cases to the organizers. The goal of this preparatory period is to ensure that the delivered tests make sense to the participants. The final test base was released on July 6 th , 2011. The data sets did not evolve after that, except for the reference alignment of the Anatomy track to which minor changes have been applied to increase its quality.

Execution phase

During the execution phase, participants used their systems to automatically match the ontologies from the test cases. In most cases, ontologies are described in OWL-DL and serialized in the RDF/XML format [START_REF] David | The alignment api 4.0[END_REF]. Participants were asked to use one algorithm and the same set of parameters for all tests in all tracks. It is fair to select the set of parameters that provides the best results (for the tests where results are known). Beside parameters, the input of the algorithms must be the two ontologies to be matched and any general purpose resource available to everyone, i.e., no resource especially designed for the test. In particular, participants should not use the data (ontologies and reference alignments) from other test cases to help their algorithms.

Participants can self-evaluate their results either by comparing their output with reference alignments or by using the SEALS client to compute precision and recall.

Evaluation phase

Participants have been encouraged to provide (preliminary) results or to upload their wrapped tools on the SEALS portal by September 1 st , 2011. Organizers evaluated the results and gave feedback to the participants. For the SEALS modality, a full-fledged test on the platform has been conducted by the organizers and problems were reported to the tool developers, until finally a properly executable version of the tool has been uploaded on the SEALS portal. Participants were asked to send their final results or upload the final version of their tools by September 23 th , 2011. Participants also provided the papers that are published hereafter.

As soon as first results were available, these results were published on the respective web pages by the track organizers. The standard evaluation measures are precision and recall computed against the reference alignments. For the matter of aggregation of the measures, we used weighted harmonic means (weights being the size of the true positives). This clearly helps in the case of empty alignments. Another technique that was used is the computation of precision/recall graphs so it was advised that participants provide their results with a weight to each correspondence they found. New measures addressing some limitations of precision and recall have also been used for testing purposes as well as measures for compensating the lack of complete reference alignments. Additionally, we measured runtimes for all tracks conducted under the SEALS modality. The number of covered runs has increased more than observed last year: 48 in 2007, 50 in 2008, 53 in 2009, 37 in 2010, and 53 in 2011. This is, of course, due to the ability to run all systems participating in the SEALS modality in all tracks. However, not all tools participating in the SEALS modality could generate results for the anatomy track (see Section 4). This does not really contradict the conjecture we made last year that systems are more specialized. In fact, only two systems (AgreementMaker and CODI) participated also in the instance matching tasks, and CODI only participated in a task (IIMB) in which no other instance matching system entered.

Comments on the execution

This year we were able to run most of the matchers in a controlled evaluation environment, in order to test their portability and deployability. This allowed us comparing systems on the same execution basis. This is also a guarantee that the tested system can be executed out of their particular development environment.

The list of participants is summarized in Table 2.

System AgrMaker Aroma CSA CIDER CODI LDOA Lily LogMap MaasMtch MapEVO MapPSO MapSSS OACAS OMR Optima Serimi YAM++ Zhishi Total=18 Confidence √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ benchmarks √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 16 anatomy √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 16 conference √ √ √ √ √ √ √ √ √ √ √ √ √ √ 14 di √ √ √ 3 iimb √ 1 Total 4 3 3 3 4 3 3 3 3 3 3 3 2 2 3 1 3 1 53
Table 2. Participants and the state of their submissions. Confidence stands for the type of result returned by a system: it is ticked when the confidence has been measured as non boolean value.

Two systems require a special remark. YAM++ used a setting that was learned from the reference alignments of the benchmark data set from OAEI 2009, which is highly similar to the corresponding benchmark in 2011. This affects the results of the traditional OAEI benchmark and no other tests. Moreover, we have run the benchmark in newly generated tests where YAM++ is indeed having weaker performances. Considering that indeed benchmarks was one of the few tests on which to train algorithms, we decided to keep YAM++ results with this warning.

AgreementMaker used machine learning techniques to choose automatically between one of three settings optimized for the benchmark, anatomy and conference data set. It used a subset of the available reference alignments as input to the training phase and clearly a specific tailored setting for passing these tests. This is typically prohibited by OAEI rules. However, at the same time, AgreementMaker has improved its results over last year so we found interesting to report them.

The summary of the results track by track is provided in the following sections.

Benchmark

The goal of the benchmark data set is to provide a stable and detailed picture of each algorithm. For that purpose, algorithms are run on systematically generated test cases.

Test data

The systematic benchmark test set is built around a seed ontology and many variations of it. The ontologies are described in OWL-DL and serialized in the RDF/XML format. The reference ontology is that of test #101. Participants have to match this reference ontology with the variations. Variations are focused on the characterization of the behavior of the tools rather than having them compete on real-life problems. They are organized in three groups:

Simple tests (1xx) such as comparing the reference ontology with itself, with another irrelevant ontology (the wine ontology used in the OWL primer) or the same ontology in its restriction to OWL-Lite; Systematic tests (2xx) obtained by discarding features from a reference ontology. It aims at evaluating how an algorithm behaves when a particular type of information is lacking. The considered features were:

-Name of entities that can be replaced by random strings, synonyms, name with different conventions, strings in another language than English; -Comments that can be suppressed or translated in another language; -Specialization hierarchy that can be suppressed, expanded or flattened; -Instances that can be suppressed; -Properties that can be suppressed or having the restrictions on classes discarded; -Classes that can be expanded, i.e., replaced by several classes or flattened. Four real-life ontologies of bibliographic references (3xx) found on the web and left mostly untouched (there were added xmlns and xml:base attributes). This is only used for the initial benchmark.

This year, we departed from the usual bibliographic benchmark that have been used since 2004. We used a new test generator [START_REF] Ros ¸oiu | Ontology matching benchmarks: generation and evaluation[END_REF] in order to reproduce the structure of benchmark from different seed ontologies. We have generated three different benchmarks against which matchers have been evaluated: benchmark (biblio) is the benchmark data set that has been used since 2004. It is used for participants to check that they can run the tests. It also allows for comparison with other systems since 2004. The seed ontology concerns bibliographic references and is inspired freely from BibTeX. It contains 33 named classes, 24 object properties, 40 data properties, 56 named individuals and 20 anonymous individuals.

We have considered the original version of benchmark (referred as original in the subsections above) and a new automatically generated one (biblio). benchmark2 (ekaw) The Ekaw ontology, one of the ontologies from the conference track ( §5), was used as seed ontology for generating the Benchmark2 data set. It contains 74 classes and 33 object properties. The results with this new data set were provided to participants after the preliminary evaluation. benchmark3 (finance) This data set is based on the Finance ontology 5 , which contains 322 classes, 247 object properties, 64 data properties and 1113 named individuals. This ontology was not disclosed to the participants.

Having these three data sets allows us to better evaluate the dependency between the results and the seed ontology. The SEALS platform allows for evaluating matchers against these many data sets automatically. For all data sets, the reference alignments are still limited: they only match named classes and properties and use the "=" relation with confidence of 1. Full description of these tests can be found on the OAEI web site.

Results

16 systems have participated in the benchmark track of this year's campaign (see Table 2). From the eleven participants last year, only four participated this year (Agree-mentMaker, Aroma, CODI and MapPSO). On the other hand, there are ten new participants, while two participants (CIDER and Lily) have been participating in the previous campaigns as well. In the following, we present the evaluation results, both in terms of runtime and compliance with relation to reference alignments.

Portability. 18 systems have been registered on the SEALS portal. One has abandoned due to requirements posed by the platform and another one abandoned silently. Thus, 16 systems bundled their tools into the SEALS format. From these 16 systems, we have not been able to run the final versions of OMR and OACAS (packaging error). CODI was not working on the operating system version under which we measured runtime. CODI runs under Windows and some versions of Linux, but has specific requirements not met on the Linux version that has been used for runnning the SEALS platform (Fedora 8). Some other systems still have (fixable) problems with the output they generate 6 .

Runtime. This year we were able to measure the performance of matchers in terms of runtime. We used a 3GHz Xeon 5472 (4 cores) machine running Linux Fedora 8 with 8GB RAM. This is a very preliminary setting for mainly testing the deployability of tools into the SEALS platform.

Table 3 presents the time required by systems to complete the 94 tests in each data set 7 . These results are based on 3 runs of each matcher on each data sets. We also include the result of a simple edit distance algorithm on labels (edna). Unfortunately, we were not able to compare CODI's runtime with other systems'.

Considering all tasks but finance, there are systems which can run them within less than 15mn (Aroma, edna, LogMap, CSA, YAM++, MapEVO, AgreementMaker, MapSSS), there are systems performing the tasks within one hour (Cider, MaasMatch, Lily) and systems which need more time (MapPSO, LDOA, Optima). Figure 1 better illustrates the correlation between the number of elements in each seed ontology and the time taken by matchers for generating the 94 alignments. The faster matcher, independently from the seed ontology, is Aroma (even for finance), followed by LogMap, CSA, YAM++, AgreementMaker (AgrMaker) and MapSSS. Furthermore, as detailed in the following, AgreementMaker, CSA, CODI and YAM++ are also the best systems for most of the different data sets. For finance, we observed that many participants were not able to deal with large ontologies. This applies to the slowest systems of the other tasks, but other problems occur with AgreementMaker and MapSSS. Fast systems like LogMap could not process some of the test cases due to the inconsistency of the finance ontology (as CODI). Finally, other relatively fast systems such as YAM++ and Lily had to time out. We plan to work on these two issues in the next campaigns.

Compliance. Concerning compliance, we focus on the benchmark2 (ekaw) data set. Table 4 shows the results of participants as well as those given by edna (simple edit distance algorithm on labels). The full results are on the OAEI web site.

As shown in Table 4, two systems achieve top performance in terms of F-measure: MapSSS and YAM++, with CODI, CSA and AgreementMaker as close followers, respectively. Lily and CIDER had presented intermediary values of precision and recall. All systems achieve a high level of precision and relatively low values of recall. Only MapEVO had a significantly lower recall than edna (with LogMap and MaasMatch (MaasMtch) with slightly lower values), while no system had lower precision. Looking at each group of tests, in simple tests (1xx) all systems have similar performance, excluding CODI. As noted in previous campaigns, the algorithms have their best score with the 1xx test series. This is because there are no modifications in the labels of classes and properties in these tests and basically all matchers are able to deal with the heterogeneity in labels. Considering that Benchmark2 has one single test in 1xx, the discriminant category is 2xx, with 101 tests. For this category, the top five systems in terms of F-measure (as stated above) are: MapSSS, YAM++, CODI, CSA and AgreementMaker, respectively (CIDER and Lily as followers).

Many algorithms have provided their results with confidence measures. It is thus possible to draw precision/recall graphs in order to compare them. Figure 2 shows the precision and recall graphs. These results are only relevant for the results of participants who provide confidence measures different from 1 or 0 (see Table 2). As last year, they show the real precision at n% recall and they stop when no more correspondences are available (then the end point corresponds to the precision and recall reported in Table 4).

The results have also been compared with the relaxed measures proposed in [4], namely symmetric proximity, correction effort and oriented measures ('Symmetric', 'Effort', 'P/R-oriented' in Table 4). Table 4 shows that these measures provide a uniform and limited improvement to most systems. As last year, the exception is MapEVO, which has a considerable improvement in precision. This could be explained by the fact this system misses the target, by not that far (the false negative correspondences found by the matcher are close to the correspondences in the reference alignment) so the gain provided by the relaxed measures has a considerable impact for this system. This may also be explained by the global optimization of the system which tends to be glob-ally roughly correct as opposed to locally strictly correct as measured by precision and recall.

The same confidence-weighted precision and recall as last year have been computed. They reward systems able to provide accurate confidence measures (or penalizes less mistakes on correspondences with low confidence) [START_REF] Euzenat | Results of the ontology alignment evaluation initiative[END_REF]. These measures provide precision increasing for most of the systems, specially edna, MapEVO and MapPSO (which had possibly many incorrect correspondences with low confidence). This shows that the simple edit distance computed by edna is valuable as a confidence measure (the weighted precision and recall for edna could be taken as a decent baseline). It also provides recall decrease specially for CSA, Lily, LogMap, MapPSO and YAM++ (which had apparently many correct correspondences with low confidence). The variation for YAM++ is quite impressive: this is because YAM++ provides especially low confidence to correct correspondences. Some systems, such as AgreementMaker, CODI, Maas-Match and MapSSS, generate all correspondences with confidence = 1, so they have no change.

Comparison across data sets. Table 5 presents the average F-measure for 3 runs, for each data set (as Table 3, some of these results are based on only one run). These three runs are not necessary: even if matchers exhibit non deterministic behavior on a test case basis, their average F-measure on the whole data set remains the same [START_REF] Ros ¸oiu | Ontology matching benchmarks: generation and evaluation[END_REF]. This year, although most of the systems participating in 2010 have improved their algorithms, none of them could outperform ASMOV, the best system in the 2010 campaign.

With respect to the original benchmark data set and the new generated one (original and biblio in Table 5), we could observe a 1-2% constant and negative variation in Fmeasure, for most of the systems (except CODI and MapEVO). Furthermore, most of the systems perform better with the bibliographic ontology than with ekaw (a variation of 5-15%). The exceptions are LDOA, LogMap and MapPSO, followed by MaasMatch and CIDER with relatively stable F-measures. Although we have not enough results for a fair comparison with finance, we could observe that CSA and MaasMatch are the most stable matchers (with less variation than the others), followed by Aroma, CIDER and AgreementMaker, respectively.

Finally, the group of best systems in each data set remains relatively the same across the different seed ontologies. Disregarding finance, CSA, CODI and YAM++ are ahead as the best systems for all three data sets, with MapSSS (2 out of 3) and Agreement-Maker, Aroma and Lily (1 out of 3) as followers.

Conclusions

For the first time, we could observe a high variation in the time matchers require to complete the alignment tasks (from some minutes to some days). We can also conclude that compliance is not proportional to runtime: the top systems in terms of F-measure were able to finish the alignment tasks in less than 15mn (with Aroma and LogMap as faster matchers, with intermediary levels of compliance). Regarding the capability of dealing with large ontologies, many of the participants were not able to process them, leaving room for further improvement on this issue. With respect to compliance, newcomers (CSA, YAM++ and MapSSS) have mostly outperformed other participants, for the new generated benchmarks. On the other hand, for the very known original benchmark data set, none of the systems was able to outperform the top-performer of the last year (ASMOV).

As in the previous years, the anatomy track confronts the existing matching technology with a specific type of ontologies from the biomedical domain. In this domain, many ontologies have been built covering different aspects of medical research. We focus on fragments of two biomedical ontologies which describe the human anatomy and the anatomy of the mouse. The data set of this track has been used since 2007. For a detailed description we refer the reader to the OAEI 2007 results paper [START_REF] Euzenat | Results of the ontology alignment evaluation initiative 2007[END_REF].

Experimental setting

Contrary to the previous years, we distinguish only between two evaluation experiments. Subtask #1 is about applying a matcher with its standard setting to the matching task. In the previous years we have also asked for additional alignments that favor precision over recall and vice versa (subtask #2 and #3). These subtasks are not part of the anatomy track in 2011 due to the fact that the SEALS platform does not allow for running tools with different configurations. Furthermore, we have proposed a fourth subtask, in which a partial reference alignment has to be used as an additional input.

In our experiments we compare precision, recall, F-measure and recall+. We have introduced recall+ to measure the amount of detected non-trivial correspondences. From 2007 to 2009, we reported on runtimes measured by the participants themselves. This survey revealed large differences in runtimes. This year we can compare the runtimes of participants by executing them on our own on the same machine. We used a Windows 2007 machine with 2.4 GHz (2 cores) and 7GB RAM allocated to the matching systems.

For the 2011 evaluation, we improved again the reference alignment of the data set. We removed doubtful correspondences and included several correct correspondences that had not been included in the past. As a result, we measured for the alignments generated in 2010 a slightly better F-measure (≈+1%) compared to the computation based on the old reference alignment. For that reason we have also included the top-3 systems of 2010 with recomputed precision/recall scores.

Results

In the following we analyze the robustness of the submitted systems and their runtimes. Further, we report on the quality of the generated alignment, mainly in terms of precision and recall.

Robustness and scalability. In 2011 there were 16 participants in the SEALS modality, while in 2010 we had only 9 participants for the anatomy track. However, this comparison is misleading. Some of these 16 systems are not really intended to match large biomedical ontologies. For that reason our first interest is related to the question, which systems generate a meaningful result in an acceptable time span. Results are shown in Table 6. First, we focused on the question whether systems finish the matching task in less than 24h. This is the case for a surprisingly low number of systems. The systems that do not finish in time can be separated in those systems that throw an exception related to insufficient memory after some time (marked with 'X'). The other group of systems were still running when we stopped the experiments after 24 hours (marked with 'T'). 8Obviously, matching relatively large ontologies is a problem for five out of fourteen executable systems. The two systems MapPSO and MapEVO can cope with ontologies that contain more than 1000 concepts, but have problems with finding correct correspondences. Both systems generate comprehensive alignments, however, MapPSO finds only one correct corespondence and MapEVO finds none. This can be related to the way labels are encoded in the ontologies. The ontologies from the anatomy track differ from the ontologies of the benchmark and conference tracks in this respect.

T 0 - - - - LDOA T 0 - - - - MapSSS X 0 - - - - Optima X 0 - - - - YAM++ X 0 - - - -
Table 6. Comparison against the reference alignment, runtime is measured in seconds, the size column refers to the number of correspondences in the generated alignment.

For those systems that generate an acceptable result, we observe a high variance in measured runtimes. Clearly ahead is the system LogMap (24s), followed by Aroma (39s). Next are Lily and AgreementMaker (approx. 10mn), CODI (30mn), CSA (1h15), and finally MaasMatch (18h).

Results for subtask #1. The results of our experiments are also presented in Table 6. Since we have improved the reference alignment, we have also included recomputed precision/recall scores for the top-3 alignments submitted in 2010 (marked by subscript 2010). Keep in mind that in 2010 AgreementMaker (AgrMaker) submitted an alignment that was the best submission to the OAEI anatomy track compared to all previous submissions in terms of F-measure. Note that we also added the base-line StringEquiv, which refers to a matcher that compares the normalized labels of two concepts. If these labels are identical, a correspondence is generated. Recall+ is defined as recall, with the difference that the reference alignment is replaced by the set difference of R \ A SE , where A SE is defined as the alignment generated by StringEquiv.

This year we have three systems that generate very good results, namely Agreement-Maker, LogMap and CODI. The results of LogMap and CODI are very similar. Both systems manage to generate an alignment with F-measure close to the 2010 submission of AgreementMaker. LogMap is slightly ahead. However, in 2011 the alignment generated by AgreementMaker is even better than in the previous year. In particular, AgreementMaker finds more correct correspondences, which can be seen in recall as well as in recall+ scores. At the same time, AgreementMaker can increase its precision. Also remarkable are the good results of LogMap, given the fact that the system finishes the matching task in less than half a minute. It is thus 25 times faster than Agreement-Maker and more than 75 times faster than CODI.

Lily, Aroma, CSA, and MaasMatch (MaasMatch) have less good results than the three top matching systems, however, they have proved to be applicable to larger matching tasks and can generate acceptable results for a pair of ontologies from the biomedical domain. While these systems cannot (or barely) top the String-Equivalence baseline in terms of F-measure, they manage, nevertheless, to generate many correct non-trivial correspondences. A detailed analysis of the results revealed that they miss at the same time many trivial correspondences. This is an uncommon result, which might, for example, be related to some pruning operations performed during the comparison of matchable entities. An exception is the MaasMatch system. It generates results that are highly similar to a subset of the alignment generated by the StringEquiv baseline.

Using an input alignment. This specific task was known as subtask #4 in the previous OAEI campaigns. Originally, we planned to study the impact of different input alignments of varying size. The idea is that a partial input alignment, which might have been generated by a human expert, can help the matching system to find missing correspondences. However, taking into account only those systems that could generate a meaningful alignment in time, only AgreementMaker, implemented the required interface. Thus, a comparative evaluation is not possible. We may have to put more effort in advertising this specific subtask for the next OAEI.

Alignment coherence. This year we also evaluated alignment coherence. The anatomy data set contains only a small amount of disjointness statements, the ontologies under discussion are in EL++. Thus, even simple techniques might have an impact on the coherence of the generated alignments. For the anatomy data set the systems LogMap, CODI, and MaasMatch generate coherent alignments. The first two systems put a focus on alignment coherence and apply special methods to ensure coherence. MaasMatch has generated a small, highly precise, and coherent alignment. The alignments generated by the other systems are incoherent. A more detailed analysis related to alignment coherence is conducted for the alignments of the conference data set in Section 5.

Conclusions

Less than half of the systems generate good or at least acceptable results for the matching task of the anatomy track. With respect to those systems that failed on anatomy, we can assume that this track was not in the focus of their developers. This means at the same time that many systems are particularly designed or configured for matching tasks that we find in the benchmark and conference tracks. Only few of them are robust "allround" matching systems that are capable of solving different tasks without changing their settings or algorithms.

The positive results of 2011 are the top results of AgreementMaker and the runtime performance of LogMap. AgreementMaker generated a very good result by increasing precision and recall compared to its last years submissions, which was the best submission in 2010 already. LogMap clearly outperforms all other systems in terms of runtimes and still generates good results. We refer the reader to the OAEI papers of these two systems for details on the algorithms.

Conference

The conference test case introduces matching several moderately expressive ontologies. Within this track, participant results were evaluated using diverse evaluation methods. As last year, the evaluation has been supported by the SEALS platform.

Test data

The collection consists of sixteen ontologies in the domain of organizing conferences. Ontologies have been developed within the OntoFarm project 9 .

The main features of this test case are:

-Generally understandable domain. Most ontology engineers are familiar with organizing conferences. Therefore, they can create their own ontologies as well as evaluate the alignments among their concepts with enough erudition. -Independence of ontologies. Ontologies were developed independently and based on different resources, they thus capture the issues in organizing conferences from different points of view and with different terminologies. -Relative richness in axioms. Most ontologies were equipped with OWL DL axioms of various kinds; this opens a way to use semantic matchers.

Ontologies differ in numbers of classes, of properties, in expressivity, but also in underlying resources. Ten ontologies are based on tools supporting the task of organizing conferences, two are based on experience of people with personal participation in conference organization, and three are based on web pages of concrete conferences.

Participants were asked to provide all correct correspondences (equivalence and/or subsumption correspondences) and/or 'interesting correspondences' within the conference data set. baseline 1 are in Group 2 (MaasMatch). Group 3 (CSA, CIDER and MapSSS) contains matchers which are better than baseline 1 at least in terms of F 2 -measure. Other matchers (Lily, Aroma, Optima, MapPSO, LDOA and MapEVO) perform worse than baseline 1 (Group 4). Optima, MapSSS and CODI did not provide graded confidence values. Performance of matchers regarding F 1 -measure is visualized in Figure 3. In conclusion, all best matchers (group one) are very close to each other. However, the matcher with the highest average F 1 -measure (.65) is YAM++, the highest average F 2 -measure (.61) is AgreementMaker and the highest average F 0.5 -measure (.75) is LogMap. In any case, we should take into account that this evaluation has been made over a subset of all possible alignments (one fifth).

Comparison with previous years. Three matchers also participated in the previous year. AgreementMaker improved its average F 1 -measure from .58 to .62 by higher precision (from .53 to .65) and lower recall (from .62 to .59), CODI increased its average F 1measure from .62 to .64 by higher recall (from .48 to .57) and lower precision (from .86 to .74). AROMA (with its AROMA-variant) slightly decreased its average F 1 -measure from .42 to .40 by lower precision (from .36 to .35) and recall (from .49 to .46).

Evaluation based on alignment coherence. As in the previous years, we apply the Maximum Cardinality measure proposed in [START_REF] Meilicke | Incoherence as a basis for measuring the quality of ontology mappings[END_REF] to measure the degree of alignment incoherence. Details on the algorithms can be found in [START_REF] Meilicke | Alignment Incoherence in Ontology Matching[END_REF]. The reasoner underlying our implementation is Pellet [START_REF] Sirin | Pellet: a practical OWL-DL reasoner[END_REF].

The results of our experiments are depicted in Table 8. It shows the average for all test cases of the conference track, which covers more than the ontologies that are connected via reference alignments. We had to omit the test cases in which the ontologies Confious and Linklings are involved as source or target ontologies. These ontologies resulted in many cases in reasoning problems. Thus, we had 91 test cases for each matching system. However, we faced reasoning problems for some combinations of test cases and alignments. In this case we computed the average score by ignoring these test cases. These problems occurred mainly for highly incoherent alignments. The last row in Table 8 informs about the number of test cases that were excluded. Note that we did not analyze the results of those systems that generated alignments with precision less than .25. CODI is the only system that guarantees the coherence of the generated alignments. While last year some of the alignments were incoherent, all of the alignments generated in 2011 are coherent. LogMap, a system with special focus on alignment coherence and efficiency [START_REF] Jiménez | Logmap: Logic-based and scalable ontology matching[END_REF], generates in most cases coherent alignments. A closer look at the outliers reveals that all incoherent alignments occured for ontology pairs where the ontology Cocus was involved. This ontology suffers from a very specific modeling error based on the inappropriate use of universal quantification. At the third position we find MaasMatch. MaasMatch generates less incoherent alignments than the remaining systems. This might be related to the high precision of the system. Contrary to LogMap, incoherent alignments are generated for different combinations of ontologies and there is no specific pattern emerging.

It is not easy to interpret the results of the remaining matching systems due to the different sizes of the alignments that they have generated. The more correspondences are contained in an alignment, the higher is the probability that this results in a concepts unsatisfiability. It is not always clear whether a relatively low/high degree of incoherence is mainly caused by the small/large size of the alignments, or related to the use of a specific technique. Overall, we conclude that alignment coherence is not taken into account by these systems. However, in 2011 we have at least some systems that apply specific methods to ensure coherence for all or at least for a large subset of generated alignments. Compared to the previous years, this is a positive result of our analysis.

The goal of the instance matching track is to evaluate the performance of different matching tools on the task of matching RDF individuals which originate from different sources but describe the same real-world entity. Data interlinking is known under many names according to various research communities: equivalence mining, record linkage, object consolidation and coreference resolution to mention the most used ones. In each case, these terms are used for the task of finding equivalent entities in or across data sets. As the quantity of data sets published on the Web of data dramatically increases, the need for tools helping to interlink resources becomes more critical. It is particularly important to maximize the automation of the interlinking process in order to be able to follow this expansion.

Unlike the other tracks, the instance matching tests specifically focus on an ontology ABox. However, the problems which have to be resolved in order to correctly match instances can originate at the schema level (use of different properties and classification schemas) as well as at the data level, e.g., different formats of values. This year, the track included two tasks. The first task, data interlinking (DI), aims at testing the performance of tools on large-scale real-world data sets published according to the linked data principles. The second one (IIMB) uses a set of artificially generated and real test cases respectively. These are designed to illustrate all common cases of discrepancies between individual descriptions (different value formats, modified properties, different classification schemas). The list of participants to the instance matching track is shown in Table 9.

DI-nyt-geonames

√ √ √ IIMB √ Table 9. Participants in the instance matching track.

Data interlinking task (DI) -New York Times

This year the data interlinking task consists of matching the New York Times subject headings to DBpedia, Freebase and Geonames. The New York Times has developed over the past 150 years an authoritative vocabulary for annotating news items. The vocabulary contains about 30,000 subject headings, or tags. They are progressively published as linked open data and, by July 2010, over 10,000 of these subject headings, in the categories People, Organizations, Locations and Descriptors, have been published 12 .

The New York Times data set was used in OAEI 2010 track on very large crosslingual resources.

The reference alignments are extracted from the links provided and curated by The New-York Times. However, the set of reference links has been updated to reflect the changes made to the external data sets during the year. In particular, several missing links were added, links pointing to non-existing DBPedia instances were removed, and links to instances redirecting to others were updated. Moreover, the Descriptors facet has been removed from the evaluation, since there was not a clear identity criterion for its instances. Subject heading facets are represented in SKOS. Each subject heading facet contains the label of the skos:Concept (skos:label), the facet it belongs to (skos:inScheme), and some specific properties: nyt:associated article count for the number of NYT articles the concept is associated with and nyt:topicPage pointing to the topic page (in HTML) gathering different information published on the subject. The Location facet also contains geo-coordinates. The concepts have links to DBpedia, Freebase and/or GeoNames. DI results. An overview of the precision, recall and F 1 -measure results per data set of the DI subtrack is shown in Table 11. A precision-recall graph visualization is shown in Figure 4. The results show a variation in both systems and data sets. Zhishi.links produces consistently high quality matches over all data sets, and obtains the highest overall scores. Matches to DBpedia locations (DI-nyt-dbpedia-loc.) appear to be difficult as AgreementMaker and SERIMI perform poorly on both precision and recall. This is not the case for Freebase locations (DI-nyt-freebase-loc.) and to a much lesser extent for Geonames (DI-nyt-geonames). We hypthesize that this is due to many locations not being present in DBPedia. Agreementmaker's scores considerably higher on People than on Locations and Organizations, which can be observed in both the DBpedia and the Freebase data set.

OWL data task (IIMB)

The OWL data task is focused on two main goals:

1. to provide an evaluation data set for various kinds of data transformations, including value transformations, structural transformations and logical transformations; 2. to cover a wide spectrum of possible techniques and tools.

To this end, we provided the ISLab Instance Matching Benchmark (IIMB). Participants were requested to find the correct correspondences among individuals of the first knowledge base and individuals of the other one. An important task here is that some of the transformations require automatic reasoning for finding the expected alignments.

IIMB is composed of a set of test cases, each one represented by a set of instances, i.e., an OWL ABox, built from an initial data set of real linked data extracted from the web. Then, the ABox is automatically modified in several ways by generating a set of new ABoxes, called test cases. Each test case is produced by transforming the individual descriptions in the reference ABox in new individual descriptions that are inserted in the test case at hand. The goal of transforming the original individuals is twofold: on one side, we provide a simulated situation where data referring to the same objects are provided in different data sources; on the other side, we generate different data sets with a variable level of data quality and complexity. IIMB provides transformation techniques supporting modifications of data property values, modifications of number and type of properties used for the individual description, and modifications of the individuals classification. The first kind of transformations is called data value transformation and it aims at simulating the fact that data expressing the same real object in different data sources may be different because of data errors or because of the usage of different conventional patterns for data representation. The second kind of transformations is called data structure transformation and it aims at simulating the fact that the same real object may be described using different properties/attributes in different data sources. Finally, the third kind of transformations, called data semantic transformation, simulates the fact that the same real object may be classified in different ways in different data sources.

The 2011 edition of IIMB is created by extracting data from Freebase, an open knowledge base that contains information about 11 million real objects including movies, books, TV shows, celebrities, locations, companies and more. Data extraction has been performed using the query language JSON together with the Freebase JAVA API 13 . IIMB2011 is a collection of OWL ontologies consisting of 29 concepts, 20 object properties, 12 data properties and more than 4000 individuals divided into 80 test cases.

Test cases from 0 to 20 contain changes in data format (misspelling, errors in text, etcetera); test cases 21 to 40 contain changes in structure (properties missing, RDF triples changed); 41 to 60 contain logical changes (class membership changed, logical errors); finally, test cases 61 to 80 contain a mix of the previous. One system, CODI, participated in this task. Its results (Table 5) show how precision drops moderately and recall drops dramatically as more errors are introduced.

IIMB results An overview of the precision, recall and F 1 -measure results per set of tests of the IIMB subtrack is shown in Table 5. A precision-recall graph visualization is shown in Figure 6.

Lesson learned and suggestions

This year we implemented most of our 2010 future plans by providing a common platform on which evaluation could be performed. There still remains one lesson not really taken into account that we identify with an asterisk (*) and that we will tackle in the coming months. The main lessons from this year are:

A) This year again indicated that requiring participants to implement a minimal interface was not a strong obstacle to participation. The interface allows for comparing matchers on the same or similar hardware. It also allows for running more tests or reproducing results without running a new campaign. B) By using the SEALS platform, we have eliminated the network issue that we had last year with web services and we can better testify the portability of tools. C) The client available for testing and evaluating wrapped tools was intensively used by participants to test and improve their systems. So, interoperability and the ability to get immediate feedback was appreciated by the tool developers. Moreover, participants could use the client to generate preliminary results to be included in their papers. D) There is a high variance in runtimes and there seems to be no correlation between runtime and quality of the generated results. *E) The low number of systems that could generate results for the Anatomy track is an uncommon result. It seems that not many matching systems of this year are capable of matching large ontologies (>1000 entities). Even if we had introduced new benchmark generation facilities, we have not used it towards scalability benchmarks. We plan to address this in the next few months.

F) Last years we reported that there are not many new systems entering the competition. This year we had many new participants. Only a minority of systems participated in one of the previous years. G) Two systems have not fully respected the OAEI rules. YAM++ used a setting learned from the reference alignments of the 2009 benchmark data set. Due to the fact that we run benchmarks also with newly generated tests, we decided to keep the YAM++ results with this warning. AgreementMaker used a specific setting to distinguish between Benchmarks, Anatomy and Conference. As AgreementMaker has improved its results over the last year, we decide to report on them as well. For the next campaigns we plan to be more attentive on these aspects. H) In spite of claims that such evaluations were needed, we had to declare the model matching and oriented alignments tracks unfruitful. It is a pity. This confirms that setting up a data set is not sufficient for attracting participants. I) More surprising, there are only a few matchers participating in the instance matching track. This is especially surprising given the high number of papers submitted and published on this topic nowadays. It seems that people involved in instance matching should cooperate to propose standard formats and evaluation modalities that everyone would use.

Future plans

In 2012, for logistic reasons, we plan to have an intermediate evaluation before OAEI-2012. This evaluation will concentrate on exploiting fully the SEALS platform and, in particular on:

-performing benchmark scalability tests by reducing randomly a large seed ontology; -generating discriminating benchmarks by suppressing easy tests; -adding new tasks, such as multilingual resources, on the SEALS platform.

We plan to run these tests within the next six months with the already registered tools that would like to be evaluated as well as with new tools willing to enter. These partial results will be integrated within the results of OAEI-2012.

Conclusions

The trend of the previous years, the number of systems and tracks they participate in, seem to stabilize. The average number of tracks entered by participants in 2011 (2.9) is above that of 2010 (2.6). This number is dominated by the use of the SEALS platform: each tool entering there can be evaluated on three tasks. It does not invalidate last year's remark that tools may be more specialized.

This year, systems did not deliver huge improvements in performance with respect to last year's performers which did not participate. However, AgreementMaker improved its results of last year to become one of the top performer. In addition, we have been able to test runtime and consistency of the tested matchers and noticed ample differences between systems. This may become a differentiating feature among matchers.

All participants have provided a description of their systems and their experience in the evaluation. These OAEI papers, like the present one, have not been peer reviewed. However, they are full contributions to this evaluation exercise and reflect the hard work and clever insight people put in the development of participating systems. Reading the papers of the participants should help people involved in ontology matching to find what makes these algorithms work and what could be improved. Sometimes participants offer alternate evaluation results.

The Ontology Alignment Evaluation Initiative will continue these tests by improving both test cases and testing methodology for being more accurate. Further information can be found at: http://oaei.ontologymatching.org.

For a few

  years, the number of participating systems has remained roughly stable: 4 participants in 2004, 7 in 2005, 10 in 2006, 17 in 2007, 13 in 2008, 16 in 2009, 15 in 2010 and 18 in 2011. However, participating systems are now constantly changing.

Fig. 1 .

 1 Fig. 1. Logarithmic plot of the time taken by matchers (averaged on 3 runs) to deal with different data sets: biblio, ekaw and finance

Fig. 3 .

 3 Fig. 3. Precision/recall triangular graph for conference. Matchers of participants from the first three groups are represented as squares. Baselines are represented as circles. Dotted lines depict level of precision/recall while values of F1-measure are depicted by areas bordered by corresponding lines F1-measure=0.[5|6|7].

Facet

Fig. 4 .

 4 Fig. 4. Precision/recall of tools participating in the DI subtrack.

Table 1 .

 1 Characteristics of the test cases (open evaluation is made with already published reference alignments and blind evaluation is made by organizers from reference alignments unknown to the participants).

Table 3 .

 3 Runtime

	original	biblio		ekaw		finance
	System Runtime Top-5 Runtime Top-5 Runtime Top-5 Runtime Top-5
	edna 1.07 AgrMaker 12.42 Aroma 1.05 CSA 2.47 CIDER 32.50 CODI -Error	√ √ √	1.06 -x 1.10 2.61 30.30 -Error	√ √ √	1.00 2.81 0.77 3.69 28.08 -Error	√ √ √	33.70 3.81h 10.83 3.10h 46.15h -Error	√ √ √ √
	LDOA 28.94h Lily 48.60		29.31h 48.18	√	17h 8.76		-T -T
	LogMap 2.45 MaasMtch 28.32		2.47 36.06		2.16 35.87		-Error 29.23h	√
	MapEVO 6.77		7.44		9.96		1.25h
	MapPSO 3.05h MapSSS 8.84	√	3.09h -x		3.72h 4.42	√	85.98h -x
	OACAS -Error		-Error		-Error		-Error
	OMR -Error		-Error		-Error		-Error
	Optima 3.15h YAM++ 6.51	√	2.48h 6.68	√	88.80h 8.02	√	-T -T

(in minutes) based on 3 runs, and the five best systems in terms of F-measure in each data set (top-5). 'Error' indicates that the tool could not run in the current setting; or their final version has some packaging error. 'T' indicates that tool could not process the single 101 test in less than 2 hours. 'x' indicates that the tool breaks when parsing some ontologies. Results in bold face are based on only 1 run.

Table 5 .

 5 Precision/recall graphs for benchmarks. The alignments generated by matchers are cut under a threshold necessary for achieving n% recall and the corresponding precision is computed. The numbers in the legend are the Mean Average Precision (MAP): the average precision for each correct retrieved correspondence. Systems for which these graphs are not meaningful (because they did not provide graded confidence values) are drawn in dashed lines. Results obtained by participants on each data set (based on 94 tests), including the results from the participants in 2010, and the top-five F-measure (five better systems in each data set).

	1.
	precision
	0.	0.	recall	1.
		edna	AgrMaker	aroma
		.52	.56	.52
		CSA	CIDER	CODI
		.59	.57	.60
		LDOA	Lily	LogMap
		.49	.56	.50
		MaasMtch	MapEVO	MapPSO
		.44	.22	.58
		MapSSS	Optima	YAM++
		.64	.53	.60
	Fig. 2.

Table 8 .

 8 Average size of alignments, number of incoherent alignments, and average degree of incoherence. The prefix > is added if the search algorithm stopped in one of the testcases due to a timeout of 10min prior to computing the degree of incoherence.

	Matcher	AgrMaker	AROMA	CIDER	CODI	CSA	Lily	LogMap	MaasMtch	MapSSS	Optima	YAM
	Size	13.9 14.1 17.9 9.5 50.8	17	8	7.5	10	31.3 10.1
	Inc. Alignments	49/90 58/88 69/88 0/91 69/69 70/90 8/91 21/91 51/90 73/84 41/91
	Degree of Inc.	12% 16% 13% 0% >29% 14% 2% 4% 9% >31% 7%
	Reasoning problems 1	3	3	0	22	1	0	0	1	7	0

Table 10 .

 10 # Concepts Links to Freebase Links to DBPedia Links to Geonames Number of links between the New-York Times corpus and other data sources.

	People	4,979	4,979	4,977	0
	Organizations	3,044	3,044	1,965	0
	Locations	1,920	1,920	1,920	1,920

Table 11 .

 11 Results of the DI subtrack.

		AgreementMaker	SERIMI	Zhishi.links
	Dataset	Prec. FMeas. Rec. Prec. FMeas. Rec. Prec. FMeas. Rec.
	DI-nyt-dbpedia-loc. .79 .69 .61 .69 .68 .67 .92 .92 .91
	DI-nyt-dbpedia-org. .84 .74 .67 .89 .88 .87 .90 .91 .93
	DI-nyt-dbpedia-peo. .98 .88 .80 .94 .94 .94 .97 .97 .97
	DI-nyt-freebase-loc. .88 .85 .81 .92 .91 .90 .90 .88 .86
	DI-nyt-freebase-org. .87 .80 .74 .92 .91 .89 .89 .87 .85
	DI-nyt-freebase-peo. .97 .96 .95 .93 .92 .91 .93 .93 .92
	DI-nyt-geonames.	.90 .85 .80 .79 .80 .81 .94 .91 .88
	H-mean.	.92 .85 .80 .89 .89 .88 .93 .92 .92

http://om2011.ontologymatching.org

http://www.seals-project.eu

http://www.seals-project.eu/join-the-community/

http://www.fadyart.com/ontologies/data/Finance.owl

All evaluations have been performed with the Alignment API 4.2[START_REF] David | The alignment api 4.0[END_REF] with the exception of LDOA for which we had to adapt the relaxed evaluators to obtain results.

From the 111 tests in the original benchmark data set, 17 of them have not been automatically generated: 102-104, 203-210, 230-231, 301-304. For comparative purposes, they were discarded.

We could not execute the two systems OACAS and OMR, not listed in the table, because the required interfaces have not been properly implemented.

http://nb.vse.cz/ ˜svatek/ontofarm.html

Computed using the absolute scores, i.e. number of true positive examples.

http://data.nytimes.com/

Acknowledgments

We warmly thank the participants of this campaign. We know that they have worked hard for having their matching tools executable in time and they provided insightful papers presenting their experience. The best way to learn about the results remains to read the following papers.

We are grateful to Dominique Ritze for participating in the extension of the reference alignments for the conference track.

We thank Jan Noessner for providing data in the process of constructing the IIMB data set. We are grateful to Martin Ringwald and Terry Hayamizu for providing the reference alignment for the anatomy ontologies and thank Elena Beisswanger for her thorough support on improving the quality of the data set.

We also thank the other members of the Ontology Alignment Evaluation Initiative steering committee: Yannis Kalfoglou (Ricoh laboratories, UK), Miklos Nagy (The Open University (UK), Natasha Noy (Stanford University, USA), Yuzhong Qu (Southeast University, CN), York Sure (Leibniz Gemeinschaft, DE), Jie Tang (Tsinghua University, CN), George Vouros (University of the Aegean, GR).

Jérôme Euzenat, Christian Meilicke, Heiner Stuckenschmidt and Cássia Trojahn dos Santos have been partially supported by the SEALS (IST-2009-238975) European project.

Ondřej Šváb-Zamazal has been supported by the CSF grant P202/10/0761.

Results

This year, we provided results in terms of F 2 -measure and F 0.5 -measure, comparison with two baseline matchers and precision/recall triangular graph.

Evaluation based on the reference alignments. We evaluated the results of participants against reference alignments. They include all pairwise combinations between 7 different ontologies, i.e. 21 alignments. For better comparison, we evaluated alignments with regard to three different average 10 F-measures independently. We used F 0.5 -measure (where β = 0.5) which weights precision higher than recall, F 1 -measure (the usual F-measure, where β = 1), which is the harmonic mean of precision and recall, and F 2 -measure (for β = 2) which weights recall higher than precision. For each of these F-measures, we selected a global confidence threshold that provides the highest average F [0.5|1|2] -measure. Results of these three independent evaluations 11 are provided in Table 7.

Matchers are ordered according to their highest average F 1 -measure. Additionally, there are two simple string matchers as baselines. Baseline 1 is a string matcher based on string equality applied on local names of entities which were lowercased before. Baseline 2 enhances baseline 1 with three string operations: removing of dashes, underscores and "has" words from all local names. These two baselines divide matchers into four groups. Group 1 consists of best matchers (YAM++, CODI, LogMap and AgreementMaker) having better results than baseline 2 in terms of F 1 -measure. Matchers which perform worse than baseline 2 in terms of F 1 -measure but still better than