Making Pattern Queries Bounded in Big Graphs

Yang Cao, Wenfei Fan, Jinpeng Huai, Ruizhe Huang

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

Abstract

It is cost-prohibitive to find matches Q(G) of a pattern query Q in a big graph G. We approach this by fetching a small subgraph GQ of G such that Q(GQ) = Q(G). We show that many practical patterns are effectively bounded under access constraints A commonly found in real life, such that GQ can be identified in time determined by Q and A only, independent of the size |G| of G. This holds no matter whether pattern queries are localized (e.g., via subgraph isomorphism) or non-localized (graph simulation). We provide algorithms to decide whether a pattern Q is effectively bounded, and if so, to generate a query plan that computes Q(G) by accessing GQ, in time independent of |G|. When Q is not effectively bounded, we give an algorithm to extend access constraints and make Q bounded in G. Using real-life data, we experimentally verify the effectiveness of the approach, e.g., about 60% of queries are effectively bounded for subgraph isomorphism, and for such queries our approach outperforms the conventional methods by 4 orders of magnitude.
Original languageEnglish
Title of host publication2015 IEEE 31st International Conference on Data Engineering
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages161-172
Number of pages12
ISBN (Electronic)978-1-4799-7964-6
DOIs
Publication statusPublished - 1 Jun 2015
Event31st International Conference on Data Engineering - Seoul, Korea, Republic of
Duration: 13 Apr 201517 Apr 2015

Publication series

Name
PublisherIEEE
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X

Conference

Conference31st International Conference on Data Engineering
Abbreviated titleICDE 2015
CountryKorea, Republic of
CitySeoul
Period13/04/1517/04/15

Keywords

  • graph theory
  • query processing
  • access constraints
  • big graph
  • pattern queries
  • query plan generation
  • subgraph isomorphism
  • Adaptation models
  • Approximation algorithms
  • Awards activities
  • Computational modeling
  • Indexes
  • Motion pictures
  • Pattern matching

Fingerprint Dive into the research topics of 'Making Pattern Queries Bounded in Big Graphs'. Together they form a unique fingerprint.

Cite this