How Long Will It Take? Accurate Prediction of Ontology Reasoning Performance

For expressive ontology languages such as OWL 2 DL, classification is a computationally expensive task— 2NEXPTIME-complete in the worst case. Hence, it is highly desirable to be able to accurately estimate classi-fication time, especially for large and complex ontolo-gies. Recently, machine learning techniques have been successfully applied to predicting the reasoning hard-ness category for a given (ontology, reasoner) pair. In this paper, we further develop predictive models to es-timate actual classification time using regression tech-niques, with ontology metrics as features. Our large-scale experiments on 6 state-of-the-art OWL 2 DL rea-soners and more than 450 significantly diverse ontolo-gies demonstrate that the prediction models achieve high accuracy, good generalizability and statistical sig-nificance. Such prediction models have a wide range of applications. We demonstrate how they can be used to efficiently and accurately identify performance hotspots in a large and complex ontology, an otherwise very time-consuming and resource-intensive task.