← Publications
conference2025ICORE 2026 BCORE 2023 BCCF C

A Survey on Efficient Graph Reachability Queries

Huangleshuai He, Zhengyi Yang*, Dong Wen, Wenqian Zhang, Michael Yu, Wenke Yang, Wenjie Zhang

Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)

RAIDS Lab Authors

Zhengyi Yang
Zhengyi Yang
(corresponding author)
Director

Details

Year
2025
Venue
Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)
Publisher
Springer
Rankings
ICORE 2026 B · CORE 2023 B · CCF C

Research Area

Scalable Data Systems

Tags

GraphReachabilitySurvey

Resources

DOI ↗

Abstract

Graph reachability queries, which determine whether a path exists between two vertices in a graph, are a foundational problem in graph analytics. This survey provides a comprehensive review of techniques for efficient graph reachability querying, including static and dynamic approaches, indexed and online methods, and recent advancements. Detailed discussions explore various design choices for efficiently handling graph reachability queries, emphasising their applicability, limitations, and performance trade-offs. Additionally, we outline key open challenges and potential future directions to advance this field. This survey aims to guide researchers in navigating and advancing the state-of-the-art in graph reachability queries.

Author Affiliations

Huangleshuai He
University of New South Wales
Zhengyi Yang
University of New South Wales
Dong Wen
University of New South Wales
Wenqian Zhang
University of New South Wales
Michael Yu
University of Hong Kong
Wenke Yang
University of New South Wales
Wenjie Zhang
University of New South Wales

BibTeX

@inproceedings{he2025survey,
  title = {A Survey on Efficient Graph Reachability Queries},
  author = {He, Huangleshuai and Yang, Zhengyi and Wen, Dong and Zhang, Wenqian and Yu, Michael and Yang, Wenke and Zhang, Wenjie},
  editor = {Wu, Xintao and Spiliopoulou, Myra and Wang, Can and Kumar, Vipin and Cao, Longbing and Zhou, Xiangmin and Pang, Guansong and Gama, Joao},
  booktitle = {Data Science: Foundations and Applications},
  year = {2025},
  publisher = {Springer Nature Singapore},
  address = {Singapore},
  pages = {58--77},
  isbn = {978-981-96-8295-9}
}