{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:12:39Z","timestamp":1780765959458,"version":"3.54.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0953950#1019343"],"award-info":[{"award-number":["IIS-0953950#1019343"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>\n            Reachability query is one of the fundamental queries in graph database. The main idea behind answering reachability queries is to assign vertices with certain labels such that the reachability between any two vertices can be determined by the labeling information. Though several approaches have been proposed for building these reachability labels, it remains open issues on how to handle increasingly large number of vertices in real-world graphs, and how to find the best tradeoff among the labeling size, the query answering time, and the construction time. In this article, we introduce a novel graph structure, referred to as\n            <jats:italic>path-tree<\/jats:italic>\n            , to help labeling very large graphs. The path-tree cover is a spanning subgraph of\n            <jats:italic>G<\/jats:italic>\n            in a tree shape. We show path-tree can be generalized to chain-tree which theoretically can has smaller labeling cost. On top of path-tree and chain-tree index, we also introduce a new compression scheme which groups vertices with similar labels together to further reduce the labeling size. In addition, we also propose an efficient incremental update algorithm for dynamic index maintenance. Finally, we demonstrate both analytically and empirically the effectiveness and efficiency of our new approaches.\n          <\/jats:p>","DOI":"10.1145\/1929934.1929941","type":"journal-article","created":{"date-parts":[[2011,3,17]],"date-time":"2011-03-17T12:40:16Z","timestamp":1300365616000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Path-tree"],"prefix":"10.1145","volume":"36","author":[{"given":"Ruoming","family":"Jin","sequence":"first","affiliation":[{"name":"Kent State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ning","family":"Ruan","sequence":"additional","affiliation":[{"name":"Kent State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Xiang","sequence":"additional","affiliation":[{"name":"The Ohio State University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haixun","family":"Wang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,3,18]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the Data Compression Conference. IEEE, 203--212","author":"Adler M.","unstructured":"Adler , M. and Mitzenmacher , M . 2001. Towards compressing web graphs . In Proceedings of the Data Compression Conference. IEEE, 203--212 . Adler, M. and Mitzenmacher, M. 2001. Towards compressing web graphs. In Proceedings of the Data Compression Conference. IEEE, 203--212."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66950"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02279-1_29"},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases. VLDB Endowment, 493--504","author":"Chen L.","unstructured":"Chen , L. , Gupta , A. , and Kurul , M . 2005. Stack-based algorithms for pattern matching on dags . In Proceedings of the 31st International Conference on Very Large Data Bases. VLDB Endowment, 493--504 . Chen, L., Gupta, A., and Kurul, M. 2005. Stack-based algorithms for pattern matching on dags. In Proceedings of the 31st International Conference on Very Large Data Bases. VLDB Endowment, 493--504."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_56"},{"key":"e_1_2_2_6_1","first-page":"1396","article-title":"On the shortest arborescence of a directed graph. Sci","volume":"14","author":"Chu Y. J.","year":"1965","unstructured":"Chu , Y. J. and Liu , T. H. 1965 . On the shortest arborescence of a directed graph. Sci . Sinica 14 , 1396 -- 1400 . Chu, Y. J. and Liu, T. H. 1965. On the shortest arborescence of a directed graph. Sci. Sinica 14, 1396--1400.","journal-title":"Sinica"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_2_8_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. MIT Press.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms. MIT Press."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.032"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579168"},{"key":"e_1_2_2_13_1","doi-asserted-by":"crossref","unstructured":"Goldberg A. V. Tardos E. and Tarjan R. E. 1990. Network Flow Algorithms. Springer Verlag 101--164.  Goldberg A. V. Tardos E. and Tarjan R. E. 1990. Network Flow Algorithms. Springer Verlag 101--164.","DOI":"10.21236\/ADA214689"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/99935.99944"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807183"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376677"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(75)90019-8"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01446400"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376661"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE). 405--416","author":"Raghavan S.","unstructured":"Raghavan , S. and Garcia-Molina , H . 2003. Representing web graphs . In Proceedings of the International Conference on Data Engineering (ICDE). 405--416 . Raghavan, S. and Garcia-Molina, H. 2003. Representing web graphs. In Proceedings of the International Conference on Data Engineering (ICDE). 405--416."},{"key":"e_1_2_2_22_1","volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT). 237--255","author":"Schenkel R.","unstructured":"Schenkel , R. , Theobald , A. , and Weikum , G . 2004. Hopi: An efficient connection index for complex xml document collections . In Proceedings of the International Conference on Extending Database Technology (EDBT). 237--255 . Schenkel, R., Theobald, A., and Weikum, G. 2004. Hopi: An efficient connection index for complex xml document collections. In Proceedings of the International Conference on Extending Database Technology (EDBT). 237--255."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90032-1"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247573"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.53"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920879"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929934.1929941","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1929934.1929941","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:32Z","timestamp":1750278392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929934.1929941"}},"subtitle":["An efficient reachability indexing scheme for large directed graphs"],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1929934.1929941"],"URL":"https:\/\/doi.org\/10.1145\/1929934.1929941","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}