Approximating Graph Pattern Queries Using Views

Jia Li, Yang Cao, Xudong Liu

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

Abstract

This paper studies approximation of graph pattern queries using views. Given a pattern query Q and a set V of views, we propose to find a pair of queries Qu and Ql, referred to as the upper and lower approximations of Q w.r.t. V, such that (a) for any data graph G, answers to (part of) Q in G are contained in Qu(G) and contain Ql(G); and (b) both Qu and Ql can be answered by using views in V. We consider pattern queries based on both graph simulation and subgraph isomorphism. We study fundamental problems about approximation using views. Given Q and V, (1) we study whether there exist upper and lower approximations of Q w.r.t. V. (2) How to find approximations that are closest to Q w.r.t. V if exist? (3) How to answer upper and lower approximations using views in V? We give characterizations of the problems, study their complexity and approximation-hardness, and develop algorithms with provable bounds. Using real-life datasets, we verify the effectiveness and efficiency of approximating simulation and subgraph queries using views.
Original languageEnglish
Title of host publicationProceedings of the 25th ACM International on Conference on Information and Knowledge Management
Place of PublicationNew York, NY, USA
PublisherACM
Pages449-458
Number of pages10
ISBN (Print)978-1-4503-4073-1
DOIs
Publication statusPublished - 24 Oct 2016
Event25th ACM International on Conference on Information and Knowledge Management - Indianapolis, United States
Duration: 24 Oct 201628 Oct 2016
https://www.cikm2016.org/

Publication series

NameCIKM '16
PublisherACM

Conference

Conference25th ACM International on Conference on Information and Knowledge Management
Abbreviated titleCIKM 2016
CountryUnited States
CityIndianapolis
Period24/10/1628/10/16
Internet address

Fingerprint Dive into the research topics of 'Approximating Graph Pattern Queries Using Views'. Together they form a unique fingerprint.

Cite this