Many applications require the establishment of mappings be-tween ontologies. Such mappings are established by domain experts or automated tools. Errors in mappings can introduce inconsistencies in the resulting combined ontology. We consider the problem of identify-ing the largest consistent subset of mappings in hierarchical ontologies. We consider mappings that assert that a concept in one ontology is a subconcept, superconcept, or equivalent concept of a concept in another ontology and show that even in this simple setting, the task of identifying the largest consistent subset is NP-hard. We explore several polynomial time algorithms for finding suboptimal solutions including a heuristic algorithm to this problem. We experimentally compare the algorithms using several synthetic as well as real-world ontologies and mappings.
展开▼
