Distributed Hop-constrained s-t Simple Path Enumeration in Labelled Graphs

RAIDS Lab Authors

Zhengyi Yang

Director

Details

Research Area

Tags

Resources

Abstract

Hop-constrained s-t simple path (HC-s-t path) enumeration is a core problem in graph analysis, commonly applied to unlabelled graphs without considering label constraints. However, in many practical scenarios, graphs are edge-labelled, requiring queries to satisfy specific label constraints on the paths between vertices. This introduces new computational challenges that traditional HC-s-t path algorithms are not equipped to handle, especially in distributed environments dealing with large-scale graphs. To address these challenges, we propose a distributed algorithm for labelled hop-constrained s-t path (LHC-s-t path) enumeration. Our approach introduces an online label-based index to prune unnecessary computations, reducing both redundant processing and communication overhead. This enables efficient LHC-s-t path enumeration across distributed systems. Extensive experiments on large real-world graphs demonstrate that our algorithm significantly outperforms existing methods, achieving over an order of magnitude improvement in performance and scalability.

Author Affiliations

@inproceedings{li2024distributed,
  title = {Distributed Hop-Constrained s-t Simple Path Enumeration in Labelled Graphs},
  author = {Li, Xia and Yang, Zhengyi and Hao, Kongzhang and Shu, Xin and Cao, Xin and Zhang, Wenjie},
  editor = {Chen, Tong and Cao, Yang and Nguyen, Quoc Viet Hung and Nguyen, Thanh Tam},
  booktitle = {Databases Theory and Applications},
  year = {2025},
  publisher = {Springer Nature Singapore},
  address = {Singapore},
  pages = {265--278},
  isbn = {978-981-96-1242-0}
}