2015 GraphQueryReformulationwithDive

• (Mottin et al., 2015) ⇒ Davide Mottin, Francesco Bonchi, and Francesco Gullo. (2015). “Graph Query Reformulation with Diversity.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783343

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Graph+Query+Reformulation+with+Diversity
• http://dl.acm.org/citation.cfm?id=2783258.2783343&preflayout=flat#citedby

Quotes

Author Keywords

• Graph databases; graph queries; query reformulation; [[selection process

Abstract

We study a problem of graph-query reformulation enabling explorative query-driven discovery in graph databases. Given a query issued by the user, the system, apart from returning the result patterns, also proposes a number of specializations (i.e., supergraphs) of the original query to facilitate the exploration of the results.

We formalize the problem of finding a set of reformulations of the input query by maximizing a linear combination of coverage (of the original query's answer set) and diversity among the specializations. We prove that our problem is hard, but also that a simple greedy algorithm achieves a (1/2) - approximation guarantee.

The most challenging step of the greedy algorithm is the computation of the specialization that brings the maximum increment to the objective function. To efficiently solve this step, we show how to compute the objective-function increment of a specialization linearly in the number of its results and derive an upper bound that we exploit to devise an efficient search-space visiting strategy.

An extensive evaluation on real and synthetic databases attests high efficiency and accuracy of our proposal.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 GraphQueryReformulationwithDive	Francesco Bonchi Francesco Gullo Davide Mottin			Graph Query Reformulation with Diversity				10.1145/2783258.2783343		2015