Making Pattern Queries Bounded in Big Graphs

Yang Cao; Wenfei Fan; Jinpeng Huai; Ruizhe Huang

doi:10.1109/ICDE.2015.7113281

Making Pattern Queries Bounded in Big Graphs

Yang Cao, Wenfei Fan, Jinpeng Huai, Ruizhe Huang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

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 G_Q of G such that Q(G_Q) = Q(G). We show that many practical patterns are effectively bounded under access constraints A commonly found in real life, such that G_Q 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 G_Q, 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 language	English
Title of host publication	2015 IEEE 31st International Conference on Data Engineering
Publisher	Institute of Electrical and Electronics Engineers
Pages	161-172
Number of pages	12
ISBN (Electronic)	978-1-4799-7964-6
DOIs	https://doi.org/10.1109/ICDE.2015.7113281
Publication status	Published - 1 Jun 2015
Event	31st International Conference on Data Engineering - Seoul, Korea, Republic of Duration: 13 Apr 2015 → 17 Apr 2015

Publication series

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

Conference

Conference	31st International Conference on Data Engineering
Abbreviated title	ICDE 2015
Country/Territory	Korea, Republic of
City	Seoul
Period	13/04/15 → 17/04/15

Keywords / Materials (for Non-textual outputs)

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

Access to Document

10.1109/ICDE.2015.7113281Licence: All Rights Reserved

icde15Accepted author manuscript, 268 KB

https://ieeexplore.ieee.org/document/7113281Licence: All Rights Reserved

Querying Graph Structured Data: Principles and Techniques
Libkin, L. & Fan, W.
EPSRC
1/11/13 → 31/10/16
Project: Research

Yang Cao
- School of Informatics - Lecturer in Database Systems
- Laboratory for Foundations of Computer Science
- Foundations of Computation
Person: Academic: Research Active

Cite this

@inproceedings{f29775c09ea54640bfb3f7959ddf0c49,

title = "Making Pattern Queries Bounded in Big Graphs",

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.",

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",

author = "Yang Cao and Wenfei Fan and Jinpeng Huai and Ruizhe Huang",

year = "2015",

month = jun,

day = "1",

doi = "10.1109/ICDE.2015.7113281",

language = "English",

publisher = "Institute of Electrical and Electronics Engineers",

pages = "161--172",

booktitle = "2015 IEEE 31st International Conference on Data Engineering",

address = "United States",

note = "31st International Conference on Data Engineering, ICDE 2015 ; Conference date: 13-04-2015 Through 17-04-2015",

}

TY - GEN

T1 - Making Pattern Queries Bounded in Big Graphs

AU - Cao, Yang

AU - Fan, Wenfei

AU - Huai, Jinpeng

AU - Huang, Ruizhe

PY - 2015/6/1

Y1 - 2015/6/1

N2 - 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.

AB - 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.

KW - graph theory

KW - query processing

KW - access constraints

KW - big graph

KW - pattern queries

KW - query plan generation

KW - subgraph isomorphism

KW - Adaptation models

KW - Approximation algorithms

KW - Awards activities

KW - Computational modeling

KW - Indexes

KW - Motion pictures

KW - Pattern matching

U2 - 10.1109/ICDE.2015.7113281

DO - 10.1109/ICDE.2015.7113281

M3 - Conference contribution

SP - 161

EP - 172

BT - 2015 IEEE 31st International Conference on Data Engineering

PB - Institute of Electrical and Electronics Engineers

T2 - 31st International Conference on Data Engineering

Y2 - 13 April 2015 through 17 April 2015

ER -

Making Pattern Queries Bounded in Big Graphs

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Projects

Querying Graph Structured Data: Principles and Techniques

Profiles

Yang Cao

Cite this