A mapping-based tree similarity algorithm and its application to ontology alignment

A mapping-based tree similarity algorithm is proposed for matching concept trees in ontology alignment to integrate various information sources in the Semantic Web. Concepts regarding classes and properties are the most critical ontological elements and metadata. First, the similarity between the individual concepts of each type is defined. These concept systems, which are considered as the foundation of ontology, are described as tree modes for overall comparison. Based on the minimal cost of edit operations, previous tree similarity measuring approaches are extremely complicated because three or four edit operations are involved. Moreover, such approaches ignore the similarity among single nodes. In the proposed algorithm, node similarity, instead of changing operation, is adopted and the inserting and deleting operation is omitted. The proposed algorithm is more concise and effective because it satisfies the maximum mapping theorem without damaging tree isomorphism. The algorithm is resolved and realized by a dynamic programming scheme. Then, the algorithm is independently used to compare class and property trees, and their mapping concept sets are regarded as the main part of the ontology alignment. Demonstration examples are used to prove the effectiveness and feasibility of the algorithm in ontology alignment.