{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T00:36:02Z","timestamp":1791074162853,"version":"4.1.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>\n                    We study the problem of answering\n                    <jats:bold>\n                      <jats:italic>k<\/jats:italic>\n                      -hop reachability queries\n                    <\/jats:bold>\n                    in a directed graph, i.e., whether there exists a directed path of length\n                    <jats:italic>k<\/jats:italic>\n                    , from a source query vertex to a target query vertex in the input graph. The problem of\n                    <jats:italic>k<\/jats:italic>\n                    -hop reachability is a general problem of the classic reachability (where\n                    <jats:italic>k<\/jats:italic>\n                    = \u221e). Existing indexes for processing classic reachability queries, as well as for processing shortest path queries, are not applicable or not efficient for processing\n                    <jats:italic>k<\/jats:italic>\n                    -hop reachability queries. We propose an index for processing\n                    <jats:italic>k<\/jats:italic>\n                    -hop reachability queries, which is simple in design and efficient to construct. Our experimental results on a wide range of real datasets show that our index is more efficient than the state-of-the-art indexes even for processing classic reachability queries, for which these indexes are primarily designed. We also show that our index is efficient in answering\n                    <jats:italic>k<\/jats:italic>\n                    -hop reachability queries.\n                  <\/jats:p>","DOI":"10.14778\/2350229.2350247","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T08:17:57Z","timestamp":1403597877000},"page":"1292-1303","source":"Crossref","is-referenced-by-count":47,"title":["K-reach"],"prefix":"10.14778","volume":"5","author":[{"given":"James","family":"Cheng","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zechao","family":"Shang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haixun","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873665"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66950"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367611"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.04.008"},{"key":"e_1_2_1_5_1","first-page":"493","volume-title":"VLDB","author":"Chen L.","year":"2005","unstructured":"L. Chen , A. Gupta , and M. E. Kurul . Stack-based algorithms for pattern matching on DAGs . In VLDB , pages 493 -- 504 , 2005 . L. Chen, A. Gupta, and M. E. Kurul. Stack-based algorithms for pattern matching on DAGs. In VLDB, pages 493--504, 2005."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767832"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213888"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0212-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807217"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043652.2043654"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247574"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516417"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_56"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353370"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11733836_47"},{"key":"e_1_2_1_17_1","first-page":"937","volume-title":"SODA","author":"Cohen E.","year":"2002","unstructured":"E. Cohen , E. Halperin , H. Kaplan , and U. Zwick . Reachability and distance queries via 2-hop labels . In SODA , pages 937 -- 946 , 2002 . E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. In SODA, pages 937--946, 2002."},{"key":"e_1_2_1_18_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2001","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms , Second Edition. The MIT Press and McGraw-Hill Book Company , 2001 . T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press and McGraw-Hill Book Company, 2001."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99944"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807183"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213856"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376677"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90032-1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989419"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.53"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516418"},{"issue":"1","key":"e_1_2_1_32_1","first-page":"276","article-title":"Grail: Scalable reachability index for large graphs","volume":"3","author":"Yildirim H.","year":"2010","unstructured":"H. Yildirim , V. Chaoji , and M. J. Zaki . Grail: Scalable reachability index for large graphs . PVLDB , 3 ( 1 ): 276 -- 284 , 2010 . H. Yildirim, V. Chaoji, and M. J. Zaki. Grail: Scalable reachability index for large graphs. PVLDB, 3(1):276--284, 2010.","journal-title":"PVLDB"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00887-0_12"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350247","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T06:27:25Z","timestamp":1672208845000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350247"}},"subtitle":["who is in your small world"],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":34,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350247"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350247","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}