We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Answering Why-questions by Exemplars in Attributed Graphs

Formale Metadaten

Titel
Answering Why-questions by Exemplars in Attributed Graphs
Serientitel
Anzahl der Teile
155
Autor
Lizenz
CC-Namensnennung 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr2019
SpracheEnglisch

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
This paper studies the problem of answering Why-questions for graph pattern queries. Given a query Q, its answers Q(G) in a graph G, and an exemplar E that describes desired answers, it aims to compute a query rewrite Q', such that Q'(G) incorporates relevant entities and excludes irrelevant ones wrt E under a closeness measure. (1) We characterize the problem by Q-Chase. It rewrites Q by applying a sequence of applicable operators guided by E, and backtracks to derive optimal query rewrite. (2) We develop feasible Q-Chase-based algorithms, from anytime solutions to fixed-parameter approximations to compute query rewrites. These algorithms implement Q-Chase by detecting picky operators at run time, which discriminately enforce E to retain answers that are closer to exemplars, and effectively prune both operators and irrelevant matches, by consulting a cache of star patterns (called star views). Using real-world graphs, we experimentally verify the efficiency and effectiveness of qchase techniques and their applications.