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

Formal Metadata

Title
Answering Why-questions by Exemplars in Attributed Graphs
Title of Series
Number of Parts
155
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
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.