Paper Info
Title
Answering graph pattern queries using views
Abstract
Answering queries using views has proven an effective technique for querying relational and semistructured data. This paper investigates this issue for graph pattern queries based on (bounded) simulation, which have been increasingly used in, e.g., social network analysis. We propose a notion of pattern containment to characterize graph pattern matching using graph pattern views. We show that a graph pattern query can be answered using a set of views if and only if the query is contained in the views. Based on this characterization we develop efficient algorithms to answer graph pattern queries. In addition, we identify three problems associated with graph pattern containment. We show that these problems range from quadratic-time to NP-complete, and provide efficient algorithms for containment checking (approximation when the problem is intractable). Using real-life data and synthetic data, we experimentally verify that these methods are able to efficiently answer graph pattern queries on large social graphs, by using views.
Year
DOI
Venue
2014
10.1109/ICDE.2014.6816650
ICDE
DocType
ISSN
Citations 
Conference
1084-4627
6
PageRank 
References 
Authors
0.42
0
3
Name
Order
Citations
PageRank
Wenfei Fan14154197.29
xin wang21857.35
Yinghui Wu382442.79