Poster – Paper 646

Predicting the Cost of Online Reasoning on Knowledge Graphs: Some Heuristics Varsha Ravichandra Mouli, Unmesh Joshi, Ceriel Jacobs and Jacopo Urbani Poster October 23, 2017, Poster and Demo Reception, 18:30-21:20 Festsaal 1 Download paper (preprint)

Abstract

We study the problem of efficiently performing online reasoning, i.e.,computing all relevant implicit answers during query answering. We focus on reasoning that can be encoded with Datalog programs.Working with implementation of two query-driven Datalog evaluations: Query-Subquery (QSQ), a top-down procedure, and Magic-Set(MS),which proceeds bottom-up, one is preferable to the other depending on the amount of reasoning triggered by the query. Thus, to achieve the highest efficiency, we study how we can estimate whether a given query will be faster with QSQ or MS. We propose a number of heuristics for making such an estimate and evaluate them. Our experiments, conducted on various KGs and using the VLog engine, showed that individual estimators were able to choose the right algorithm in most of the cases. This increases significantly the efficiency of reasoning at query-time.