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

Open

Documents

Original languageEnglish
Title of host publicationData Engineering (ICDE), 2015 IEEE 31st International Conference on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages161-172
Number of pages12
DOIs
Publication statusPublished - 1 Apr 2015

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.

    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

Download statistics

No data available

ID: 19939327