Structure preserving semantic matching

The most common matching applications, e.g., ontology matching, focus on the computation of the correspondences holding between the nodes of graph structures (e.g., concepts in two ontologies). However there are applications, such as matching of web service descriptions, where matching may need to compute the correspondences holding among the full graph structures and preserve certain structural properties of the graphs being considered. The goal of this paper is to provide an implementation of a new matching operator, that we call structure preserving match. This operator takes two graph-like structures and produces a mapping between those nodes of the structures that correspond semantically to each other, (i) still preserving a set of structural properties of the graphs being matched, (ii) only in the case if the graphs globally correspond semantically to each other. We present an exact and an approximate structure matching algorithms. The latter is based on a formal theory of abstraction and builds upon the well known tree edit distance measures. We have implemented the algorithms and applied them to the web service matchmaking scenario. The evaluation results, though preliminary, show the efficiency and effectiveness of our approach.