Instance Matching. **There are numerous approaches to match instances of**
one ontology to instances of another ontology. Ferrara, Lorusso, and Montanelli [10] introduce this problem from a philosophical point of view. Different techniques are being used, such as exploiting the terminological structure [23], logical deduction [25], or a combination of logical and numerical methods [26].

The Sig.ma **engine [29] uses heuristics to match instances. Perhaps closest to**
our approach is [15], which introduces the concept of functionality. Different from their approach, paris **does not require an additional smoothening factor.**
The silk **framework [31] allows specifying manual mapping rules. The** ObjectCoref **approach by Hu, Chen, and Qu [16] allows learning a mapping between**
the instances from training data. With paris**, we aim at an approach that**
uses neither manual input nor training data. We compare some **of the results**
of ObjectCoref **to that of** paris **on the datasets of the ontology alignment**
evaluation initiative [9] in Section 6. Hogan [14] matches instances and propose to use these instances to compute the similarity between classes, but provides no experiments. Thus, none of these approaches can align classes and relations like paris.

Holistic Approaches. **Only very few approaches address the cause of aligning**
both schema and instances: the RiMOM **[20] and** iliads **[30] systems. Both**
of these have only been tested on small ontologies. The RiMOM **system can**
align classes, but it cannot find *subclassOf* **relationships. Furthermore, the**
approach provides a bundle of heuristics and strategies to choose from, while paris **is monolithic. None of the ontologies the** iliads **system has been tested on** contained full-fledges instances with properties. In contrast, paris **is shown to**
perform well even on large-scale real-world ontologies with millions of instances.

## 3 Preliminaries

In this section, we recall the notions of ontology and of equivalence. Finally, we introduce the notion of functionality as one of the key concepts for ontology alignment.

Ontologies. **We are concerned with ontologies available in the Resource Description Framework Schema (RDFS [33]), the W3C standard for knowledge** representation. An RDFS ontology builds on *resources***. A resource is an identifier for a real-world object, such as a city, a person, or a university, but also the**
concept of mathematics. For example, *London* **is a resource that represents the** city of London. A *literal* is a string, date or number. A *property* (or *relation***) is**
a binary predicate that holds between two resources or between a resource and a literal. For example, the property *isLocatedIn* **holds between the resources**
London and UK**. In the RDFS model, it is assumed that there exists a fixed**
global set R of resources, a fixed global set L **of literals, and a fixed global**
set P of properties. Each resource is described by a URI. An RDFS *ontology* can be seen as a set of triples O ⊂ R × P × (R ∪ L), called *statements***. In** the following, we assume given an ontology O. To say that h*x, r, y*i ∈ O**, we**
will write r(*x, y*) and we call x and y the *arguments* of r**. Intuitively, such a**
statement means that the relation r holds between the entities x and y**. We**
say that *x, y* is a *pair* of r**. A relation** r
−1is called the *inverse* **of a relation** r