EUVIMEDEUVIMED entdecken
Crossref

Indexing Techniques for Graph Reachability Queries

Chao Zhang, Angela Bonifati, M. Tamer Özsu

ACM Computing Surveys · 30.04.2026 · 58 (6) · 1-35

DOI: 10.1145/3776737 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Computing Surveys, online erschienen am 08.12.2025. Verfasst von Chao Zhang und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 118 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We survey graph reachability indexing techniques for efficiently processing reachability queries in two popular graph models: plain graphs and edge-labeled graphs . Reachability queries determine whether a directed path exists between a source and a target vertex, forming a core class of navigational queries in graph analytics. Reachability indexes are specialized data structures that accelerate such query processing. Work on this topic goes back four decades—we include 33 of the proposed techniques. Plain graphs consist of only vertices and edges, with reachability queries checking for the existence of a path. Edge-labeled graphs extend plain graphs by adding labels to edges, and their queries further impose constraints on the labels along the path. We categorize indexing techniques for both plain and edge-labeled graphs and discuss them based on this classification, using representative methods to illustrate key ideas. We discuss the main challenges within each category and how these might be addressed in other approaches. We conclude with a discussion of the open challenges and future research directions, along the lines of integrating reachability indexes into modern graph database management systems. This survey serves as a comprehensive resource for researchers and practitioners interested in the advancements, techniques, and challenges of reachability indexing in graph analytics.

Zitieren

APA

Zhang, C., Bonifati, A., & Özsu, M. T. (2026). Indexing Techniques for Graph Reachability Queries. ACM Computing Surveys, 58(6), 1-35. https://doi.org/10.1145/3776737

Vancouver

Zhang C, Bonifati A, Özsu MT. Indexing Techniques for Graph Reachability Queries. ACM Computing Surveys. 2026;58(6):1-35. doi:10.1145/3776737

BibTeX
@article{Zhang2026,
  author = {Zhang, Chao and Bonifati, Angela and Özsu, M. Tamer},
  title = {Indexing Techniques for Graph Reachability Queries},
  journal = {ACM Computing Surveys},
  year = {2026},
  volume = {58},
  number = {6},
  pages = {1--35},
  doi = {10.1145/3776737}
}
Kostenlos starten →