Anytime classification by ontology approximation

Reasoning with large or complex ontologies is one of the bottle-necks of the Semantic Web. In this paper we present an anytime algorithm for classification based on approximate subsumption. We give the formal definitions for approximate subsumption, and show its monotonicity and soundness; we show how it can be computed in terms of classical subsumption; and we study the computational behaviour of the algorithm on a set of realistic benchmarks. The most interesting finding is that anytime classification works best on ontologies where classical subsumption is hardest to compute.