EUVIMEDEUVIMED entdecken
LeitlinieOpen Access · CC BY 4.0

Graph reachability queries: A unified multi-metric framework with dynamic evaluation and practical guidelines

Huangleshuai He, Zhengyi Yang, Dong Wen, Wenke Yang, Wenjie Zhang

World Wide Web · 2026-11 · 29 (6)

DOI: 10.1007/s11280-026-01440-9 ↗

Kurz gefasst

Leitlinie in der Zeitschrift World Wide Web, online erschienen am 09.11.2026. Verfasst von Huangleshuai He und 4 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: University of New South Wales.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • University of New South Wales

Zitieren

APA

He, H., Yang, Z., Wen, D., Yang, W., & Zhang, W. (2026). Graph reachability queries: A unified multi-metric framework with dynamic evaluation and practical guidelines. World Wide Web, 29(6). https://doi.org/10.1007/s11280-026-01440-9

Vancouver

He H, Yang Z, Wen D, Yang W, Zhang W. Graph reachability queries: A unified multi-metric framework with dynamic evaluation and practical guidelines. World Wide Web. 2026;29(6). doi:10.1007/s11280-026-01440-9

BibTeX
@article{He2026,
  author = {He, Huangleshuai and Yang, Zhengyi and Wen, Dong and Yang, Wenke and Zhang, Wenjie},
  title = {Graph reachability queries: A unified multi-metric framework with dynamic evaluation and practical guidelines},
  journal = {World Wide Web},
  year = {2026},
  volume = {29},
  number = {6},
  doi = {10.1007/s11280-026-01440-9}
}
Kostenlos starten →