Edinburgh Research Explorer

Making Pattern Queries Bounded in Big Graphs

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

Related Edinburgh Organisations

Open Access permissions



Original languageEnglish
Title of host publication2015 IEEE 31st International Conference on Data Engineering
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Electronic)978-1-4799-7964-6
Publication statusPublished - 1 Jun 2015
Event31st International Conference on Data Engineering - Seoul, Korea, Republic of
Duration: 13 Apr 201517 Apr 2015

Publication series

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


Conference31st International Conference on Data Engineering
Abbreviated titleICDE 2015
CountryKorea, Republic of


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.

    Research areas

  • 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


31st International Conference on Data Engineering


Seoul, Korea, Republic of

Event: Conference

Download statistics

No data available

ID: 19939327