{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T13:27:48Z","timestamp":1778765268810,"version":"3.51.4"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2022,10,21]],"date-time":"2022-10-21T00:00:00Z","timestamp":1666310400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council\u00a0(ERC) under the European Union\u2019s Seventh Framework Programme","award":["340506"],"award-info":[{"award-number":["340506"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            One of the most fundamental problems in computer science is the\n            <jats:italic>reachability problem<\/jats:italic>\n            : Given a directed graph and two vertices\n            <jats:italic>s<\/jats:italic>\n            and\n            <jats:italic>t<\/jats:italic>\n            , can\n            <jats:italic>s<\/jats:italic>\n            <jats:italic>reach<\/jats:italic>\n            <jats:italic>t<\/jats:italic>\n            via a path? We revisit existing techniques and combine them with new approaches to support a large portion of\n            <jats:italic>reachability queries<\/jats:italic>\n            in constant time using a linear-sized\n            <jats:italic>reachability index<\/jats:italic>\n            . Our new algorithm\n            <jats:monospace>O\u2019Reach<\/jats:monospace>\n            can be easily combined with previously developed solutions for the problem or run standalone.\n          <\/jats:p>\n          <jats:p>\n            In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph but also on the result, i.e.,\n            <jats:italic>reachable<\/jats:italic>\n            or\n            <jats:italic>unreachable<\/jats:italic>\n            . Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn\u2019t necessarily pay off:\n            <jats:italic>Reachability queries<\/jats:italic>\n            can often be answered even faster than single memory accesses in a precomputed full reachability matrix.\n          <\/jats:p>","DOI":"10.1145\/3556540","type":"journal-article","created":{"date-parts":[[2022,8,17]],"date-time":"2022-08-17T12:23:58Z","timestamp":1660739038000},"page":"1-27","source":"Crossref","is-referenced-by-count":6,"title":["O\u2019Reach: Even Faster Reachability in Large Graphs"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5945-837X","authenticated-orcid":false,"given":"Kathrin","family":"Hanauer","sequence":"first","affiliation":[{"name":"University of Vienna, Faculty of Computer Science, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2823-3506","authenticated-orcid":false,"given":"Christian","family":"Schulz","sequence":"additional","affiliation":[{"name":"Heidelberg University, Heidelberg, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1086-4756","authenticated-orcid":false,"given":"Jonathan","family":"Trummer","sequence":"additional","affiliation":[{"name":"University of Vienna, Faculty of Computer Science, Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,21]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6170-8_23"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_56"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_3_3_7_2","volume-title":"Introduction to Algorithms (3rd ed.)","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press, Chapter Elementary Data Structures."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00043"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1110.0401"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SEA.2020.14"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SEA.2021.13"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99944"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213856"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1929934.1929941"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556578"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376677"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/368996.369025"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_3_22_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved Feb 1 2021 from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_58"},{"key":"e_1_3_3_24_2","first-page":"45","article-title":"Introducing the graph 500","volume":"19","author":"Murphy Richard C.","year":"2010","unstructured":"Richard C. Murphy, Kyle B. Wheeler, Brian W. Barrett, and James A. Ang. 2010. Introducing the graph 500. Cray Users Group 19 (2010), 45\u201374.","journal-title":"Cray Users Group"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199462"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCAM.2008.22"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2631160"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00268499"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989419"},{"key":"e_1_3_3_34_2","first-page":"511","volume-title":"Proceedings of the EDBT","author":"Veloso Ren\u00ea Rodrigues","year":"2014","unstructured":"Ren\u00ea Rodrigues Veloso, Lo\u00efc Cerf, Wagner Meira, and Mohammed J. Zaki. 2014. Reachability queries in very large graphs: A fast refined online search approach. In Proceedings of the EDBT. 511\u2013522."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.53"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0468-3"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505724"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0256-4"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_6"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3556540","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3556540","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:32Z","timestamp":1750186832000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3556540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,21]]},"references-count":40,"alternative-id":["10.1145\/3556540"],"URL":"https:\/\/doi.org\/10.1145\/3556540","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,21]]}}}