Algorithms for Measuring Similarity Between ELH Concept Descriptions: A Case Study on Snomed ct

Abstract

In Description Logics, subsumption is regarded as one of the most prominent reasoning services. It checks, relative to the logical definitions in the ontology, whether one concept is more general/specific than another. When no subsumption relationship is identified, however, no information about the two concepts can be given. In several realistic Semantic Web applications, knowing the level of similarity between two concepts, though lacking the subsumption relationship, is beneficial. This work introduces a new method for measuring the degree of similarity between two concept descriptions in the DL ELH, despite not being in a subsumption relation. Two algorithms are devised based on the known homomorphism-based structural subsumption characterization. The first algorithm employs the top-down approach, whereas the second is carried out in the reverse direction. A bottom-up algorithm has better efficiency, making it more suitable to large-scale ontologies developed using an inexpressive DL in the EL family, such as the renowned medical ontology Snomed ct. The computational performance of the proposed measure is intensively studied, and interesting findings in Snomed ct are reported.