Jorge Martinez-Gil

José F Aldana-Montes

Knowledge and Information Systems

Keywords: Ontology Meta-Matching, Knowledge Management, Information Integration

Evaluation of two heuristic approaches to solve the ontology meta-matching problem

Introduction

The Semantic Web is a promising paradigm for the Web in which the semantics of information is defined, making it possible for the Web to understand and satisfy all of the requests from people and machines using the web resources. Therefore, most authors consider the Web as an universal medium for data, information, and knowledge exchange (Berners- [START_REF] Lee | eTuner: tuning schema matching software using synthetic scenarios[END_REF].

In relation to knowledge, it is very important the notion of ontology as a form of representation about a particular universe of discourse or some part of it. Ontology matching is fundamental so that appropriate knowledge exchange in this extension of the Web can be possible; it allows organizations to model their knowledge without having to stick to a specific standard. In fact, there are two good reasons why most organizations are not interested in working with a standard for modeling their own knowledge: (a) it is very difficult or expensive for many organizations to reach agreement about a common standard, and (b) those standards which do exist often do not fit in with the specific needs of all the participants.

Although automatic matching is perhaps the most appropriate way to align ontologies, it has the disadvantage that finding good similarity functions is, data, context, and sometimes even user-dependent, and needs to be reconsidered every time new data or a new task is inspected [START_REF] Kiefer | The Fundamentals of iSPARQL: A Virtual Triple Approach for Similarity-Based Semantic Web Tasks[END_REF]. Moreover, dealing with natural language often leads to a significant error rate. This last statement is very important for those authors who do not easily allow interpretation of the intellectual nature of a given concept by a machine [START_REF] Doerr | Semantic Problems of Thesaurus Mapping[END_REF]. However, they admit that automatic methods are far cheaper and can detect relations of which humans are unaware. We are convinced that the future lies in the coordinated combination of intellectual and automatic methods. But in this work, we are going to try to find customized similarity functions (CSF) in order to obtain the best ontology alignment for each situation.

On the other hand, functions for calculating alignments can be divided into similarity measures and distance measures.

-A similarity measure is a function that associates a numeric value with a pair of objects, based on the idea that a higher value indicates greater similarity. -A distance measure is a function that associates a non-negative numeric value with a pair of objects, based on the idea that a short distance means greater similarity. Distance measures usually satisfy the mathematical axioms of a metric.

In practice, there are long-standing psychological objections to the axioms used to define a distance metric. For example, a metric will always give the same distance from a to b as from b to a, but in practice we are more likely to say that a child resembles their parent than to say that a parent resembles their child [START_REF] Widdows | Geometry and Meaning[END_REF]. Similarity measures, however, give us an idea about the probability of compared objects being the same [START_REF] Pfitzner | Characterization and evaluation of similarity measures for pairs of clusterings[END_REF], but without falling into the psychological objections of a metric. So from our point of view, working with similarity measures is more appropriate for detecting correspondences between different ontologies belonging to same domain. In this sense, Ontology Meta-Matching could be considered a technique that automatically selects the appropriate similarity measures and their associated weights in the case where similarity measures need to be composed. It tries to avoid the research work which depends heavily on human thought. Ontology Meta-Matching can be performed in several ways. We have designed one greedy and one genetic algorithm. The greedy algorithm allows us to obtain reasonable results with a low computational cost and, the advantages inherent to the second strategy are its great accuracy and scalability. The main contributions of this work are:

-An introduction to the problem of Ontology Meta-Matching.

-A greedy algorithm for solving the problem automatically and efficiently.

-A genetic algorithm for optimizing the solutions to the problem.

-An empirical evaluation of the proposed algorithms and a discussion of their advantages.

The remainder of this article is organized as follows. Section 2 describes the problem statement related to the Ontology Meta-Matching problem, describes the preliminary definitions and properties that are necessary for understanding our proposal and and compares our proposal to the other approaches that try to solve the problem. Section 3 discusses a greedy strategy and a way to effectively compute it. Section 4 describes a genetic strategy and a way to implement it. Section 5 shows the empirical data that we have obtained from some experiments, including results obtained from a standard benchmark for ontology matching. Section 6 includes the related work section which compares our work with other approaches. And finally, in Section 7 the conclusions are discussed.

Problem Statement

The process of aligning ontologies can be expressed as a function f where given a pair of ontologies O and O , an input alignment A, a set of parameters p and a set of resources r, an alignment A is returned::

A = f (O, O , A, p, r)
Where A is a set of mappings. A mapping 1 is an expression that can be written in the form (id, e, e , n, R). Where id is an unique identifier for the mapping, e and e are entities belonging to different ontologies, R is the relation of correspondence and n is a real number between 0 and 1, which represents the mathematical probability that R may be true [START_REF] Ehrig | Ontology Alignment: Bridging the Semantic Gap[END_REF]. The entities that can be related are the concepts, roles, rules and, even axioms of the ontologies.

However, experience tells us that finding f is far from being trivial. As we commented earlier, the heterogeneity and ambiguity of data description makes it unavoidable that optimal mappings for many pairs of entities will be considered as "best mappings" by none of the existing ontology matching algorithms which are usually called matchers. For this reason, it is necessary to compose these simple matchers. Figure 1 shows an example of an user-dependent alignment between ontologies, because this alignment is not valid for all the countries in the world.

Composite matchers are an aggregation of simple matching algorithms, usually called matchers. Matchers exploit a wide range of information, such as ontology characteristics (i.e. metadata, such as element names, data types, and structural properties), characteristics of data instances, as well as background knowledge from dictionaries and thesauri.

1. String normalization. This consists of methods such as removing unnecessary words or symbols from the entity names. Moreover, they can be used for detecting plural nouns or to take into account common prefixes or suffixes as well as other natural language features. 2. String similarity. Text similarity is a string based method for identifying similar entity names. For example, it may be used to identify identical concepts of two ontologies if they have a similar name. The reader can see [START_REF] Navarro | A guided tour to approximate string matching[END_REF] for a classical approach to the problem or [START_REF] Woon | String alignment for automated document versioning[END_REF] for a more modern point of view. as lexicons and thesauri to identify possible similarities. Some of most popular linguistic method is to use WordNet (Wordnet, 2008) to identify some kinds of relationships between entities or background knowledge from the web in general [START_REF] Rosenfeld | Self-supervised relation extraction from the Web[END_REF] or from more specific sources as Wikipedia as the work presented in [START_REF] Wang | Using Wikipedia knowledge to improve text classification[END_REF]. 5. Inheritance analysis. These kinds of methods take into account the inheritance between concepts to identify relationships. The most popular method is the is-a analysis that tries to identify subsumptions between concepts. 6. Data analysis. These kinds of methods are based on the rule: If two concepts have the same instances, they will probably be similar. Sometimes, it is possible to identify the meaning of an upper level entity by looking at a lower level one. For example, if instances contain a string such as years old, it probably belongs to an attribute called age. 7. Graph-Mapping. This consists of identifying similar graph structures in two ontologies. These methods use known graph algorithms to do so. Most of times this involves computing and comparing paths, adjacent nodes and taxonomy leaves. For example [START_REF] Maguitman | Algorithmic computation and approximation of semantic similarity[END_REF]. 8. Statistical analysis. It consists of the extraction of keywords and textual de-scriptions for detecting the meaning of the entities in relation to other entities. For example (Martinez-Gil et al, 2008). 9. Taxonomy analysis. It tries to identify similar concepts by looking at their related concepts. The main idea is that two concepts belonging to different ontologies have a certain degree of probability of being similar if they have the same neighbours. 10. Semantic methods According to [START_REF] Euzenat | Ontology Matching[END_REF], semantic algorithms handle the input based on its semantic interpretation. One supposes that if two entities are the same, then they share the same interpretation. Thus, these are well grounded deductive methods. Most outstanding approaches are description logics reasoning techniques.

However, choosing from among this variety of algorithms is far from being a trivial task. Firstly, more and more are constantly being developed, and this diversity in itself complicates the choice of the most appropriate for a given application domain. Secondly, recent empirical analysis shows that there is no (and may never be) single dominant matcher that performs best, regardless of the data model and application domain [START_REF] Kiefer | The Fundamentals of iSPARQL: A Virtual Triple Approach for Similarity-Based Semantic Web Tasks[END_REF]. In fact, due to effectively unlimited heterogeneity and the ambiguity of data description used in the ontology development, it seems unavoidable that optimal mappings for many pairs of correspondences will be considered as best mappings by none of the existing matchers. For this reason, it is necessary to use composite matchers. Using composite matchers has the advantage that all matching algorithms are considered as black boxes in order to select the most appropriates. In this way, automatically methods are able to tighten or loosen the matching function automatically if necessary. This means that it is not necessary for users to decide which algorithms have to be used.

The main idea of composite matchers is to combine similarity values predicted by multiple similarity measures to determine correspondences between ontology elements. The most outstanding proposals in this area are COMA [START_REF] Do | COMA -A System for Flexible Combination of Schema Matching Approaches[END_REF], COMA++ (Amueller et al, 2005), QuickMig [START_REF] Drumm | Quickmig: automatic schema matching for data migration projects[END_REF] and OntoBuilder [START_REF] Gal | A framework for modeling and evaluating automatic semantic reconciliation[END_REF], but these proposals use weights determined by an expert. Meta-Matching does not use weights from an expert, but selects those that would solve the problem according to a training benchmark, which is a set of ontologies that have been previously aligned by an expert.

Technical Background

Definition 1 (Similarity Measure). A similarity measure sm is a function sm : µ 1 × µ 2 → R that associates the similarity of two input terms µ 1 and µ 2 to a similarity score sc ∈ in the range [0, 1]. This definition has been taken from [START_REF] Kiefer | The Fundamentals of iSPARQL: A Virtual Triple Approach for Similarity-Based Semantic Web Tasks[END_REF] Moreover, we need to know that a similarity score of 0 stands for complete inequality and 1 for equality of the input terms µ 1 and µ 2 .

Definition 2 (Customizable Similarity Measure). A Customizable Similarity Measure is a similarity measure that can be parametrized. Example 1 shows a function of this type.

Example 1 (Weighted Similarity Measure). Let A be a vector of similarity measures and w a weight vector and let O 1 , O 2 be two input ontologies, then we can define wsm as a weighted similarity measure in the following form:

wsm(O 1 , O 2 ) = x ∈ [0, 1] ∈ → ∃ A, w , x = max( i=n i=1 A i • w i )
with the following restriction i=n i=1 w i ≤ κ But from an engineering point of view, this function leads to an optimization problem for calculating the weight vector, because the number of candidates from the solution space (in this case an arbitrary continuous and real interval) is infinite. For this reason, a brute force strategy would clearly be inefficient. It is necessary to look for better computational mechanisms that allow the problem of computing weighted measures to be solved more efficiently.

Definition 3 (Ontology Matching). An ontology matching om is a function om : O 1 × O 2 sm → A that associates two input ontologies O 1 and O 2 to an alignment A using a similarity measure (or a customizable similarity measure).

Definition 4 (Ontology Alignment). An ontology alignment oa is a set {t, M D}. t is a set of tuples in the form {(id, e, e , n, R)}. Where id is a unique identifier, e and e are entities belonging to two different ontologies, R is the relation of correspondence between these entities and n is a real number between 0 and 1 representing the mathematical probability that R may be true. The entities than can be related are the concepts, roles, rules and, even axioms of the ontologies. On the other hand, MD is some metadata related to the matching process for statistical purposes.

Definition 5 (Alignment Evaluation). An alignment evaluation ae is a function ae :

A × A R → precision ∈ ∈ [0, 1] × recall ∈ ∈ [0, 1]
that associates an alignment A and a reference alignment A R to three real numbers stating the precision, recall and fall-out of A in relation to A R .

Definition 6 (Meta-Matching Function). A Meta-Matching Function mmf is a function mmf : SC → that defines how previously calculated similarity score sc i ∈ SC. The result is an optimized similarity score sc o ∈ . We call optimized similarity score to the best possible value, thus, the similarity score closest to 1 that we can achieve.

Meta-matching Techniques

What exactly is ontology Meta-Matching in practice? It is the technique of selecting the appropriate algorithms, weights and thresholds in ontology matching scenarios in order to obtain a satisfactory alignment between ontologies. Figure 2 shows a diagram for modeling the actions in a Meta-Matching process.

Note that algorithms do not need to be reconsidered. The idea is to provide all possible algorithms initially and then automatically associate a weight of 0 to those that are not useful for solving the problem. How the algorithms are used or the weights and the threshold recalculated are what makes one Meta-Matching strategy better than another, in terms of accuracy and time consumption.

Fig. 2. General model for Meta-Matching

In general, we can describe the following as characteristics of a Meta-Matching task:

-It is not necessary for it to be done at runtime. Functions are computed and can be reused. -It must be an automatic process, because it is a problem with a very complex computational nature. -It must return the best possible matching function, thus, the function that best mimics the behavior of a human expert user.

Moreover, Meta-matching can be seen from two points of view: (i) From the point of view of the algorithmic techniques used to obtain the matching function:

-Aggregation. This technique [START_REF] Domshlak | Rank Aggregation for Automatic Schema Matching[END_REF] determines the upper bound T(n) on the values obtained from a sequence of n matchers, then calculates the average value to be T(n)/n. -Combination. The main idea is to combine similarity values predicted by multiple matchers to determine correspondences between ontology entities.

Where combinations can be as simple as: arithmetic or harmonic means, maximum, minimum, Minkowski distances, any kind of weighted product or sum, and so on, or more complex combinations like Linguistic Combinations [START_REF] Ji | LCS: A Linguistic Combination System for Ontology Matching[END_REF])

-Composition. Let f 1 , f 2 , ..., f n be n unique matchers, a composition is a function f (O 1 , O 2 ) = f 1 • f 2 • ... • f n .
Thus, the idea of this mechanism is to use simple functions to build more complicated ones (ii) From the point of view of the computer science paradigm that makes the Meta-Matching possible, i.e. the form of recalculating the parameters. Although, this problem can be solved trivially by a brute force search when the number of matchers to use is low, Meta-Matching scales better for a higher number of matchers. For this reason we do not include brute force methods as a viable technique. These are the two main groups of techniques considered:

-Heuristic Meta-Matching, where the most outstanding approaches are

Based on Genetic Algorithms meta-matching. In this case, it is said that parameters are optimized and, Greedy meta-matching, in such case, it is said that parameters are estimated. In Genetic Strategies, solutions tend to scale better and in Greedy techniques, solutions are obtained more quickly. -Based on Machine Learning meta-matching, where the most outstanding approaches are Relevance Feedback and Neural networks training for metamatching. In both cases, it is said that parameters are learned.

Heuristic Meta-Matching.

A heuristic is a method to help to solve a problem, commonly informal. It is used particularly for a method that may lead to a solution which is usually reasonably close to the best possible answer. Two fundamental goals in computer science are to find algorithms with probably good run times and with probably good or optimal solution quality. A heuristic is an algorithm that abandons one or both of these goals; for example, it usually finds pretty good solutions, but there is no proof that the solutions could not get arbitrarily bad; or it usually runs reasonably quickly, but there is no argument that this will always be the case.

Therefore, the use of heuristics is very common in real world implementations. For many practical problems, a heuristic algorithm may be the only way to get good solutions within a reasonable amount of time.

A lot of tools clearly implement heuristic Meta-Matching, we can see the clearest example in the default configuration of COMA [START_REF] Do | COMA -A System for Flexible Combination of Schema Matching Approaches[END_REF], where an expert has initially adjusted the weights of the conceptual and structural techniques respectively. In order to avoid human interaction in this field, we can use Genetic Algorithms for optimizing the parameters or Greedy Algorithms to estimate them.

Based on Genetic Algorithm methods. Based on Genetic Algorithm methods [START_REF] Forrest | Genetic Algorithms[END_REF] are adaptive heuristic search algorithms premised on the evolutionary ideas of natural selection and genetics. The basic concept of GAs is designed to simulate the natural evolutionary system.

This approach is able to work with several goals (Martinez-Gil and Aldana-Montes, 2008): maximizing the precision, maximizing the recall, maximizing the fMeasure or reducing the number of false positives. Moreover, it has been tested combining some leading-edge similarity measures over a standard benchmark and produced some good results.

Another proposal is [START_REF] Wang | GAOM: Genetic Algorithm based Ontology Matching[END_REF], a genetic algorithm-based optimization procedure for the ontology matching problem that is presented as a featurematching process. First, from a global view, they model the problem of ontology matching as an optimization problem of a mapping between two compared ontologies, with each ontology having its associated feature sets. Secondly, as a powerful heuristic search strategy, a genetic algorithm is employed for the ontology matching problem. Given a certain mapping as optimizing object for GA, a fitness function is defined as a global similarity measure function between two ontologies based on feature sets.

Greedy Meta-Matching Greedy (Cohen et al, 1996) Meta-Matching is a technique which, given a particular matching task, tries to automatically tune an ontology matching function. For that purpose, it tries to choose the best matchers and parameters to be used, but with a short-sighted strategy. The most popular example of this technique can be found at [START_REF] Lee | eTuner: tuning schema matching software using synthetic scenarios[END_REF]. Results from Greedy techniques are, in general, worse than those based on Genetics, but its computation time also tends to be much lower.

Based on Machine Learning Methods

Based on Machine Learning (Langey, 1994) Meta-Matching techniques considers both schema information and instance data. This kind of Meta-Matching can be divided into two subtypes2 (i) Relevance Feedback and (ii) Neural Networks.

Relevance Feedback. This kind of approach explores the user validation of initial ontology alignments for automatically optimizing the configuration parameters of the matching strategies. A clear example of this kind of Meta-Matching is [START_REF] Lee | eTuner: tuning schema matching software using synthetic scenarios[END_REF]. Using such techniques we are able to avoid the user, and maybe the context, the dependency of the matching task, however, it implies spending a lot of time on training the systems. To do that automatically, it is possible to use Neural Networks.

Neural Networks Training. A neural network [START_REF] Jordan | Neural Networks[END_REF]) is an interconnected group of artificial neurons that uses a mathematical or computational model for information processing based on a connectionistic approach to computation. In most cases a neural network is an adaptive system that changes its structure based on external or internal information flowing through the network. In more practical terms neural, networks are non-linear statistical data modeling or decision making tools. They can be used to model complex relationships between inputs and outputs or to find patterns in data.

Neural networks training for Meta-Matching consists of training a neural network with heterogeneous enough benchmarks and then using the knowledge to predict new similarity functions. This is the case of [START_REF] Huang | Ontology Matching Using an Artificial Neural Network to Learn Weights[END_REF] where authors exploit an approach to learn the weights for different semantic aspects of ontologies, through applying an artificial neural networks technique.

Another approach consists of an automatic ontology alignment method based on the recursive neural network model that uses ontology instances to learn similarities between ontology concepts. Recursive neural networks are an extension of common neural networks, designed to process efficiently structured data [START_REF] Chortaras | Learning Ontology Alignments Using Recursive Neural Networks[END_REF].

Greedy Strategy

In this section, we are going to discuss the greedy strategy to solve the Meta-Matching problem. Moreover, we propose an efficient greedy algorithm and compute its associated complexity according to the big O notation.

Maximum Similarity Measure

An initial approach for an ideal Customizable Similarity Measure which would be defined in the following way:

Let A be a vector of atomic matching algorithms in the form of a similarity measure and w a numeric weight vector then:

M aSiM e(c1, c2) = x ∈ [0, 1] ∈ → ∃ A, w , x = max( i=n i=1 A i • w i )
with the following restriction i=n i=1 w i ≤ 1 But as we showed in Section 3, this kind of measure leads to an optimization problem for calculating the weight vector, because the number of candidates from the solution space is infinite. For this reason, we present MaSiMe, which uses the notion of granularity for setting a finite number of candidates in that solution space. This solution means that the problem of computing the similarity can be solved in a polynomial time.

Definition 7. Maximum Similarity Measure (MaSiMe).

M aSiM e(c1, c2) = x ∈ [0, 1] ∈ → ∃ A, w, g , x = max( i=n i=1 A i • w i ) with the following restrictions i=n i=1 w i ≤ 1 ∧ ∀w i ∈ w, w i ∈ {g} Example 2.
Given an arbitrary set of algorithms and a granularity of 0.05, calculate MaSiMe for the pair (author, name author).

M aSiM e(author, name author) = .542 ∈ [0, 1] → ∃ A = (L, B, M, Q), w = (0.8, 0, 0, 0.2), g = 0.05 , 0.542 = max( (Levenshtein, 1996), B = BlockDistance [START_REF] Ziegler | Detecting Similarities in Ontologies with the SOQA-SimPack Toolkit[END_REF], M = MatchingCoefficient [START_REF] Ziegler | Detecting Similarities in Ontologies with the SOQA-SimPack Toolkit[END_REF] , Q = QGramsDistance [START_REF] Ukkonen | Approximate String Matching with q-grams and Maximal Matches[END_REF] This example shows an entity alignment, however, MaSiMe can be applied with different kinds of granularity:

i=4 i=1 A i • w i ) Where L = Levhenstein
-Entity-Entity. In this case, we may compute the best weights to align a pair of entities. -Ontology-Ontology. In this case, MaSiMe may compute the best weighted function for aligning two input ontologies. -Benchmark Level. This kind of calculation implies the computation of the best weights for a whole benchmark.

There are several properties for Definition 3:

Property 1 (Continuous uniform distribution). A priori, MaSiMe presents a continuous uniform distribution in the interval [0, 1], that is to say, its probability density function is characterized by

∀ a, b ∈ [0, 1] → f (x) = 1 b -a f or a ≤ x ≤ b
Property 2 (Maximality). If one of the algorithms belonging to the set of matching algorithms returns a similarity of 1, then the value of MaSiMe is 1.

∃A i ∈ A, A i (c1, c2) = 1 → M aSiM e(c1, c2) = 1
Moreover, the reciprocal is true

M aSiM e(c1, c2) = 1 → ∃A i ∈ A, A i (c1, c2) = 1
Example 3. Let us suppose that we have: A = (Google Similarity Distance [START_REF] Ehrig | Ontology Alignment: Bridging the Semantic Gap[END_REF], BlockDistance, MatchingCoefficient, QGramsDistance) and g = 0.05, calculate w for maximizing R in the mapping (plane, aeroplane, Equivalence, R) Solution:

(1, 0, 0, 0)

So the optimum matching algorithm for the equivalence of (plane, aeroplane) in this case would be:

1 • GoogleDistance + 0 • BlockDistance + 0 • M atchingCoef f icient + 0 • QGramsDistance, R = 0.555
Moreover, we can say that the worst vector is w = (0, 0.8, 0.15, 0.05) because it generates R = 0.027

Property 3 (Monotonocity). Let S be a set of matching algorithms, and let S' be a superset of S. If MaSiMe has a specific value for S, then the value for S' is either equal to or greater than this value.

∀S ⊃ S, M aSiM e s = x → M aSiM e s ≥ x Property 4. (Dependent completeness). If one of the algorithms belonging to the set of matching algorithms provides a similarity of 1 and the chosen granularity is not a submultiple (notation ˙) of 1, then the value of MaSiMe is less than 1.

∃A i ∈ A ∧ 1 / ∈ {g} ∧ A i (c1, c2) = 1 → M aSiM e(c1, c2) < 1
Example 4. Let us suppose we have the same conditions as in Example 3, i.e., that we have: A = (Google Similarity Distance, BlockDistance, MatchingCoefficient, QGramsDistance) but now g = 0.21. Calculate w for maximizing R in the mapping (plane, aeroplane, Equivalence, R) Solution:

(0.84, 0, 0, 0) So the optimum matching algorithm for the equivalence for (plane, aeroplane) is not the same as that in Example 3.

The reason is that if the granularity is not a multiple of 1, the summation from the weight vector cannot be 1, and therefore A • w cannot be optimal.

Computing the Weight Vector

Once the problem is clear and the parameters A and g are known, it is necessary to effectively compute the weight vector. At this point, we leave the field of similarity measures to move into the field of programming engineering.

It is possible to compute MaSiMe in several ways, for this work, we have designed a greedy mechanism that seems to be effective and efficient. The following paragraphs discuss this mechanism.

Greedy strategy.

A greedy strategy follows the problem solving heuristic of making the locally optimum choice at each stage with the hope of finding the global optimum.

Theorem 1 (About computing MaSiMe). Let S be the set of all the matching algorithms, let A be the subset of S, thus, the set of matching algorithms that we want to use, let g be the granularity, let Q the set of positive Rational Numbers, let i, j, k, ..., t be indexes belonging to the set of multiples for the granularity (denoted {g}) then, a set of rational vectors r exists where each element r i is result of the scalar product between A and the index pattern (i, j -i, k -j, ..., 1 -t). All of this subject to j ≥ i ∧ k ≥ j ∧ 1 ≥ k. Moreover, the final result, called R, is the maximum of the elements r i and is always less or equal than 1.

And in mathematical form:

∃A ⊂ S, ∃g ∈ [0, 1] ∈ Q+, ∀i, j, k, ..., t ∈ {g} → ∃ r, r i = A • (i, j -i, k -j, ..., 1 -t)
with the followings restrictions j

≥ i ∧ k ≥ j ∧ 1 ≥ k R = max (r i ) ≤ 1
Proof (Theorem 1). r i is by definition the scalar product between a vector of matching algorithms that implements similarity measures and the pattern (i, j -i, k -j, ..., 1 -t). In this case, a similarity measure cannot be greater than 1 by Definition 1 and the sum of the pattern indexes cannot be greater than 1 by restriction (i, j -i, k -j, ..., 1 -t), so scalar product of such factors cannot be greater than 1.

Now, we are going to show how to implement the computation of MaSiMe by using an imperative programming language. Algorithm 1 shows the pseudocode implementation for this theorem.

The algorithm can be stopped when it obtains a partial result equal to 1, because this is the maximum value than we can hope for.

Input: ontology: O, O Input: algorithm vector: A Input: granularity: g Output: M aSiM e foreach pair (c1, c2) of entities ∈O and O'do The strategy seems to be brute force, but it is not. It should be taken into account that the input data size is n length of A , but the computational complexity for the algorithm according to O notation is

foreach index i, j, k, ..., t ∈ κ × g do result = A 1 (c1, c2) • i + A 2 (c1, c2) • j -i + A 3 (c1, c2) • k -j + A 4 (c1, c2) • t -k + ... A n (c1, c2) • 1 -t ; if result > M
O(n length of A -1)
In this way, the total complexity (TC) for MaSiMe is:

T C(M aSiM e A ) = O(max(max(O(A i )), O(strategy)))
and therefore for MaSiMe using the greedy strategy

T C(M aSiM e A ) = O(max(max(O(A i ), O(n length of A-1 )))
Example 5. Given the set A = {Levhenstein, BlockDistance, MatchingCoefficient, QGrams-Distance} , the complexity for the matching process using MaSiMe is calculated.

T C(M aSiM e

A ) = O(max(O(n 2 ), O(n 3 ))) = O(n 3 )
Brute force complexity for 4 matching algorithms may require 4 loops, MaSiMe requires 3 loops, so we can conclude that O m < O bf .

Genetic Strategy

Genetic Algorithms (GAs) are often used to search along very high dimensional problems spaces. For example, if we want to find the maximum value of the function wsf with three independent variables x, y and z:

wsf (O 1 , O 2 ) = x • datatype(O 1 , O 2 ) + y • normalization(O 1 , O 2 ) + z • synonyms(O 1 , O 2 )
where x, y and z are weights to determine the importance of the three associated similarity measures, which belong, for instance, to the continuous interval [0,1]. The problem that we want to solve is to find a good value of x, y and z in order to find the largest possible value of wsf .

While this problem can be solved trivially by a brute force search over the range of the independent variables x, y and z, the GA method scales very well to similar problems of a higher dimensionality; for example, we might have functions using a large number of independent variables x, y, z,..., t. In this case, an exhaustive search would be prohibitively expensive.

The methodology of the application of a GA requires defining the following strategies:

-Characterize the problem by encoding in a string of values the contents of a tentative solution.

-Provide a numeric fitness function that will allow the relative quality of each individual tentative solution in a population to be rated.

GOAL

Now, we describe the method to solve meta-matching schemas that we have developed using Genetic Algorithms.

Definition 8. Genetics for Ontology ALignments (GOAL). It is an elitist genetic algorithm which works under the paradigm of a single goal programming strategy. The idea behind GOAL is to automatically tune a combination of basic matching algorithms using sample cases solved by experts. The goal to optimize can be whatever specific aspect resulting from the evaluation of the matching tasks.

GOAL is designed to work with lots of basic algorithms, all of them are chosen on the basis of their results, instead of their behavior, so can be considered as black boxes. The idea behind GOAL is that each component of the weight vector is associated to a basic matching algorithm. If we measure the distance between the result generated using the weight vector and the fitness value, we can know how good a weight vector is. In fact, we can know what the best weight vector is. Now we can interpret this vector; a value of 0 associated to a matching algorithm means that such algorithm is not relevant to solve the problem. A value between 0 and 1 means that the algorithm is relevant and if the value is 1 then the algorithm is able to solve the problem by itself.

Moreover, GOAL tries to not return local minimum for the weight vector associated to the matching function, because the crossover we introduce produces random chromosomes in order to extend the search space.

Apart from the quality of the results which we will evaluate in the next section, advantages inherent to GOAL are the great scalability and the possibility of avoiding the internal behavior of the basic matching algorithms.

Development

To develop GOAL, we have characterized the search space as some parameters. Then, we have encoded several parameters in a single chromosome, so we have designed a method for converting a 10-bit representation to a set of floating-point numbers in the arbitrary range [0,1].

Later, we have designed a fitness function to determine which chromosomes in the population are most likely to survive and reproduce using genetic crossover and mutation operations.

To return the fitness function, we can choose any parameter provided for the alignment evaluation process, i.e. precision, recall, fmeasure or fallout. In this way, we are providing the possibility of selecting one of these goals.

-Optimizing the precision (f itness := precision) -Optimizing the recall (f itness := recall) -Optimizing the fmeasure (f itness := f measure) -Reducing the number of false positives (f itness := f all -out) All of them are concepts used in Information Retrieval for measuring the quality of a retrieval task. Precision is the percentage of items returned that are relevant. Recall is the fraction of the items that are relevant to a query (in this case, to a matching task). fmeasure is a weighted sum from precision and recall. Finally, false positives are relationships which have been provided to the user even though they are false (Buckland and Gey, 1994). In some domains, (for instance in medicine) false positives are absolutely unwanted. Take into account that we know all of them because we are using a set of test cases solved by an expert (or committee of experts). So the resulting matching function will behave ideally as experts who solve the sample cases.

Preliminary Study

We are going to do a preliminary study of the parameters for the algorithm.

-For the number of genes per chromosome we have selected such values as 5, 10 and 20. A study using a t-Test distribution has shown us that that the differences between samples are not statistically significant. Therefore, we have selected 20 genes per chromosome. -For the number of individuals in the population, we have selected such values as 20, 50 and 100. Again, a t-Test statistical distribution has shown that the differences between these samples are not statistically significant. We have selected a population of 100 individuals. -Related to crossover and mutation fraction, we have chosen a high value for the crossover between genes and, a small percentage for mutations, because we wish a classical configuration for the algorithm. -After ten independent executions, we noticed that the genetic algorithm did not improve the results beyond the fifth generation, so we have set a limit of five generations.

Data to Repeat the Experiment

Related to the conditions of the experiment, we have used:

-As similarity measure vector: {Levhenstein (Levenshtein, 1996), SIFO(Martinez-Gil et al, 2008), Stoilos [START_REF] Stoilos | A String Metric for Ontology Alignment[END_REF], QGrams(Ukkonen, 1992)} -The GA has been configured taking the following parameters into account 3 :

• 20 genes per chromosome • A population of 100 individuals • 0.98 for crossover fraction • 0.05 for mutation fraction • We allow 5 generations -The platform characteristics: Intel Core 2 Duo, 2.33Ghz and 4GB RAM. The programming language was Java.

Evaluation

The evaluation of a Meta-Matching strategy consists of the evaluation of its returned matching function.

There are several ways to evaluate an output alignment:

-Compliance measures provide some insight on the quality of identified alignments. -Performance measures show how good the approach is in terms of computational resources. -User-related measures help to determine the overall subjective user satisfaction, partially measured, e.g., through user effort needed. -There are task-related measures, which measure how good the alignment was for a certain use case or application.

In practice, there is a certain degree of agreement to use some measures from the Information Retrieval field (Baeza-Yates and Ribeiro-Neto, 1999). These are: precision, recall, fmeasure and fallout. Table 2. Behavior of MaSiMe for the standard benchmark of the OAEI the quality of MaSiMe and GOAL using these formulas. These test cases belongs to the Ontology Matching Evaluation Initiative4 (OAEI). These test cases try to measure the quality of methods when solving several use cases which are common in ontology matching scenarios. On the other hands, using this set of data means that GOAL will behave as international experts who solve the sample cases included in the benchmark.

P recision

Table 2 shows the results we have obtained for the greedy strategy called MaSiMe. Table 3 shows the results we have obtained for the genetic strategy called GOAL. Figure 3 shows a graphical comparison of the two strategies we have used. Next subsection discusses the results. Table 3. Behavior of the GOAL for the standard benchmark of the OAEI Fig. 3. Comparative results between strategies

Discussion

Precision takes all retrieved correspondences into account because measures the number of correct correspondences divided by the number of all returned correspondences. We reach an average precision of 99 percent because, most of times, it is possible to find a weighted algorithm combination which retrieve only correct correspondences.

On the other hand, in theory, it is easy to achieve recall of 100 percent by returning all possible correspondences between two ontologies. But recall alone is not enough; it is necessary to measure the number of non-relevant correspondences also. To to that, we compute the precision. So take into account that recall is computed in relation to the precision on all of our experiments.

So we have that getting only a good precision or only a good recall is not enough in general purpose scenarios. It is necessary to obtain a good combination of them. For this reason, fmeasure appeared. Remember that our strategy can improve whatever specific aspect of a matching task even fmeasure what it is really one of the great advantages of this work. That it is to say, we can improve the pair precision-recall when defining this fmeasure as the parameter to optimize. Possibility to optimize this parameter makes that GOAL is better in terms Fig. 4. Comparison with other tools of accuracy than MaSiMe. MaSiMe is, however, an acceptable method for obtaining low cost results as we will see in the next section, where we compare these two strategies with other existing tools. In the future, we want to improve to a multiobjetive strategy (Pappa and Freitas, 2009) to avoid unwanted deviations from precision and recall values.

Related Work

If we look at the literature, we can distinguish between individual algorithms (i.e. Similarity Flooding [START_REF] Melnik | Similarity Flooding: A Versatile Graph Matching Algorithm and Its Application to Schema Matching[END_REF] or S-Match [START_REF] Giunchiglia | S-Match: an Algorithm and an Implementation of Semantic Matching[END_REF])) which apply only a single method of matching items i.e. linguistic or taxonomical matchers and combinations of the former ones, which intend to overcome their limitations by proposing hybrid and composite solutions. A hybrid approach (i.e.Cupid [START_REF] Madhavan | Generic Schema Matching with Cupid[END_REF])) follows a black box paradigm, in which various individual matchers are joined together in a new algorithm [START_REF] Domshlak | Rank Aggregation for Automatic Schema Matching[END_REF], while the so-called composite matchers allow increased user interaction (i.e. COMA++ (Amueller et al, 2005), Falcon [START_REF] Hu | The Results of Falcon-AO in the OAEI 2006 Campaign[END_REF], CtxMatch [START_REF] Niedbala | Evolving rule induction algorithms with multi-objective grammar-based genetic programming[END_REF], RiMOM [START_REF] Li | Result of Ontology Alignment with RiMOM at OAEI'06[END_REF]).

The problem is that those kinds of proposals, in the best of cases, use weights defined by an expert for configuring the matchers, but using our approaches involves computing the weights in an automatic way, so that the process can be more accurate. In Figure 4, we can see a comparison between some of the most popular tools for matching ontologies. The figure represents the arithmetic means of the values obtained for the standard benchmark for the precision and recall, obtaining the fmeasure and fallout is trivial.

To avoid the need for human expert intervention, there are three research lines now; one for evaluating the results of an alignment tool and maybe feedback the process [START_REF] Gal | A framework for modeling and evaluating automatic semantic reconciliation[END_REF] [START_REF] Lambrix | A Tool for Evaluating Ontology Alignment Strategies[END_REF], another that tries to select automatically the algorithms according to their metadata [START_REF] Mochol | A High-Level Architecture of a Metadata-based Ontology Matching Framework[END_REF] and another called Ontology Meta-Matching [START_REF] Euzenat | Ontology Matching[END_REF] that tries to optimize automatically the parameters related to the matching task. So, our approach could be considered a mechanism for Meta-Matching. Most outstanding examples for this paradigm are: (i) Based on Exhaustive search solutions, (ii) Based on Neural Networks solutions, and (iii) Based on Genetic Algorithms solutions:

Based on Exhaustive Search Solutions

Ontology Meta-Matching can be solved trivially by an exhaustive search when the number of similarity measures is low, one of the most outstanding approaches in this sense is eTuner [START_REF] Lee | eTuner: tuning schema matching software using synthetic scenarios[END_REF]) that it is a system which, given a particular matching task, automatically tunes an ontology matching system (computing one-to-one alignments). For that purpose, it chooses the most effective basic matchers, and the best parameters to be used.

However, exhaustive searches are very expensive, and unworkable when combining a large number of measures from a computational point of view. For this reason, most solutions try to avoid this kind of methods.

Based on Machine Learning Solutions

Based on Machine Learning Meta-Matching techniques can be divided into two subtypes: Relevance feedback [START_REF] Salton | Improving retrieval performance by relevance feedback[END_REF] and Neural Networks [START_REF] Jordan | Neural Networks[END_REF]:

-The idea behind relevance feedback [START_REF] Salton | Improving retrieval performance by relevance feedback[END_REF]) is to take the results that are initially returned from a given query and to use information about whether or not those results are relevant to perform a new query: APFEL (Alignment Process Feature Estimation and Learning) (Ehrig et al, 2005) is a machine learning approach that explores user validation of initial alignments for optimizing automatically the configuration parameters of some of the matching strategies of the system, e.g., weights, thresholds, for the given matching task. -Neural Networks [START_REF] Jordan | Neural Networks[END_REF] are non-linear statistical data modeling or decision making tools. They can be used to model complex relationships between inputs and outputs or to find patterns of data. SFS [START_REF] Huang | Ontology Matching Using an Artificial Neural Network to Learn Weights[END_REF]) is a tool for ontology Meta-Matching that tries to obtain automatically a vector of weights for different semantic aspects of a matching task, such as comparison of concept names, comparison of concept properties, and comparison of concept relationships. To do so, it uses the neural networks technique.

However, these kinds of solutions involve spending much effort and time on training the systems in relation to our two proposals.

Based on Genetic Algorithms Solutions

In relation to solutions based on Genetic Algorithm approaches, the most outstanding tool is Genetic Algorithms Based Ontology Matching (GAOM) [START_REF] Wang | GAOM: Genetic Algorithm based Ontology Matching[END_REF] which is a genetic algorithm based approach for solving the ontology matching problem. For the purposes of better and more precise representation of ontology features, it defines the features from two points of view: intensional and extensional. On the other hand, the ontology matching problem is modeled as a global optimization of a mapping between two ontologies. Then a genetic algorithm is used to achieve an approximate optimal solution.

Table 4 shows a comparison of the results for both GAOM and our proposal.

Although we follow the same paradigm, it can be observed that GOAL shows Table 4. Comparison between GAOM and our proposal slightly better results. We think that the main differences in relation to the other tool is that they do not use basic and widely tested matching solutions but their own algorithms and the fitness function that we use, because we do not force to the algorithm to find always a global solution, this fact makes worse the results. Therefore, as far as we know, our results constitute the new state of the art when solving meta-matching schemes using GAs.

Conclusions

We have presented Ontology Meta-Matching, a novel computational discipline for flexible and accurate automatic ontology matching that generalizes and extends previous proposals for exploiting simple ontology matchers. We have presented the main techniques for ontology Meta-Matching. These techniques take into account that it is not trivial to determine what the weights of the semantic aspects should be and tries to avoid the research work which depends heavily on human heuristics. We have provided an analysis of the most popular algorithms and techniques for simple matching, and characterized their relative applicability as black boxes in a Meta-Matching environment. It is necessary to bear in mind that the success of the Meta-Matching depends largely on the kind of the underlying simples matchers used and the heterogeneity and soundness of the benchmarks for estimating, optimizing or learning the parameters.

We have designed and implemented two approaches to solve the Ontology Meta-Matching problem. Firstly, we have presented a greedy approach that is reasonably efficient, because is fast and reasonably accurate. Secondly, we have presented an approach based on Genetic Algorithms that is able to obtain more accurate results and is highly scalable, thus, it can be expanded with a lot of simple matching algorithms.

We have compared our two approaches with the most promising techniques and tools in the area of Ontology Meta-Matching. Like techniques, tools can be classified as either heuristic or learning-based. Such tools represent a serious effort to make the task of ontology matching a more independent process from users, context, and even data involved. The results shows that our approach is in line with the best available tools and is able to overcome their limitations in some specific cases.

The lessons learned on Ontology Meta-Matching will allow us to work with other kinds of conceptual schemas for modeling knowledge. In this sense, we are convinced that Ontology Meta-Matching is a perfect candidate for taking users a step further in the state-of-the-art in terms of interoperability in the Semantic Web.

Acknowledgments

We wish to thank to all anonymous reviewers for their comments and suggestions which have helped to improve this work. We thank Enrique Alba for his comments in relation to the approach based on Genetic Algorithms. This work has been funded by the Spanish Ministry of Innovation and Science through the project: ICARIA: A basic infrastructure for development in the Semantic Web and its application to conceptual mediation in bioinformatics. TIN2008-04844 and Pilot Project for Training and Developing Technologies for Applied Systems Biology, P07-TIC-02978 (From the Regional Government of Andalucia).

Fig. 1 .

 1 Fig. 1. Example of an user-dependent alignment. Most probably none of the two ontology owners will consider it optimal for them

Table 1 .

 1 In Table1, we explain briefly each of the test we are going to use to measure Brief explanation of the performed tests

		=	{relevant mappings} ∩ {retrieved mappings} {relevant mappings}
	Recall =	{relevant mappings} ∩ {retrieved mappings} {retrieved mappings}
	f measure =	2 × precision × recall precision + recall
	f allout =	{non relevant mappings} ∩ {retr. mappings} {non relevant mappings}

Although learning techniques exist such as Bayes learning, WHIRL learning, decision trees or stacked generalization, there are no Meta-Matching proposals using them as yet

http://www.ontologymatching.org

Author Biographies

Jorge Martinez-Gil is currently Junior Researcher in the Department of Languages of Computing Sciences at the University of Malaga (Spain). He obtained his Bachelors and Master degree in Computer Science in the University of Extremadura at Caceres (Spain), and his MPhil in Software Engineering and Artificial Intelligence in the University of Malaga. His main research interests are related with the interoperability in the Semantic Web. In fact, his PhD thesis deals with the search for finding more flexible ways to match ontologies and other kinds of models to represent knowledge. Mr Martinez-Gil has published several papers in conferences and journals. He is a volunteer reviewer in some international journals related to his research field, and has been an invited researcher in some leading research groups.

José F. Aldana-Montes is currently professor in the Department of Languages of Computing Sciences at the Higher Computing School from the University of Malaga (Spain) and Head of Khaos Research, a group for researching about semantic aspects of databases. Dr Aldana-Montes has more than 20 years of experience in research about several aspects of databases, semistructured data and semantic technologies and its application to such fields as bioinformatics or tourism. He is author of several relevant papers in top bioinformatic journals and conferences. Related to teaching, he has been teaching theoretical and practical aspects of databases at all possible university levels: from undergraduate courses to PhD.

Correspondence and offprint requests to: José F. Aldana-Montes, Department of Languages and Computing Sciences, Boulevard Luis Pasteur s/n 29071 Málaga (Spain). Email: jfam@lcc.uma.es