=Paper=
{{Paper
|id=Vol-551/paper-4
|storemode=property
|title=Computing minimal mappings
|pdfUrl=https://ceur-ws.org/Vol-551/om2009_Tpaper4.pdf
|volume=Vol-551
|dblpUrl=https://dblp.org/rec/conf/semweb/GiunchigliaMA08
}}
==Computing minimal mappings==
https://ceur-ws.org/Vol-551/om2009_Tpaper4.pdf
Computing minimal mappings
Fausto Giunchiglia, Vincenzo Maltese, Aliaksandr Autayeu
Dipartimento di Ingegneria e Scienza dell’Informazione (DISI) - Università di Trento
{fausto, maltese, autayeu}@disi.unitn.it
Abstract. Given two classifications, or lightweight ontologies, we compute the
minimal mapping, namely the subset of all possible correspondences, called
mapping elements, between them such that i) all the others can be computed
from them in time linear in the size of the input ontologies, and ii) none of them
can be dropped without losing property i). In this paper we provide a formal
definition of minimal mappings and define a time efficient computation algo-
rithm which minimizes the number of comparisons between the nodes of the
two input ontologies. The experimental results show a substantial improvement
both in the computation time and in the number of mapping elements which
need to be handled.
Keywords: Ontology matching, lightweight ontologies, minimal mappings
1 Introduction
Given any two graph-like structures, e.g., database and XML schemas, classifica-
tions, thesauri and ontologies, matching is usually identified as the problem of finding
those nodes in the two structures which semantically correspond to one another. Any
such pair of nodes, along with the semantic relationship holding between the two, is
what we informally call a mapping element. In the last few years a lot of work has
been done on this topic both in the digital libraries [15, 16, 17, 21] and the computer
science [2, 3, 4, 5, 6, 8, 9] communities. In this paper we concentrate on lightweight
ontologies (or formal classifications), as formally defined in [1, 7], and we focus on
the problem of finding minimal mappings, that is, the subset of all possible corre-
spondences, called mapping elements, such that i) all the others can be computed from
them in time linear in the size of the input graphs, and ii) none of them can be
dropped without losing property i). This must not be seen as a limitation. There are
plenty of schemas in the world which can be translated, with almost no loss of infor-
mation, into lightweight ontologies. For instance, thesauri, library classifications, file
systems, email folder structures, web directories, business catalogues and so on.
Lightweight ontologies are well defined and pervasive. The main advantage of mini-
mal mappings is that they are the minimal amount of information that needs to be
dealt with. Notice that this is a rather important feature as the number of possible
mapping elements can grow up to n*m with n and m being the size of the two input
ontologies. Minimal mappings provide clear usability advantages. Many systems and
corresponding interfaces, mostly graphical, have been provided for the management
of mappings but all of them hardly scale with the increasing number of nodes, and the
resulting visualizations are rather messy [3]. Furthermore, the maintenance of smaller
sets makes the work of the user much easier, faster and less error prone [11].
The main contributions of this paper are a formal definition of minimal and, dually,
redundant mappings, evidence of the fact that the minimal mapping always exists and
it is unique and an algorithm for computing it. This algorithm has the following main
features:
1. It can be proved to be correct and complete, in the sense that it always com-
putes the minimal mapping;
2. It minimizes the number of calls to the node matching function which com-
putes the relation between two nodes. Notice that node matching in the general
case amounts to logical reasoning [5], and it may require exponential time;
3. It computes the mapping of maximum size (including the maximum number of
redundant elements) as it maximally exploits the information codified in the
graph of the lightweight ontologies in input. This, in turn, avoids missing
mapping elements due to pitfalls in the node matching functions, e.g. because
of missing background knowledge [8].
As far as we know very little work has been done on the issue of computing mini-
mal mappings. In general the computation of minimal mappings can be seen as a spe-
cific instance of the mapping inference problem [4]. Closer to our work, in [9, 10, 11]
the authors use Distributed Description Logics (DDL) [12] to represent and reason
about existing ontology mappings. They introduce a few debugging heuristics which
remove mapping elements which are redundant or generate inconsistencies from a
given set [10]. The main problem of this approach, as also recognized by the authors,
is the complexity of DDL reasoning [11]. In our approach, instead of pruning redun-
dant elements, we directly compute the minimal set. Among other things, our ap-
proach allows us to minimize the number of calls to node matching.
The rest of the paper is organized as follows. Section 2 provides a motivating ex-
ample. Section 3 provides the definition for redundant and minimal mappings, and it
shows that the minimal set always exists and it is unique. Section 4 describes the al-
gorithm while Section 5 evaluates it. Finally, Section 6 draws some conclusions and
outlines the future work.
2 A motivating example
Classifications are perhaps the most natural tool humans use to organize informa-
tion content. Information items are hierarchically arranged under topic nodes moving
from general ones to more specific ones as long as we go deeper in the hierarchy.
Classification (1) Classification (2)
journals D programming and
A development
development and
programming E languages
B
languages
java F java
C
G magazines
Fig. 1. Two classifications
This attitude is well known in Knowledge Organization as the principle of organiz-
ing from the general to the specific [16], called synthetically the get-specific principle
in [1, 7]. Consider the two fragments of classifications depicted in Fig. 1. They are
designed to arrange more or less the same content, but from different perspectives.
The second is a fragment taken from the Yahoo web directory1 (category Computers
and Internet).
Following the approach described in [1] and exploiting dedicated NLP techniques
tuned to short phrases (for instance, as described in [13]), classifications can be con-
verted, exactly or with a certain degree of approximation, into their formal alter-ego,
namely into lightweight ontologies. Lightweight ontologies [1, 7] are acyclic graph
structures where each natural language node label is translated into a propositional
Description Logic (DL) formula codifying the meaning of the node. Notice that the
formula associated to each node contains the formula of the node above to capture the
fact that the meaning of each node is contextualized by the meaning of its ancestor
nodes. As a consequence, the backbone structure of the resulting lightweight ontolo-
gies is represented by subsumption relations between nodes. The resulting formulas
are reported in Fig. 2.
Source Target
⊑
journals#1 A D programming#2 ⊔ development#1
⊑
(development#1 ⊔ programming#2) ⊑ languages#3 ⊓
B ⊑ E
⊓ languages#3 ⊓ journals#1 (programming#2 ⊔ development#1)
⊑
Java#3 ⊓ C F java#3 ⊓ languages#3 ⊓
⊒ ⊒
(development#1 ⊔ programming#2) (programming#2 ⊔ development#1)
⊓ languages#3 ⊓ journals#1 G magazines#1 ⊓ java#3 ⊓
≡
languages#3 ⊓
(programming#2 ⊔ development#1)
M’ = {, , , , , , , }
M = { , }
Fig. 2. The minimal and redundant mapping between two lightweight ontologies
Here each string denotes a concept (e.g., journals#1) and the number at the end of
the strings denote a specific concept constructed from a WordNet sense. Fig. 2 also
reports the resulting mapping elements. We assume that each mapping element is as-
sociated with one of the following semantic relations: disjointness (⊥), equivalence
(≡), more specific (⊑) and less specific (⊒), as computed for instance by semantic
matching [5]. Notice however that not all the mapping elements have the same se-
mantic valence. For instance, B⊑D is a trivial logical consequence of B⊑E and E⊑D,
and similarly for C⊑F and C≡G. We represent the elements in the minimal mapping
using solid lines and redundant elements using dashed lines. M’ is the set of maxi-
mum size (including the maximum number of redundant elements) while M is the
minimal set. The problem is how to compute the minimal set in the most efficent way.
1
http://dir.yahoo.com/
3 Redundant and minimal mappings
Adapting the definition in [1] we define a lightweight ontology as follows:
Definition 1 (Lightweight ontology). A lightweight ontology O is a rooted tree
where:
a) N is a finite set of nodes;
b) E is a set of edges on N;
c) LF is a finite set of labels expressed in a Propositional DL language such that for
any node ni ∈ N, there is one and only one label liF∈LF;
d) li+1F ⊑ liF with ni being the parent of ni+1.
The superscript F is used to emphasize that labels are in a formal language. Fig. 2
above provides an example of (a fragment of) two lightweight ontologies.
We then define mapping elements as follows:
Definition 2 (Mapping element). Given two lightweight ontologies O1 and O2, a
mapping element m between them is a triple , where:
a) n1 ∈N1 is a node in O1, called the source node;
b) n2 ∈N2 is a node in O2, called the target node;
c) R ∈ {≡, ⊑, ⊒, ⊥} is the strongest semantic relation holding between n1 and n2.
The partial order is such that disjointness is stronger than equivalence which, in
turn, is stronger than subsumption (in both directions), and such that the two sub-
sumption symbols are unordered. This is in order to return subsumption only when
equivalence does not hold or one of the two nodes being inconsistent (this latter case
generating at the same time both a disjointness and a subsumption relation), and simi-
larly for the order between disjointness and equivalence. Notice that, under this order-
ing, there can be at most one mapping element between two nodes.
The next step is to define the notion of redundancy. The key idea is that, given a
mapping element , a new mapping element is redundant with
respect to the first if the existence of the second can be asserted simply by looking at
the relative positions of n1 with n1’, and n2 with n2’. In algorithmic terms, this means
that the second can be computed without running the time expensive node matching
functions. We have identified four basic redundancy patterns as follows:
(1) (2) (3) (4)
⊑ D C ⊒ A F
≡ ≡
⊑ ⊒ ⊥ ≡
A B A B A B C D
⊥
C D C D E B
Fig. 3. Redundancy detection patterns
In Fig. 3, the blue dashed mappings are redundant w.r.t. the solid blue ones. The
bold red solid lines show how a semantic relation propagates. Let us discuss the ra-
tionale for each of the patterns:
• Pattern (1): each mapping element is redundant w.r.t. . In
fact, C is more specific than A which is more specific than B which is more
specific than D. As a consequence, by transitivity C is more specific than D.
• Pattern (2): dual argument as in pattern (1).
• Pattern (3): each mapping element is redundant w.r.t. . In
fact, we know that A and B are disjoint, that C is more specific than A and that
D is more specific than B. This implies that C and D are also disjoint.
• Pattern (4): Pattern 4 is the combinations of patterns (1) and (2).
In other words, the patterns are the way to capture logical inference from structural
information, namely just by looking at the position of the nodes in the two trees. As
we will show, this on turn allows computing the redundant elements in linear time
(w.r.t. the size of the two ontologies) from the ones in the minimal set. Notice that
patterns (1) and (2) are still valid in case we substitute subsumption with equivalence.
However, in this case we cannot exclude the possibility that a stronger relation holds
between C and D. A trivial example of where this is not the case is provided in Fig. 4
(a).
(a) ≡ ⊑ (b)
Car A D Auto Mammal A B Animal
⊑ ⊑ ⊑
≡ ⊑
Automobile C Canine C D Dog
Fig. 4. Examples of non redundant mapping elements
On the basis of the patterns and the considerations above we can define redundant
elements as follows. Here path(n) is the path from the root to the node n.
Definition 3 (Redundant mapping element). Given two lightweight ontologies O1
and O2, a mapping M and a mapping element m’∈M with m’ = between
them, we say that m’ is redundant in M iff one of the following holds:
(1) If R’ is ⊑, ∃m∈M with m = and m ≠ m’ such that R ∈ {⊑, ≡}, A
∈ path(C) and D ∈ path(B);
(2) If R’ is ⊒, ∃m∈M with m = and m ≠ m’ such that R ∈ {⊒, ≡}, C
∈ path(A) and B ∈ path(D);
(3) If R’ is ⊥, ∃m∈M with m = and m ≠ m’ such that A ∈ path(C)
and B ∈ path(D);
(4) If R’ is ≡, conditions (1) and (2) must be satisfied.
See how Definition 3 maps to the four patterns in Fig. 3. Fig. 2 in Section 2 pro-
vides examples of redundant elements. Definition 3 can be proved to capture all and
only the cases of redundancy.
Theorem 1 (Redundancy, soundness and completeness). Given a mapping M between
two lightweight ontologies O1 and O2, a mapping element m’ ∈ M is redundant if and
only if it satisfies one of the conditions of Definition 3.
The soundness argument is the rationale described for the patterns above. Com-
pleteness can be shown by constructing the counterargument that we cannot have re-
dundancy in the remaining cases. We can proceed by enumeration, negating each of
the patterns, encoded one by one in the conditions appearing in the Definition 3. The
complete proof is given in [22]. Fig. 4 (b) provides an example of non redundancy
which is based on pattern (1). It tells us that the existence of a link between two nodes
does not necessarily propagate to the two nodes below. For example we cannot derive
that Canine ⊑ Dog from the set of axioms {Canine ⊑ Mammal, Mammal ⊑ Animal,
Dog ⊑ Animal}, and it would be wrong to do so.
The notion of redundancy allows us to formalize the notion of minimal mapping as
follows:
Definition 4 (Minimal mapping). Given two lightweight ontologies O1 and O2, we
say that a mapping M between them is minimal iff:
a) ∄m∈M such that m is redundant (minimality condition);
b) ∄M’⊃M satisfying condition a) above (maximality condition).
A mapping element is minimal if it belongs to the minimal mapping.
Note that conditions (a) and (b) ensure that the minimal set is the set of maximum
size with no redundant elements. As an example, the set M in Fig. 2 is minimal.
Comparing this mapping with M’ we can observe that all elements in the set M’ - M
are redundant and that, therefore, there are no other supersets of M with the same
properties. In effect, and are redundant w.r.t. for pat-
tern (2); , and are redundant w.r.t. for pat-
tern (1); is redundant w.r.t. for pattern (1). Note that M contains
far less mapping elements w.r.t. M’.
As last observation, for any two given lightweight ontologies, the minimal map-
ping always exists and it is unique.
Theorem 2 (Minimal mapping, existence and uniqueness). Given two lightweight
ontologies O1 and O2, there is always one and only one minimal mapping between
them.
A proof is given in [22].
4 Computing minimal and redundant mappings
The patterns described in the previous section suggest how to significantly reduce
the amount of calls to the node matchers. By looking for instance at pattern (2) in Fig.
3, given a mapping element m = we know that it is not necessary to com-
pute the semantic relation holding between A and any descendant C in the sub-tree of
B since we know in advance that it is ⊒. At the top level the algorithm is organized as
follows:
• Step 1, computing the minimal mapping modulo equivalence: compute the
set of disjointness and subsumption mapping elements which are minimal
modulo equivalence. By this we mean that they are minimal modulo collaps-
ing, whenever possible, two subsumption relations of opposite direction into a
single equivalence mapping element;
• Step 2, computing the minimal mapping: eliminate the redundant subsump-
tion mapping elements. In particular, collapse all the pairs of subsumption
elements (of opposite direction) between the same two nodes into a single
equivalence element. This will result into the minimal mapping;
• Step 3, computing the mapping of maximum size: Compute the mapping of
maximum size (including minimal and redundant mapping elements). During
this step the existence of a (redundant) element is computed as the result of the
propagation of the elements in the minimal mapping.
The first two steps are performed at matching time, while the third is activated
whenever the user wants to exploit the pre-computed mapping elements, for instance
for their visualization. For lack of space in the following we give only the pseudo-
code for the first step. The interested reader can look at [22] for the pseudo-code of
the other two steps.
The minimal mapping is computed by a function TreeMatch whose pseudo-code
is given in Fig. 5. M is the minimal set while T1 and T2 are the input lightweight on-
tologies.
10 node: struct of {cnode: wff; children: node[];}
20 T1,T2: tree of (node);
30 relation in {⊑, ⊒, ≡, ⊥};
40 element: struct of {source: node; target: node; rel: relation;};
50 M: list of (element);
60 boolean direction;
70 function TreeMatch(tree T1, tree T2)
80 {TreeDisjoint(root(T1),root(T2));
90 direction := true;
100 TreeSubsumedBy(root(T1),root(T2));
110 direction := false;
120 TreeSubsumedBy(root(T2),root(T1));
130 TreeEquiv();
140 };
Fig. 5. Pseudo-code for the tree matching function
TreeMatch is crucially dependent on the node matching functions NodeDisjoint
(given in [22]) and NodeSubsumedBy (Fig. 6) which take two nodes n1 and n2 and
return a positive answer respectively in case of disjointness or subsumption, or a
negative answer if it is not the case or they are not able to establish it. Notice that
these two functions hide the heaviest computational costs; in particular their computa-
tion time is exponential when the relation holds, but possibly much faster, when the
relation does not hold. The main motivation for this is that the node matching prob-
lem, in the general case, should be translated into disjointness or subsumption prob-
lem in propositional DL (see [5] for a detailed description). The goal, therefore, is to
compute the minimal mapping by minimizing the calls to the node matching functions
and, in particular minimizing the calls where the relation will turn out to hold. We
achieve this purpose by processing both trees top down. To maximize the perform-
ance of the system, TreeMatch has therefore been built as the sequence of three func-
tion calls: the first call to TreeDisjoint (line 80) computes the minimal set of dis-
jointness mapping elements, while the second and the third call to TreeSubsumedBy
compute the minimal set of subsumption mapping elements in the two directions
modulo equivalence (lines 90-120). Notice that in the second call, TreeSubsumedBy
is called with the input ontologies with swapped roles. These three calls correspond to
Step 1 above. Line 130 in the pseudo code of the TreeMatch implements the Step 2.
Given two sub-trees in input, rooted in n1 and n2, the TreeDisjoint function
searches for the first disjointness elements along any pair of paths in them. Look at
[22] for corresponding pseudo-code and the complete description.
TreeSubsumedBy (Fig. 6) recursively finds all minimal mapping elements where
the strongest relation between the nodes is ⊑ (or dually, ⊒ in the second call in the
TreeMatch, line 120. In the following we will concentrate only on the first call).
10 function boolean TreeSubsumedBy(node n1, node n2)
20 {c1,c2: node; LastNodeFound: boolean;
30 if ( ∈ M) then return false;
40 if (!NodeSubsumedBy(n1, n2)) then
50 foreach c1 in GetChildren(n1) do TreeSubsumedBy(c1,n2);
60 else
70 {LastNodeFound := false;
80 foreach c2 in GetChildren(n2) do
90 if (TreeSubsumedBy(n1,c2)) then LastNodeFound := true;
100 if (!LastNodeFound) then AddSubsumptionMappingElement(n1,n2);
120 return true;
140 };
150 return false;
160 };
170 function boolean NodeSubsumedBy(node n1, node n2)
180 {if (Unsatisfiable(mkConjunction(n1.cnode,negate(n2.cnode)))) then
return true;
190 else return false; };
200 function AddSubsumptionMappingElement(node n1, node n2)
210 {if (direction) then AddMappingElement();
220 else AddMappingElement(); };
Fig. 6. Pseudo-code for the TreeSubsumedBy function
Notice that TreeSubsumedBy assumes that the minimal disjointness elements are
already computed. As a consequence, at line 30 it checks whether the mapping ele-
ment between the nodes n1 and n2 is already in the minimal set. If this is the case it
stops the recursion. This allows computing the stronger disjointness relation rather
than subsumption when both hold (namely in presence of an inconsistent node).
Given n2, lines 40-50 implement a depth first recursion in the first tree till a subsump-
tion is found. The test for subsumption is performed by the NodeSubsumedBy func-
tion that checks whether the formula obtained by the conjunction of the formulas as-
sociated to the node n1 and the negation of the formula for n2 is unsatisfiable (lines
170-190). Lines 60-140 implement what happens after the first subsumption is found.
The key idea is that, after finding the first subsumption, TreeSubsumedBy keeps re-
cursing down the second tree till it finds the last subsumption. When this happens, the
resulting mapping element is added to the minimal set (line 100). Notice that both
NodeDisjoint and NodeSubsumedBy call the function Unsatisfiable which embeds
a call to a SAT solver.
To fully understand TreeSubsumedBy, the reader should check what happens in
the four situations in Fig. 7. In case (a) the first iteration of the TreeSubsumedBy
finds a subsumption between A and C. Since C has no children, it skips lines 80-90
and directly adds the mapping element to the minimal set (line 100). In
case (b), since there is a child D of C the algorithm iterates on the pair A-D (lines 80-
90) finding a subsumption between them. Since there are no other nodes under D, it
adds the mapping element to the minimal set and returns true. Therefore
LastNodeFound is set to true (line 90) and the mapping element between the pair A-C
is recognized as redundant. Case (c) is similar. The difference is that TreeSubsum-
edBy will return false when checking the pair A-D (line 30), thanks to previous com-
putation of minimal disjointness mapping elements, and therefore the mapping ele-
ment is recognized as minimal. In case (d) the algorithm iterates after the
second subsumption mapping element is identified. It first checks the pair A-C and it-
erates on A-D concluding that subsumption does not hold between them (line 40).
Therefore, it recursively calls TreeSubsumedBy between B and D. In fact, since will be recognized as minimal, it is not worth checking for pattern
(1). As a consequence is recognized as minimal together with .
(a) (b) (c) (d)
⊑ ⊑ ⊑ ⊑
A C A C A C A C
⊑
⊑ ⊥ ⊑
D B D B D
Fig. 7. Examples of applications of the TreeSubsumedBy
Five observations. The first is that, even if, overall, TreeMatch implements three
loops instead of one, the wasted (linear) time is largely counterbalanced by the expo-
nential time saved by avoiding a lot of useless calls to the SAT solver. The second is
that, when the input trees T1 and T2 are two nodes, TreeMatch behaves as a node
matching function which returns the semantic relation holding between the input
nodes. The third is that the call to TreeDisjoint before the two calls to TreeSubsum-
edBy allows us to implement the partial order on relations defined in the previous
section. In particular it allows returning only a disjointness mapping element when
both disjointness and subsumption hold. The fourth is the fact that skipping (in the
body of the TreeDisjoint) the two sub-trees where disjointness holds is what allows
not only implementing the partial order (see the previous observation) but also saving
a lot of useless calls to the node matching functions. The fifth and last observation is
that the implementation of TreeMatch crucially depends on the fact that the minimal
elements of the two directions of subsumption and disjointness can be computed in-
dependently (modulo inconsistencies).
5 Evaluation
The algorithm presented in the previous section, let us call it MinSMatch, has been
implemented by taking the node matching routines of the state of the art matcher
SMatch [5] and by changing the way the tree structure is matched. The evaluation has
been performed by directly comparing the results of MinSMatch and SMatch on sev-
eral real-world datasets. All tests have been performed on a Pentium D 3.40GHz with
2GB of RAM running Windows XP SP3 operating system with no additional applica-
tions running except the matching system. Both systems were limited to allocating no
more than 1GB of RAM. The tuning parameters were set to the default values. The
selected datasets had been already used in previous evaluations, see [14]. Some of
these datasets can be found at OAEI web site2. The first two datasets describe courses
and will be called Cornell and Washington, respectively. The second two come from
the arts domain and will be referred to as Topia and Icon, respectively. The third two
datasets have been extracted from the Looksmart, Google and Yahoo! directories and
will be referred to as Source and Target. The fourth two datasets contain portions of
the two business directories eCl@ss3 and UNSPSC4 and will be referred to as Eclass
and Unspsc. Table 1 describes some indicators of the complexity of these datasets.
# Dataset pair Node count Max depth Average
branching factor
1 Cornell/Washington 34/39 3/3 5.50/4.75
2 Topia/Icon 542/999 2/9 8.19/3.66
3 Source/Target 2857/6628 11/15 2.04/1.94
4 Eclass/Unspsc 3358/5293 4/4 3.18/9.09
Table 1. Complexity of the datasets
Consider Table 2. The reduction in the last column is calculated as (1-m/t), where
m is the number of elements in the minimal set and t is the total number of elements
in the mapping of maximum size, as computed by MinSMatch. As it can be easily no-
ticed, we have a significant reduction, in the range 68-96%.
The second interesting observation is that in Table 2, in the last two experiments,
the number of total mapping elements computed by MinSMatch is slightly higher
(compare the second and the third column). This is due to the fact that in the presence
of one of the patterns, MinSMatch directly infers the existence of a mapping element
without testing it. This allows MinSMacth, differently from SMatch, to avoid missing
2 http://oaei.ontologymatching.org/2006/directory/
3 http://www.eclass-online.com/
4
http://www.unspsc.org/
elements because of failures of the node matching functions (because of lack of back-
ground knowledge [8]). One such example from our experiments is reported below
(directories Source and Target):
\Top\Computers\Internet\Broadcasting\Video Shows
\Top\Computing\Internet\Fun & Games\Audio & Video\Movies
We have a minimal mapping element which states that Video Shows ⊒ Movies.
The element generated by this minimal one, which is captured by MinSMatch and
missed by SMatch (because of the lack of background knowledge about the relation
between ‘Broadcasting’ and ‘Movies’) states that Broadcasting ⊒ Movies.
S-Match MinSMatch
# Total mapping Total mapping Minimal mapping Reduction, %
elements (t) elements (t) elements (m)
1 223 223 36 83.86
2 5491 5491 243 95.57
3 282638 282648 30956 89.05
4 39590 39818 12754 67.97
Table 2. Mapping sizes.
To conclude our analysis, Table 3 shows the reduction in computation time and
calls to SAT. As it can be noticed, the time reductions are substantial, in the range
16% - 59%, but where the smallest savings are for very small ontologies. In principle,
the deeper the ontologies the more we should save. The interested reader can refer to
[5, 14] for a detailed qualitative and performance evaluation of SMatch w.r.t. other
state of the art matching algorithms.
Run Time, ms SAT calls
# S-Match MinSMatch Reduction, S-Match MinSMatch Reduction,
% %
1 472 397 15.88 3978 2273 42.86
2 141040 67125 52.40 1624374 616371 62.05
3 3593058 1847252 48.58 56808588 19246095 66.12
4 6440952 2642064 58.98 53321682 17961866 66.31
Table 3. Run time and SAT problems
6 Conclusions
In this paper we have provided a definition and a fast algorithm for the computa-
tion of the minimal mapping between two lightweight ontologies. The evaluation
shows a substantial improvement in the (much lower) computation time, in the (much
lower) number of elements which need to be stored and handled and in the (higher)
total number of mapping elements which are computed.
The future work includes the experimentation with various large Knowledge Or-
ganization Systems (e.g., NALT, AGROVOC, LCSH).
References
1. F. Giunchiglia, M. Marchese, I. Zaihrayeu, 2006. Encoding Classifications into Light-
weight Ontologies. Journal of Data Semantics 8, pp. 57-81.
2. P. Shvaiko, J. Euzenat, 2007. Ontology Matching. Springer-Verlag New York, Inc. Se-
caucus, NJ, USA.
3. P. Shvaiko, J. Euzenat, 2008. Ten Challenges for Ontology Matching. In Proceedings of the
7th International Conference on Ontologies, Databases, and Applications of Semantics
(ODBASE 2008).
4. J. Madhavan, P. A. Bernstein, P. Domingos, A. Y. Halevy, 2002. Representing and Rea-
soning about Mappings between Domain Models. At the 18th National Conference on Arti-
ficial Intelligence (AAAI 2002).
5. F. Giunchiglia, M. Yatskevich, P. Shvaiko, 2007. Semantic Matching: algorithms and im-
plementation. Journal on Data Semantics, IX, 2007.
6. C. Caracciolo, J. Euzenat, L. Hollink, R. Ichise, A. Isaac, V. Malaisé, C. Meilicke, J. Pane,
P. Shvaiko, 2008. First results of the Ontology Alignment Evaluation Initiative 2008.
7. F.Giunchiglia, I. Zaihrayeu, 2007. Lightweight Ontologies. In The Encyclopedia of Data-
base Systems, to appear. Springer, 2008.
8. F.Giunchiglia, P. Shvaiko, M. Yatskevich, 2006. Discovering missing background knowl-
edge in ontology matching. Proceedings of the 17th European Conference on Artificial In-
telligence (ECAI 2006), pp. 382–386.
9. H. Stuckenschmidt, L. Serafini, H. Wache, 2006. Reasoning about Ontology Mappings.
Proceedings of the ECAI-06 Workshop on Contextual Representation and Reasoning.
10. C. Meilicke, H. Stuckenschmidt, A. Tamilin, 2006. Improving automatically created map-
pings using logical reasoning. In the proceedings of the 1st International Workshop on On-
tology Matching OM-2006, CEUR Workshop Proceedings Vol. 225.
11. C. Meilicke, H. Stuckenschmidt, A. Tamilin, 2008. Reasoning support for mapping revi-
sion. Journal of Logic and Computation, 2008.
12. A. Borgida, L. Serafini. Distributed Description Logics: Assimilating Information from
Peer Sources. Journal on Data Semantics pp. 153-184.
13. I. Zaihrayeu, L. Sun, F. Giunchiglia, W. Pan, Q. Ju, M. Chi, and X. Huang, 2007. From
web directories to ontologies: Natural language processing challenges. In 6th International
Semantic Web Conference (ISWC 2007).
14. P. Avesani, F. Giunchiglia and M. Yatskevich, 2005. A Large Scale Taxonomy Mapping
Evaluation. In Proceedings of International Semantic Web Conference (ISWC 2005),
pp. 67-81.
15. M. L. Zeng, L. M. Chan, 2004. Trends and Issues in Establishing Interoperability Among
Knowledge Organization Systems. Journal of the American Society for Information Sci-
ence and Technology, 55(5) pp. 377–395.
16. L. Kovács. A. Micsik, 2007. Extending Semantic Matching Towards Digital Library Con-
texts. Proc.eedings of the 11th European Conference on Digital Libraries (ECDL 2007), pp.
285-296.
17. B. Marshall, T. Madhusudan, 2004. Element matching in concept maps. Proceedings of the
4th ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL 2004), pp.186-187.
18. B. Hjørland, 2008. What is Knowledge Organization (KO)?. Knowledge Organization. In-
ternational Journal devoted to Concept Theory, Classification, Indexing and Knowledge
Representation 35(2/3) pp. 86-101.
19. D. Soergel, 1972. A Universal Source Thesaurus as a Classification Generator. Journal of
the American Society for Information Science 23(5), pp. 299–305.
20. D. Vizine-Goetz, C. Hickey, A. Houghton, and R. Thompson. 2004. Vocabulary Mapping
for Terminology Services. Journal of Digital Information, Volume 4, Issue 4.
21. M. Doerr, 2001. Semantic Problems of Thesaurus Mapping. Journal of Digital Information,
Volume 1, Issue 8.
22. F. Giunchiglia, V. Maltese, A. Autayeu, 2008. Computing minimal mappings. University
of Trento, DISI Technical Report: http://eprints.biblio.unitn.it/archive/00001525/