H.: Scalable instance retrieval for the semantic web by approximation

Abstract. Approximation has been identified as a potential way of re-ducing the complexity of logical reasoning. Here we explore approxi-mation for speeding up instance retrieval in a Semantic Web context. For OWL ontologies, i.e., Description Logic (DL) Knowledge Bases, it is known that reasoning is a hard problem. Especially in instance retrieval when the number of instances that need to be retrieved becomes very large. We discuss two approximation methods for retrieving instances to conjunctive queries over DL T-Boxes and the results of experiments carried out with a modified version of the Instance Store System.