Graph reachability queries: A unified multi-metric framework with dynamic evaluation and practical guidelines
Abstract
Reachability queries are a fundamental operation in large graph analysis, with applications in domains such as social networks, finance, program analysis, and XML query processing. Although many reachability indexes have been proposed, existing empirical studies remain limited in benchmark diversity, evaluation dimensions, and practical deployment guidance. In this work, we present a comprehensive empirical study of representative reachability indexes across diverse graph structures, query workloads, and both static and dynamic settings. We construct a large-scale benchmark covering 1,400 graphs and more than 38,000 query configurations, significantly broadening the structural and workload coverage of prior evaluations. To enable a more practical comparison, we introduce a unified multi-metric evaluation framework with complementary metrics that jointly consider query time, index size, construction cost, and dynamic update behaviour, thereby capturing a richer range of space–time trade-offs than previous studies. Our experiments reveal how graph structure, workload characteristics, and system constraints influence the relative advantages of different methods. Based on these findings, we further develop a decision-tree-based analysis to uncover feature-driven method preferences and derive practical guidelines for index selection under different deployment scenarios.