{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T13:00:59Z","timestamp":1759496459913,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"S3","license":[{"start":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T00:00:00Z","timestamp":1519862400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61472339","61303040","61572421","61272124"],"award-info":[{"award-number":["61472339","61303040","61572421","61272124"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shanghai Alliance Program","award":["LM201552"],"award-info":[{"award-number":["LM201552"]}]},{"name":"Shanghai University of Engineering and Technology School-Enterprise cooperation projects","award":["DZ-025"],"award-info":[{"award-number":["DZ-025"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cluster Comput"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s10586-018-2278-9","type":"journal-article","created":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T08:10:30Z","timestamp":1519891830000},"page":"6517-6527","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient computation of the transitive closure size"],"prefix":"10.1007","volume":"22","author":[{"given":"Xian","family":"Tang","sequence":"first","affiliation":[]},{"given":"Ziyang","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Kai","family":"Li","sequence":"additional","affiliation":[]},{"given":"Xiang","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,1]]},"reference":[{"issue":"2","key":"2278_CR1","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":"2278_CR2","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s13173-012-0089-z","volume":"19","author":"CER Alves","year":"2013","unstructured":"Alves, C.E.R., C\u00e1ceres, E.N., de Castro, A.A., Song, S.W., Szwarcfiter, J.L.: Parallel transitive closure algorithm. J. Braz. Comp. Soc. 19(2), 161\u2013166 (2013)","journal-title":"J. Braz. Comp. Soc."},{"key":"2278_CR3","unstructured":"Chen, Y., Chen, Y.: Decomposing dags into spanning trees: A new way to compress transitive closures. In: Proceedings of the 27th International Conference on Data Engineering, ICDE 2011, April 11\u201316, 2011, Hannover, Germany, pp. 1007\u20131018 (2011)"},{"key":"2278_CR4","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":"2278_CR5","unstructured":"Cohen, E.: Estimating the size of the transitive closure in linear time. In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20\u201322 November 1994, pp. 190\u2013200 (1994)"},{"key":"2278_CR6","doi-asserted-by":"crossref","unstructured":"Dar, S.: Augmenting Databases with Generalized Transitive Closure. PhD thesis, Univ. ofWisconsin-Madison (1993)","DOI":"10.1109\/69.243510"},{"key":"2278_CR7","unstructured":"Ding, C.H.Q., He, X., Peng, H.: Finding cliques in protein interaction networks via transitive closure of a weighted graph. In: Proceedings of the 5th international workshop on Bioinformatics, BIOKDD 2005, Chicago, Illinois, USA, August 21, 2005, pp. 69\u201375 (2005)"},{"key":"2278_CR8","unstructured":"Fletcher, G.H.L., Gyssens, M., Leinders, D., den Bussche, J.V., Gucht, D.V., Vansummeren, S., Wu., Y.: The impact of transitive closure on the boolean expressiveness of navigational query languages on graphs. In: Foundations of Information and Knowledge Systems\u20147th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings, pp. 124\u2013143 (2012)"},{"issue":"1\u20132","key":"2278_CR9","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10472-013-9346-x","volume":"73","author":"GHL Fletcher","year":"2015","unstructured":"Fletcher, G.H.L., Gyssens, M., Leinders, D., den Bussche, J.V., Gucht, D.V., Vansummeren, S., Wu, Y.: The impact of transitive closure on the expressiveness of navigational query languages on unlabeled graphs. Ann. Math. Artif. Intell. 73(1\u20132), 167\u2013203 (2015)","journal-title":"Ann. Math. Artif. Intell."},{"key":"2278_CR10","unstructured":"Gora lcikov\u00e1, A., Koubek, V.: A reduct-and-closure algorithm for graphs. In: Mathematical Foundations of Computer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3\u20137, 1979, pp. 301\u2013307 (1979)"},{"key":"2278_CR11","unstructured":"Pfeiffer, J.J., Fond, T.L., Moreno, S., Neville, J.: Fast generation of large scale social networks while incorporating transitive closures. In: 2012 International Conference on Privacy, Security, Risk and Trust, PASSAT 2012, and 2012 International Confernece on Social Computing, SocialCom 2012, Amsterdam, Netherlands, September 3\u20135, 2012, pp. 154\u2013165 (2012)"},{"key":"2278_CR12","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":"14","key":"2278_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":"2278_CR14","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1007\/978-1-4939-2864-4_158","volume-title":"Encyclopedia of Algorithms","author":"Valerie King","year":"2016","unstructured":"King, V.: Fully dynamic transitive closure. In: Encyclopedia of Algorithms, pp. 808\u2013809 (2016)"},{"key":"2278_CR15","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1145\/1227161.1370597","volume":"12","author":"I Krommidas","year":"2008","unstructured":"Krommidas, I., Zaroliagis, C.D.: An experimental study of algorithms for fully dynamic transitive closure. ACM J. Exp. Algorithm 12, 16 (2008)","journal-title":"ACM J. Exp. Algorithm"},{"issue":"1\u20132","key":"2278_CR16","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.dam.2012.06.013","volume":"161","author":"P Niesink","year":"2013","unstructured":"Niesink, P., Poulin, K., Sajna, M.: Computing transitive closure of bipolar weighted digraphs. Discret. Appl. Math. 161(1\u20132), 217\u2013243 (2013)","journal-title":"Discret. Appl. Math."},{"key":"2278_CR17","unstructured":"Palkowski, M., Bielecki, W.: Optimizing numerical code by means of the transitive closure of dependence graphs. In: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, FedCSIS 2017, Prague, Czech Republic, September 3\u20136, 2017., pp. 523\u2013526 (2017)"},{"issue":"1","key":"2278_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1328911.1328917","volume":"4","author":"L Roditty","year":"2008","unstructured":"Roditty, L.: A faster and simpler fully dynamic transitive closure. ACM Trans. Algorithms 4(1), 1\u201316 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"2278_CR19","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/s00453-008-9166-2","volume":"56","author":"P Sankowski","year":"2010","unstructured":"Sankowski, P., Mucha, M.: Fast dynamic transitive closure with lookahead. Algorithmica 56(2), 180\u2013197 (2010)","journal-title":"Algorithmica"},{"key":"2278_CR20","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":"2278_CR21","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":"2278_CR22","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1109\/TKDE.2016.2631160","volume":"29","author":"J Su","year":"2017","unstructured":"Su, J., Zhu, Q., Wei, H., Yu, J.X.: Reachability querying: can it be even faster? IEEE Trans. Knowl. Data Eng. 29(3), 683\u2013697 (2017)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"2278_CR23","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":"2278_CR24","doi-asserted-by":"crossref","unstructured":"ten Cate, B.: The expressivity of xpath with transitive closure. In: Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26\u201328, 2006, Chicago, Illinois, USA, pp. 328\u2013337 (2006)","DOI":"10.1145\/1142351.1142398"},{"key":"2278_CR25","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":"1","key":"2278_CR26","doi-asserted-by":"publisher","first-page":"145","DOI":"10.3233\/IDA-140701","volume":"19","author":"J Wan","year":"2015","unstructured":"Wan, J., Zhu, Q., Lei, D., Lu, J.: Outlier detection based on transitive closure. Intell. Data Anal. 19(1), 145\u2013160 (2015)","journal-title":"Intell. Data Anal."},{"issue":"12","key":"2278_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":"2278_CR28","doi-asserted-by":"crossref","unstructured":"Williams, V.V: Multiplying matrices faster than coppersmith-winograd. In STOC, pp. 887\u2013898 (2012)","DOI":"10.1145\/2213977.2214056"},{"key":"2278_CR29","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2\u20134, 1990, Nashville, Tennessee, USA, pp. 230\u2013242 (1990)","DOI":"10.1145\/298514.298576"},{"key":"2278_CR30","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":"2278_CR31","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":"2278_CR32","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":"2278_CR33","unstructured":"Zhou, J., Zhou, S., Yu, J.X., Wei, H., Chen, Z., Tang, X.: DAG reduction: Fast answering reachability queries. In: Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14\u201319, 2017, pp. 375\u2013390 (2017)"},{"key":"2278_CR34","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, pages 1323\u20131334 (2014)","DOI":"10.1145\/2588555.2612181"}],"container-title":["Cluster Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-018-2278-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10586-018-2278-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-018-2278-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T02:03:49Z","timestamp":1660529029000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10586-018-2278-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,1]]},"references-count":34,"journal-issue":{"issue":"S3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["2278"],"URL":"https:\/\/doi.org\/10.1007\/s10586-018-2278-9","relation":{},"ISSN":["1386-7857","1573-7543"],"issn-type":[{"type":"print","value":"1386-7857"},{"type":"electronic","value":"1573-7543"}],"subject":[],"published":{"date-parts":[[2018,3,1]]},"assertion":[{"value":"4 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2018","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}