{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T05:59:02Z","timestamp":1774677542610,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,8]]},"abstract":"<jats:p>\n            Reachability query is a fundamental graph operation which answers whether a vertex can reach another vertex over a large directed graph\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>n<\/jats:italic>\n            vertices and\n            <jats:italic>m<\/jats:italic>\n            edges, and has been extensively studied. In the literature, all the approaches compute a label for every vertex in a graph\n            <jats:italic>G<\/jats:italic>\n            by index construction offline. The query time for answering reachability queries online is affected by the quality of the labels computed in index construction. The three main costs are the index construction time, the index size, and the query time. Some of the up-to-date approaches can answer reachability queries efficiently, but spend non-linear time to construct an index. Some of the up-to-date approaches construct an index in linear time and space, but may need to depth-first search\n            <jats:italic>G<\/jats:italic>\n            at run-time in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>m<\/jats:italic>\n            ). In this paper, as the first, we propose a new randomized labeling approach to answer reachability queries, and the randomness is by independent permutation. We conduct extensive experimental studies to compare with the up-to-date approaches using 19 large real datasets used in the existing work and synthetic datasets. We confirm the efficiency of our approach.\n          <\/jats:p>","DOI":"10.14778\/2732977.2732992","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"1191-1202","source":"Crossref","is-referenced-by-count":57,"title":["Reachability querying"],"prefix":"10.14778","volume":"7","author":[{"given":"Hao","family":"Wei","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Can","family":"Lu","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruoming","family":"Jin","sequence":"additional","affiliation":[{"name":"Kent State University Kent, OH"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66950"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"key":"e_1_2_1_3_1","volume-title":"Proc. of SEQUENCES'97","author":"Broder A.","year":"1997","unstructured":"A. Broder . On the resemblance and containment of documents . In Proc. of SEQUENCES'97 , 1997 . A. Broder. On the resemblance and containment of documents. In Proc. of SEQUENCES'97, 1997."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276781"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1871437.1871457"},{"key":"e_1_2_1_6_1","volume-title":"Proc. of ICWSM'10","author":"Cha M.","year":"2010","unstructured":"M. Cha , H. Haddadi , F. Benevenuto , and P. K. Gummadi . Measuring user influence in twitter: The million follower fallacy . In Proc. of ICWSM'10 , 2010 . M. Cha, H. Haddadi, F. Benevenuto, and P. K. Gummadi. Measuring user influence in twitter: The million follower fallacy. In Proc. of ICWSM'10, 2010."},{"key":"e_1_2_1_7_1","volume-title":"Proc. of VLDB'05","author":"Chen L.","year":"2005","unstructured":"L. Chen , A. Gupta , and M. E. Kurul . Stack-based algorithms for pattern matching on dags . In Proc. of VLDB'05 , 2005 . L. Chen, A. Gupta, and M. E. Kurul. Stack-based algorithms for pattern matching on dags. In Proc. of VLDB'05, 2005."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767832"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465286"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_56"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353370"},{"key":"e_1_2_1_13_1","volume-title":"Proc. of SODA'02","author":"Cohen E.","year":"2002","unstructured":"E. Cohen , E. Halperin , H. Kaplan , and U. Zwick . Reachability and distance queries via 2-hop labels . In Proc. of SODA'02 , 2002 . E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. Reachability and distance queries via 2-hop labels. In Proc. of SODA'02, 2002."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_2_1_15_1","volume-title":"Statistical tables for biological, agricultural and medical research. Oliver and Boyd","author":"Fisher R. A.","year":"1949","unstructured":"R. A. Fisher , F. Yates , Statistical tables for biological, agricultural and medical research. Oliver and Boyd , Edinburgh , 3 rd edition, 1949 . R. A. Fisher, F. Yates, et al. Statistical tables for biological, agricultural and medical research. Oliver and Boyd, Edinburgh, 3rd edition, 1949.","edition":"3"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99944"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213856"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1929934.1929941"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556578"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376677"},{"key":"e_1_2_1_22_1","volume-title":"The art of computer programming","author":"Knuth D. E.","unstructured":"D. E. Knuth . The art of computer programming , volume 2: seminumerical algorithms, 1981 . D. E. Knuth. The art of computer programming, volume 2: seminumerical algorithms, 1981."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90032-1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989419"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.53"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0256-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_6"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732977.2732992","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:21:57Z","timestamp":1672226517000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732977.2732992"}},"subtitle":["an independent permutation labeling approach"],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":31,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.14778\/2732977.2732992"],"URL":"https:\/\/doi.org\/10.14778\/2732977.2732992","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,8]]}}}