Hop-Constrained s-t Simple Path Enumeration in Billion-Scale Labelled Graphs

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Hop-constrained s-t simple path (HC-s-tpath) enumeration is a fundamental problem in graph analysis. Existing solutions for this problem focus on unlabelled graphs and assume queries are issued without any label constraints. However, in many real-world applications, graphs are edge-labelled and the queries involve label constraints on the path connecting two vertices. Therefore, we study the problem of labelled hop-constrained s-t path (LHC-s-tpath) enumeration in this paper. We aim to efficiently enumerate the HC-s-tpaths using only edges with provided labels. To achieve this goal, we first demonstrate the existence of unnecessary computation specific to the label constraints in the state-of-the-art HC-s-tpath enumeration algorithm. We then devise a novel online index to identify the fruitless exploration during the enumeration. Based on the proposed index, we design an efficient LHC-s-tpath enumeration algorithm in which unnecessary computation is effectively pruned. Extensive experiments are conducted on real-world graphs with billions of edges. Experiment results show that our proposed algorithms significantly outperform the baseline methods by over one order of magnitude.

Author Affiliations

@inproceedings{li2022hop,
  title = {Hop-Constrained s-t Simple Path Enumeration in Billion-Scale Labelled Graphs},
  author = {Li, Xia and Hao, Kongzhang and Yang, Zhengyi and Cao, Xin and Zhang, Wenjie and Yuan, Long and Lin, Xuemin},
  editor = {Chbeir, Richard and Huang, Helen and Silvestri, Fabrizio and Manolopoulos, Yannis and Zhang, Yanchun},
  booktitle = {Web Information Systems Engineering -- WISE 2022},
  year = {2022},
  publisher = {Springer International Publishing},
  address = {Cham},
  pages = {49--64},
  isbn = {978-3-031-20891-1}
}