Answering graph pattern queries using views

Wenfei Fan, Xin Wang, Yinghui Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationIEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
Publication statusPublished - 2014


Dive into the research topics of 'Answering graph pattern queries using views'. Together they form a unique fingerprint.

Cite this