{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:58:56Z","timestamp":1760709536957,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T00:00:00Z","timestamp":1519603200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00778-018-0495-8","type":"journal-article","created":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T06:03:16Z","timestamp":1519624996000},"page":"271-296","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Accelerating reachability query processing based on $$\\varvec{DAG}$$ DAG reduction"],"prefix":"10.1007","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6494-5319","authenticated-orcid":false,"given":"Junfeng","family":"Zhou","sequence":"first","affiliation":[]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Na","family":"Li","sequence":"additional","affiliation":[]},{"given":"Hao","family":"Wei","sequence":"additional","affiliation":[]},{"given":"Ziyang","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Xian","family":"Tang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,26]]},"reference":[{"key":"495_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: SIGMOD, pp. 253\u2013262 (1989)","DOI":"10.1145\/67544.66950"},{"issue":"2","key":"495_CR2","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho, A.V., Garey, M.R., Ullman, J.D.: The transitive reduction of a directed graph. SIAM J. Comput. 1(2), 131\u2013137 (1972)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"495_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1480506.1480511","volume":"42","author":"P Boldi","year":"2008","unstructured":"Boldi, P., Santini, M., Vigna, S.: A large time-aware web graph. SIGIR Forum 42(2), 33\u201338 (2008)","journal-title":"SIGIR Forum"},{"key":"495_CR4","doi-asserted-by":"crossref","unstructured":"Cha, M., Haddadi, H., Benevenuto, F., Gummadi, P.K.: Measuring user influence in twitter: the million follower fallacy. In: ICWSM (2010)","DOI":"10.1609\/icwsm.v4i1.14033"},{"key":"495_CR5","doi-asserted-by":"crossref","unstructured":"Cheng, J., Huang, S., Wu, H., Fu, A.W.: TF-label: a topological-folding labeling scheme for reachability querying in a large graph. In: SIGMOD, pp. 193\u2013204 (2013)","DOI":"10.1145\/2463676.2465286"},{"key":"495_CR6","doi-asserted-by":"crossref","unstructured":"Cohen, E.: Estimating the size of the transitive closure in linear time. In: 35th Annual Symposium on Foundations of Computer Science, pp. 190\u2013200 (1994)","DOI":"10.1109\/SFCS.1994.365694"},{"key":"495_CR7","doi-asserted-by":"crossref","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: ACM-SIAM, pp. 937\u2013946 (2002)","DOI":"10.1137\/S0097539702403098"},{"key":"495_CR8","doi-asserted-by":"crossref","unstructured":"Fan, W., Li, J., Wang, X., Wu, Y.: Query preserving graph compression. In: SIGMOD, pp. 157\u2013168 (2012)","DOI":"10.1145\/2213836.2213855"},{"issue":"1\u20133","key":"495_CR9","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/0012-365X(93)90164-O","volume":"111","author":"M Habib","year":"1993","unstructured":"Habib, M., Morvan, M., Rampon, J.: On the calculation of transitive reduction\u2014closure of orders. Discrete Math. 111(1\u20133), 289\u2013303 (1993)","journal-title":"Discrete Math."},{"key":"495_CR10","doi-asserted-by":"crossref","unstructured":"Jiang, H., Wang, W., Lu, H., Yu, J.X.: Holistic twig joins on indexed XML documents. In: VLDB, pp. 273\u2013284 (2003)","DOI":"10.1016\/B978-012722442-8\/50032-X"},{"key":"495_CR11","doi-asserted-by":"crossref","unstructured":"Jin, R., Ruan, N., Dey, S., Yu, J.X.: SCARAB: scaling reachability computation on large graphs. In: SIGMOD, pp. 169\u2013180 (2012)","DOI":"10.1145\/2213836.2213856"},{"issue":"1","key":"495_CR12","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/1929934.1929941","volume":"36","author":"R Jin","year":"2011","unstructured":"Jin, R., Ruan, N., Xiang, Y., Wang, H.: Path-tree: an efficient reachability indexing scheme for large directed graphs. ACM Trans. Database Syst. 36(1), 7 (2011)","journal-title":"ACM Trans. Database Syst."},{"issue":"14","key":"495_CR13","first-page":"1978","volume":"6","author":"R Jin","year":"2013","unstructured":"Jin, R., Wang, G.: Simple, fast, and scalable reachability oracle. PVLDB 6(14), 1978\u20131989 (2013)","journal-title":"PVLDB"},{"key":"495_CR14","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Fuhry, D.: 3-hop: a high-compression indexing scheme for reachability query. In: SIGMOD, pp. 813\u2013826 (2009)","DOI":"10.1145\/1559845.1559930"},{"key":"495_CR15","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In: SIGMOD, pp. 595\u2013608 (2008)","DOI":"10.1145\/1376616.1376677"},{"key":"495_CR16","doi-asserted-by":"crossref","unstructured":"Katajainen, J., Tr\u00e4ff, J.L.: A meticulous analysis of mergesort programs. In: CIAC\u201997, pp. 217\u2013228 (1997)","DOI":"10.1007\/3-540-62592-5_74"},{"key":"495_CR17","unstructured":"Kornaropoulos, E.M., Tollis, I.G.: Weak dominance drawings and linear extension diameter. CoRR. arXiv:1108.1439 [cs.DS] (2011)"},{"issue":"2","key":"495_CR18","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF00383402","volume":"8","author":"T-H Ma","year":"1991","unstructured":"Ma, T.-H., Spinrad, J.: Transitive closure for restricted classes of partial orders. Order 8(2), 175\u2013183 (1991)","journal-title":"Order"},{"key":"495_CR19","doi-asserted-by":"crossref","unstructured":"Seufert, S., Anand, A., Bedathur, S.J., Weikum, G.: FERRARI: flexible and efficient reachability range assignment for graph indexing. In: ICDE, pp. 1009\u20131020 (2013)","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"495_CR20","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(88)90032-1","volume":"58","author":"K Simon","year":"1988","unstructured":"Simon, K.: An improved algorithm for transitive closure on acyclic digraphs. Theor. Comput. Sci. 58, 325\u2013346 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"495_CR21","first-page":"683","volume":"29","author":"J Su","year":"2017","unstructured":"Su, J., Zhu, Q., Wei, H., Yu, J.X.: Reachability querying: Can it be even faster? TKDE 29(3), 683\u2013697 (2017)","journal-title":"TKDE"},{"issue":"2","key":"495_CR22","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"495_CR23","doi-asserted-by":"crossref","unstructured":"Tri\u00dfl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: SIGMOD, pp. 845\u2013856 (2007)","DOI":"10.1145\/1247480.1247573"},{"issue":"2","key":"495_CR24","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298\u2013313 (1982)","journal-title":"SIAM J. Comput."},{"key":"495_CR25","doi-asserted-by":"crossref","unstructured":"van Schaik, S.J., de Moor, O.: A memory efficient reachability data structure through bit vector compression. In: SIGMOD, pp. 913\u2013924 (2011)","DOI":"10.1145\/1989323.1989419"},{"key":"495_CR26","unstructured":"Veloso, R.R., Cerf, L., Junior, W.M., Zaki, M.J.: Reachability queries in very large graphs: a fast refined online search approach. In: EDBT, pp. 511\u2013522 (2014)"},{"issue":"12","key":"495_CR27","first-page":"1191","volume":"7","author":"H Wei","year":"2014","unstructured":"Wei, H., Yu, J.X., Lu, C., Jin, R.: Reachability querying: an independent permutation labeling approach. PVLDB 7(12), 1191\u20131202 (2014)","journal-title":"PVLDB"},{"key":"495_CR28","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith\u2013Winograd. In: STOC, pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"495_CR29","doi-asserted-by":"crossref","unstructured":"Yano, Y., Akiba, T., Iwata, Y., Yoshida, Y.: Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In: CIKM, pp. 1601\u20131606 (2013)","DOI":"10.1145\/2505515.2505724"},{"issue":"1","key":"495_CR30","first-page":"276","volume":"3","author":"H Yildirim","year":"2010","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: scalable reachability index for large graphs. PVLDB 3(1), 276\u2013284 (2010)","journal-title":"PVLDB"},{"issue":"4","key":"495_CR31","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00778-011-0256-4","volume":"21","author":"H Yildirim","year":"2012","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: a scalable index for reachability queries in very large graphs. VLDB J. 21(4), 509\u2013534 (2012)","journal-title":"VLDB J."},{"key":"495_CR32","doi-asserted-by":"crossref","unstructured":"Zhou, J., Zhou, S., Yu, J.X., Wei, H., Chen, Z., Tang, X.: DAG reduction: fast answering reachability queries. In: SIGMOD, pp. 375\u2013390 (2017)","DOI":"10.1145\/3035918.3035927"},{"key":"495_CR33","doi-asserted-by":"crossref","unstructured":"Zhu, A.D., Lin, W., Wang, S., Xiao, X.: Reachability queries on large dynamic graphs: a total order approach. In: SIGMOD, pp. 1323\u20131334 (2014)","DOI":"10.1145\/2588555.2612181"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-018-0495-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-018-0495-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-018-0495-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T08:36:17Z","timestamp":1693557377000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-018-0495-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,26]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["495"],"URL":"https:\/\/doi.org\/10.1007\/s00778-018-0495-8","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"type":"print","value":"1066-8888"},{"type":"electronic","value":"0949-877X"}],"subject":[],"published":{"date-parts":[[2018,2,26]]},"assertion":[{"value":"16 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}