{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T15:33:28Z","timestamp":1765294408356,"version":"3.46.0"},"reference-count":118,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2026,4,30]]},"abstract":"<jats:p>\n                    We survey graph reachability indexing techniques for efficiently processing reachability queries in two popular graph models:\n                    <jats:italic toggle=\"yes\">plain graphs<\/jats:italic>\n                    and\n                    <jats:italic toggle=\"yes\">edge-labeled graphs<\/jats:italic>\n                    . 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\u2014we 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.\n                  <\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1145\/3776737","type":"journal-article","created":{"date-parts":[[2025,11,14]],"date-time":"2025-11-14T11:20:46Z","timestamp":1763119246000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Indexing Techniques for Graph Reachability Queries"],"prefix":"10.1145","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4972-9380","authenticated-orcid":false,"given":"Chao","family":"Zhang","sequence":"first","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo","place":["Waterloo, Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9582-869X","authenticated-orcid":false,"given":"Angela","family":"Bonifati","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lyon 1 University","place":["Lyon, France"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8126-1717","authenticated-orcid":false,"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo","place":["Waterloo, Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,12,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263676"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66950"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2012.31"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96193-4_1"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2389241.2389250"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465216"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2010.11.002"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3581784.3607068"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3604932"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3335409.3335411"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.2200\/S00873ED1V01Y201808DTM051"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.117"},{"key":"e_1_3_2_18_2","unstructured":"Horst Bunke. 2000. Graph matching: Theoritical foundations algorithms and applications. Proceedings of International Conference on Vision Interface Vision Interface. Montreal 82\u201388."},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871457"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1805"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/959060.959076"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551813"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083651"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529348"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3451159"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350247"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0346-6"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.14778\/3648160.3648179"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767858"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3282488"},{"key":"e_1_3_2_36_2","first-page":"25","volume-title":"Proceedings of the Conference on Innovative Data Systems Research","volume":"7","author":"Feng Xiyang","year":"2023","unstructured":"Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Saliho\u011flu. 2023. K\u00f9zu graph database management system. In Proceedings of the Conference on Innovative Data Systems Research, Vol. 7. 25\u201335."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-63962-8_212-1"},{"key":"e_1_3_2_38_2","first-page":"636","volume-title":"Proceedings of the 19th International Conference on Extending Database Technology","author":"Fletcher George H. L.","year":"2016","unstructured":"George H. L. Fletcher, Jeroen Peters, and Alexandra Poulovassilis. 2016. Efficient regular path query evaluation using path indexes. In Proceedings of the 19th International Conference on Extending Database Technology. 636\u2013639."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","unstructured":"L. R. Foulds. 1992. Digraphs. In Graph Theory Applications. Springer New York New York NY 93\u2013122. DOI:10.1007\/978-1-4612-0933-1_7","DOI":"10.1007\/978-1-4612-0933-1_7"},{"key":"e_1_3_2_40_2","first-page":"43","volume-title":"Proceedings of the AAAI Fall Symposium","author":"Gallagher Brian","year":"2006","unstructured":"Brian Gallagher. 2006. Matching structure and semantics: A survey on graph-based pattern matching. In Proceedings of the AAAI Fall Symposium. 43\u201353."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.14778\/3641204.3641214"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2484425.2484443"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476297"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3418294"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.53"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.9"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3556540"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492668"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99944"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510400"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807183"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3392717.3392745"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213856"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/1929934.1929941"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556578"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376677"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.3389\/fbioe.2020.00034"},{"key":"e_1_3_2_59_2","first-page":"582","volume-title":"Proceedings of the 24th International Conference on Extending Database Technology","author":"Kuijpers Jochem","year":"2021","unstructured":"Jochem Kuijpers, George Fletcher, Tobias Lindaaker, and Nikolay Yakovets. 2021. Path indexing in the cypher query pipeline. In Proceedings of the 24th International Conference on Extending Database Technology. 582\u2013587. Retrieved from https:\/\/openproceedings.org\/2021\/conf\/edbt\/p156.pdf"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274585"},{"key":"e_1_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10044-012-0284-8"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-73197-7_52"},{"key":"e_1_3_2_64_2","article-title":"White Paper: Neo4j for Financial Services","author":"Mathur Nav","year":"2021","unstructured":"Nav Mathur. 2021. White Paper: Neo4j for Financial Services. Retrieved June 20, 2025 from https:\/\/neo4j.com\/whitepapers\/financial-services-neo4j","journal-title":"https:\/\/neo4j.com\/whitepapers\/financial-services-neo4j"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_58"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453927"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389733"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00025"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380753"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.3390\/computation8040103"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_7"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.82"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007387"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00548-x"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434642"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.57"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00049"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","DOI":"10.1145\/3128571"},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_3_2_84_2","article-title":"SPARQL 1.1 Query Language","author":"Steve Harris","year":"2013","unstructured":"Harris Steve and Seaborne Andy. 2013. SPARQL 1.1 Query Language. Retrieved June 20, 2025 from https:\/\/www.w3.org\/TR\/2013\/REC-sparql11-overview-20130321\/","journal-title":"https:\/\/www.w3.org\/TR\/2013\/REC-sparql11-overview-20130321\/"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2631160"},{"key":"e_1_3_2_86_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-58943-5_43"},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809983"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_2_89_2","article-title":"openCypher","author":"Team The Neo4j","year":"2016","unstructured":"The Neo4j Team. 2016. openCypher. Retrieved June 20, 2025 from http:\/\/www.opencypher.org","journal-title":"http:\/\/www.opencypher.org"},{"key":"e_1_3_2_90_2","volume-title":"Proceedings of the 13th Biennial Conference on Innovative Data Systems Research","author":"Wolde Daniel ten","year":"2023","unstructured":"Daniel ten Wolde, Tavneet Singh, G\u00e1bor Sz\u00e1rnyas, and Peter A. Boncz. 2023. DuckPGQ: Efficient property graph queries in an analytical RDBMS. In Proceedings of the 13th Biennial Conference on Innovative Data Systems Research. Retrieved from https:\/\/www.cidrdb.org\/cidr2023\/papers\/p66-wolde.pdf"},{"key":"e_1_3_2_91_2","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_3_2_92_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035955"},{"key":"e_1_3_2_93_2","first-page":"511","volume-title":"Proceedings of the 17th International Conference on Extending Database Technology","author":"Veloso Ren\u00ea Rodrigues","year":"2014","unstructured":"Ren\u00ea Rodrigues Veloso, Lo\u00efc Cerf, Wagner Meira Jr., and Mohammed J. Zaki. 2014. Reachability queries in very large graphs: A fast refined online search approach. In Proceedings of the 17th International Conference on Extending Database Technology. 511\u2013522. Retrieved from https:\/\/openproceedings.org\/EDBT\/2014\/paper_166.pdf"},{"key":"e_1_3_2_94_2","doi-asserted-by":"publisher","DOI":"10.1145\/3589259"},{"key":"e_1_3_2_95_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00049"},{"key":"e_1_3_2_96_2","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732992"},{"key":"e_1_3_2_97_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0468-3"},{"key":"e_1_3_2_98_2","unstructured":"Mathias Weller. 2014. Optimal hub labeling is NP-complete. arxiv:1407.8373 [cs.CC]. Retrieved from https:\/\/arxiv.org\/abs\/1407.8373"},{"key":"e_1_3_2_99_2","doi-asserted-by":"publisher","DOI":"10.1145\/2206869.2206879"},{"key":"e_1_3_2_100_2","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063807"},{"key":"e_1_3_2_101_2","doi-asserted-by":"publisher","DOI":"10.1145\/2911996.2912035"},{"key":"e_1_3_2_102_2","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364329"},{"key":"e_1_3_2_103_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505724"},{"key":"e_1_3_2_104_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"},{"key":"e_1_3_2_105_2","unstructured":"Hilmi Yildirim Vineet Chaoji and Mohammed J. Zaki. 2013. DAGGER: A scalable index for reachability queries in large dynamic graphs. arxiv:1301.0977. Retrieved from https:\/\/arxiv.org\/abs\/1301.0977"},{"key":"e_1_3_2_106_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"e_1_3_2_107_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00172"},{"key":"e_1_3_2_108_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-00129-1_37"},{"key":"e_1_3_2_109_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00013"},{"key":"e_1_3_2_110_2","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589408"},{"key":"e_1_3_2_111_2","doi-asserted-by":"publisher","DOI":"10.14778\/3675034.3675040"},{"key":"e_1_3_2_112_2","unstructured":"Chao Zhang Angela Bonifati and M. Tamer \u00d6zsu. 2023. Indexing techniques for graph reachability queries. arxiv:2311.03542 [cs.DB]. Retrieved from https:\/\/arxiv.org\/abs\/2311.03542"},{"key":"e_1_3_2_113_2","unstructured":"Chao Zhang Angela Bonifati and Tamer \u00d6zsu. 2025. Low-Latency sliding window connectivity. arxiv:2410.00884 [cs.DB]. Retrieved from https:\/\/arxiv.org\/abs\/2410.00884"},{"key":"e_1_3_2_114_2","doi-asserted-by":"publisher","DOI":"10.1145\/3639260"},{"key":"e_1_3_2_115_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3108433"},{"key":"e_1_3_2_116_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035927"},{"key":"e_1_3_2_117_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612181"},{"key":"e_1_3_2_118_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.003"},{"key":"e_1_3_2_119_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-016-5554-y"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776737","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T15:21:14Z","timestamp":1765293674000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776737"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,8]]},"references-count":118,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2026,4,30]]}},"alternative-id":["10.1145\/3776737"],"URL":"https:\/\/doi.org\/10.1145\/3776737","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"type":"print","value":"0360-0300"},{"type":"electronic","value":"1557-7341"}],"subject":[],"published":{"date-parts":[[2025,12,8]]},"assertion":[{"value":"2023-11-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}