Abstract
Modern knowledge representation relies heavily on ontologies, yet these systems often suffer from "bloated" concept definitions that are redundant and difficult to maintain. This paper introduces a novel algorithm that computes the absolute smallest equivalent concept in $\mathcal{EL}$ logic. By utilizing Regular Tree Grammars (RTGs) and dynamic derivation rules, the authors transform a theoretically NP-complete problem into a practical tool capable of optimizing massive medical ontologies like SNOMED CT and GALEN in seconds or minutes.
Introduction: The Problem of Structural Complexity
In Description Logics (DLs), the $\mathcal{EL}$ fragment is the standard for large-scale biomedical ontologies. However, because these ontologies are often developed collaboratively over decades or generated automatically, they frequently contain "wordy" definitions with redundant logical intersections and existential quantifications. For instance, a definition for "Clotting" might redundantly list physical states of blood already covered by more concise terms. This bloat hinders human readability, increases computational overhead for reasoners, and complicates maintenance. While finding the minimal equivalent concept is known to be NP-complete, this work provides the first practical solution for large-scale systems.
Methodology: Dynamic Regular Tree Grammars
The proposed minimization algorithm is built upon the framework of Regular Tree Grammars (RTGs), enhanced by several key optimizations:
- Subsumer Grammars: The search space is restricted to "subsumers"—concepts more general than the target. The authors prove that a minimal equivalent concept for $\mathcal{EL}$ always exists within this set.
- Dynamic Derivation Rules: Unlike traditional static rules, the algorithm updates its derivation rules "on-demand" based on the specific context and non-terminal being processed. This innovation reduces the number of applied rules by approximately eight orders of magnitude.
- Aggressive Pruning: The search is constrained by Size Monotonicity (discarding branches that exceed the current best candidate's size) and Subsumption Monotonicity (discarding concepts too general to be equivalent).
- Irreducible Sets: The algorithm identifies minimal sets of equivalence classes to ensure no redundant conjuncts are included in the final output.
Experimental Evaluation
The researchers evaluated the tool using 100 concepts from five major biomedical ontologies: SNOMED CT, GALEN, NCI Thesaurus (NCIT), FYPO, and Genomic CDS.
Key Results
- Efficiency: For most ontologies (NCIT, Galen, FYPO), minimal concepts were found in seconds. Even for the massive SNOMED CT (320k+ axioms), the tool averaged approximately 5 minutes per concept.
- Significant Redundancy: A notable proportion of concepts in every dataset were reducible. In GALEN, 100% of tested concepts with a size of 10 or more were found to have a smaller equivalent, with an average size reduction of 72%.
- Search Space Optimization: The dynamic rule approach was critical, reducing the number of considered subsets by five orders of magnitude compared to baseline methods.
Discussion and Future Work
The study demonstrates that the hierarchical structure of real-world ontologies allows for efficient optimization of NP-complete problems. However, the current methodology is limited to $\mathcal{EL}$ logic and does not yet support negation, universal quantification, or disjunction. Future research will focus on extending these techniques to more expressive Description Logics and exploring global ontology refactoring to improve usability for medical professionals.
Summary updated