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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Survey on Efficient Graph Reachability Queries

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

摘要

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.