Scaling Hop-Based Reachability Indexing for Fast Graph Pattern Query Processing

Ronghua Liang, Xiaorui Jiang, Hai Zhuge, Qiang Zeng, Xiaofei He

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


Graphs are becoming increasingly dominant in modeling real-life networked data including social and biological networks, the WWW and the Semantic Web, etc. Graph pattern queries are useful for gathering information with expressive semantics from these graph-structured data. Current methods for graph pattern query processing have performance deficiency caused by inefficiencies of the underlying reachability index and costly merge-join operations on huge amounts of tuple-formatted intermediate results. To overcome the above problems, this paper contributes in the following aspects to boost graph pattern query evaluation. First, we propose an improved hop-based reachability indexing scheme 3-Hop which gains faster reachability query evaluation, less indexing costs and better scalabilities than state-of-the-art hop-based methods. Second, we propose a two-stage node filtering algorithm based on 3-Hop to answer tree pattern queries more efficiently. Tree pattern queries serve as the underlying facility for graph pattern query evaluation. Furthermore, we use a graph representation of the intermediate results during node filtering and final results enumeration. Experiments on real-life and synthetic datasets demonstrate the effectiveness of the proposed methods.
Original languageEnglish
Pages (from-to)2803-2817
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number11
Early online date11 Mar 2014
Publication statusPublished - Nov 2014
Externally publishedYes


  • Graph pattern query processing
  • two-stage node filtering
  • reachability indexing
  • 3-Hop* labeling


Dive into the research topics of 'Scaling Hop-Based Reachability Indexing for Fast Graph Pattern Query Processing'. Together they form a unique fingerprint.

Cite this