Adaptive Query Extension Suggestions for Ontology-Based Visual Query Systems

• Main Author: Klungre, Vidar Norstein
• Format: Dissertation
• Language: English

Ontology-based visual query systems enable users to construct ad-hoc queries in a way that is intuitive, and which allows them to receive feedback directly from the system interface. In this query construction setting, dead-ends are the undesirable query extensions leading to queries without any answers. Dead-end detection is then the problem of detecting and possibly disabling such extensions. The standard approach used to detect dead-ends, which requires querying over the data, is often too inefficient. This can be solved by using efficient indices, but current solutions only work when the user queries are limited to one single class and a fixed number of properties. We consider systems where the user is allowed to make more complex queries with two or more connected classes, but it is impossible to ensure both perfect and efficient dead-end detection in this setting because it would require an index of infinite size. This thesis introduces an index-based framework that can be used to efficiently approximate dead-end detection in systems that support ad-hoc, complex queries. In order to use this framework, it is necessary to provide a configuration structure where the classes and properties to support are given. This configuration determines both which parts of the data to include in the index, and how precise the dead-end detection approximation will be. Finding the configuration that leads to the highest possible precision while keeping the cost (index size) at an acceptable level is a non-trivial combinatorial optimization problem. The search space of possible configurations is too extensive for exhaustive search, and finding the true cost and precision of a configuration is time-consuming. We propose a solution to this problem where efficient cost and precision estimates are used to guide the search for the optimal configuration. Our evaluation of this search, which uses an extensive benchmark based on Wikidata, shows that it is able to efficiently compute non-trivial configurations with both high precision and an acceptable cost.