{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T04:36:14Z","timestamp":1747802174832,"version":"3.41.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T00:00:00Z","timestamp":1737417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T00:00:00Z","timestamp":1737417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No. 61932004","62072205"],"award-info":[{"award-number":["No. 61932004","62072205"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cluster Comput"],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s10586-024-04814-8","type":"journal-article","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T10:27:59Z","timestamp":1737455279000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["TDS: fast answering reachability queries with hierarchical traversal trees"],"prefix":"10.1007","volume":"28","author":[{"given":"Daoliang","family":"He","sequence":"first","affiliation":[]},{"given":"Pingpeng","family":"Yuan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,21]]},"reference":[{"issue":"Supplement","key":"4814_CR1","first-page":"2555","volume":"22","author":"F Ai","year":"2019","unstructured":"Ai, F.: Research on a large-scale community detection algorithm based on non-weighted graph. Clust. Comput. 22(Supplement), 2555\u20132562 (2019)","journal-title":"Clust. Comput."},{"issue":"Suppl 1","key":"4814_CR2","doi-asserted-by":"publisher","first-page":"847","DOI":"10.1007\/s10586-017-1332-3","volume":"22","author":"S Song","year":"2019","unstructured":"Song, S., Huang, W., Sun, Y.: Semantic query graph based SPARQL generation from natural language questions. Clust. Comput. 22(Suppl 1), 847\u2013858 (2019)","journal-title":"Clust. Comput."},{"issue":"4","key":"4814_CR3","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":"4814_CR4","unstructured":"Reps, T.W.: Program analysis via graph reachability. In: Logic Programming, Proceedings of the 1997 International Symposium, pp. 5\u201319. MIT Press (1997)"},{"key":"4814_CR5","doi-asserted-by":"crossref","unstructured":"Jin, R., Hong, H., Wang, H., Ruan, N., Xiang, Y.: Computing label-constraint reachability in graph databases. In: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 123\u2013134. ACM (2010)","DOI":"10.1145\/1807167.1807183"},{"key":"4814_CR6","doi-asserted-by":"crossref","unstructured":"Zhu, J., Nie, Z., Liu, X., Zhang, B., Wen, J.: StatSnowball: a statistical approach to extracting entity relationships. In: Proceedings of the 18th International Conference on World Wide Web, WWW, pp. 101\u2013110. ACM (2009)","DOI":"10.1145\/1526709.1526724"},{"issue":"1","key":"4814_CR7","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s10586-022-03540-3","volume":"26","author":"S Srivastava","year":"2023","unstructured":"Srivastava, S., Singh, A.K.: Fraud detection in the distributed graph database. Clust. Comput. 26(1), 515\u2013537 (2023)","journal-title":"Clust. Comput."},{"key":"4814_CR8","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Wang, H.: Efficiently answering reachability queries on very large directed graphs. In: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 595\u2013608. ACM (2008)","DOI":"10.1145\/1376616.1376677"},{"key":"4814_CR9","doi-asserted-by":"crossref","unstructured":"Schaik, S.J., Moor, O.: A memory efficient reachability data structure through bit vector compression. In: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 913\u2013924. ACM (2011)","DOI":"10.1145\/1989323.1989419"},{"key":"4814_CR10","doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., Fuhry, D.: 3-HOP: a high-compression indexing scheme for reachability query. In: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 813\u2013826. ACM (2009)","DOI":"10.1145\/1559845.1559930"},{"issue":"1","key":"4814_CR11","doi-asserted-by":"publisher","first-page":"276","DOI":"10.14778\/1920841.1920879","volume":"3","author":"H Yildirim","year":"2010","unstructured":"Yildirim, H., Chaoji, V., Zaki, M.J.: GRAIL: scalable reachability index for large graphs. Proc. VLDB Endow. 3(1), 276\u2013284 (2010)","journal-title":"Proc. VLDB Endow."},{"key":"4814_CR12","doi-asserted-by":"crossref","unstructured":"Tri\u00dfl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 845\u2013856. ACM (2007)","DOI":"10.1145\/1247480.1247573"},{"issue":"3","key":"4814_CR13","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":"12","key":"4814_CR14","doi-asserted-by":"publisher","first-page":"1191","DOI":"10.14778\/2732977.2732992","volume":"7","author":"H Wei","year":"2014","unstructured":"Wei, H., Yu, J.X., Lu, C., Jin, R.: Reachability querying: an independent permutation labeling approach. Proc. VLDB Endow. 7(12), 1191\u20131202 (2014)","journal-title":"Proc. VLDB Endow."},{"issue":"2","key":"4814_CR15","doi-asserted-by":"publisher","first-page":"1000","DOI":"10.1109\/TSC.2020.2969898","volume":"15","author":"P Yuan","year":"2022","unstructured":"Yuan, P., You, Y., Zhou, S., Jin, H., Liu, L.: Providing fast reachability query services with MGTag: a multi-dimensional graph labeling method. IEEE Trans. Serv. Comput. 15(2), 1000\u20131011 (2022)","journal-title":"IEEE Trans. Serv. Comput."},{"issue":"4","key":"4814_CR16","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/s11280-016-0407-z","volume":"20","author":"L Li","year":"2017","unstructured":"Li, L., Hua, W., Zhou, X.: HD-GDD: high dimensional graph dominance drawing approach for reachability query. World Wide Web 20(4), 677\u2013696 (2017)","journal-title":"World Wide Web"},{"key":"4814_CR17","doi-asserted-by":"crossref","unstructured":"Yu, J.X., Cheng, J.: Graph reachability queries: a survey. In: Managing and Mining Graph Data, vol. 40, pp. 181\u2013215. Springer (2010)","DOI":"10.1007\/978-1-4419-6045-0_6"},{"key":"4814_CR18","doi-asserted-by":"crossref","unstructured":"Chen, Y., Chen, Y.: An efficient algorithm for answering graph reachability queries. In: Proceedings of the 24th International Conference on Data Engineering, ICDE, pp. 893\u2013902. IEEE Computer Society (2008)","DOI":"10.1109\/ICDE.2008.4497498"},{"key":"4814_CR19","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: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 193\u2013204. ACM (2013)","DOI":"10.1145\/2463676.2465286"},{"issue":"5","key":"4814_CR20","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4814_CR21","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\u20131744 (2011)","journal-title":"ACM Trans. Database Syst."},{"issue":"4","key":"4814_CR22","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/99935.99944","volume":"15","author":"HV Jagadish","year":"1990","unstructured":"Jagadish, H.V.: A compression technique to materialize transitive closure. ACM Trans. Database Syst. 15(4), 558\u2013598 (1990)","journal-title":"ACM Trans. Database Syst."},{"key":"4814_CR23","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 253\u2013262. ACM (1989)","DOI":"10.1145\/67544.66950"},{"key":"4814_CR24","doi-asserted-by":"crossref","unstructured":"Chen, Y.: General spanning trees and reachability query evaluation. In: Canadian Conference on Computer Science & Software Engineering, C3S2E, pp. 243\u2013252. ACM (2009)","DOI":"10.1145\/1557626.1557665"},{"key":"4814_CR25","doi-asserted-by":"crossref","unstructured":"Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: answering graph reachability queries in constant time. In: Proceedings of the 22nd International Conference on Data Engineering, ICDE, pp. 75\u201386. IEEE Computer Society (2006)","DOI":"10.1109\/ICDE.2006.53"},{"key":"4814_CR26","doi-asserted-by":"crossref","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: HOPI: an efficient connection index for complex XML document collections. In: Proceedings of the 9th International Conference on Extending Database Technology, EDBT, vol. 2992, pp. 237\u2013255. Springer (2004)","DOI":"10.1007\/978-3-540-24741-8_15"},{"key":"4814_CR27","doi-asserted-by":"crossref","unstructured":"Cheng, J., Yu, J.X., Lin, X., Wang, H., Yu, P.S.: Fast computation of reachability labeling for large graphs. In: Proceedings of the 10th International Conference on Extending Database Technology, EDBT, vol. 3896, pp. 961\u2013979. Springer (2006)","DOI":"10.1007\/11687238_56"},{"key":"4814_CR28","doi-asserted-by":"crossref","unstructured":"Cai, J., Poon, C.K.: Path-hop: efficiently indexing large graphs for reachability queries. In: Proceedings of the 19th Conference on Information and Knowledge Management, CIKM, pp. 119\u2013128. ACM (2010)","DOI":"10.1145\/1871437.1871457"},{"issue":"14","key":"4814_CR29","doi-asserted-by":"publisher","first-page":"1978","DOI":"10.14778\/2556549.2556578","volume":"6","author":"R Jin","year":"2013","unstructured":"Jin, R., Wang, G.: Simple, fast, and scalable reachability oracle. Proc. VLDB Endow. 6(14), 1978\u20131989 (2013)","journal-title":"Proc. VLDB Endow."},{"key":"4814_CR30","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: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 1323\u20131334. ACM (2014)","DOI":"10.1145\/2588555.2612181"},{"key":"4814_CR31","unstructured":"Chen, L., Gupta, A., Kurul, M.E.: Stack-based algorithms for pattern matching on DAGs. In: Proceedings of the 31st International Conference on Very Large Data Bases, VLDB, pp. 493\u2013504. ACM (2005)"},{"key":"4814_CR32","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: 29th IEEE International Conference on Data Engineering, ICDE, pp. 1009\u20131020. IEEE Computer Society (2013)","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"4814_CR33","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"GD Battista","year":"1999","unstructured":"Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, Upper Saddle River (1999)"},{"key":"4814_CR34","unstructured":"Veloso, R.R., Cerf, L., Jr., W.M., Zaki, M.J.: Reachability queries in very large graphs: a fast refined online search approach. In: Proceedings of the 17th International Conference on Extending Database Technology, EDBT, pp. 511\u2013522. Springer (2014)"},{"key":"4814_CR35","doi-asserted-by":"crossref","unstructured":"Sengupta, N., Bagchi, A., Ramanath, M., Bedathur, S.: ARROW: approximating reachability using random walks over web-scale graphs. In: Proceedings of the 35th IEEE International Conference on Data Engineering, ICDE, pp. 470\u2013481. IEEE Computer Society (2019)","DOI":"10.1109\/ICDE.2019.00049"},{"key":"4814_CR36","doi-asserted-by":"crossref","unstructured":"Su, Z., Wang, D., Zhang, X., Cui, L., Miao, C.: Efficient reachability query with extreme labeling filter. In: Proceedings of the 5th International Conference on Web Search and Data Mining, WSDM, pp. 966\u2013975. ACM (2022)","DOI":"10.1145\/3488560.3498446"},{"issue":"3","key":"4814_CR37","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s41019-019-00099-9","volume":"4","author":"S Anirban","year":"2019","unstructured":"Anirban, S., Wang, J., Islam, M.S.: Modular decomposition-based graph compression for fast reachability detection. Data Sci. Eng. 4(3), 193\u2013207 (2019)","journal-title":"Data Sci. Eng."},{"key":"4814_CR38","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: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 375\u2013390. ACM (2017)","DOI":"10.1145\/3035918.3035927"},{"issue":"3","key":"4814_CR39","first-page":"2590","volume":"35","author":"J Zhou","year":"2023","unstructured":"Zhou, J., Yu, J.X., Qiu, Y., Tang, X., Chen, Z., Du, M.: Fast reachability queries answering based on RCN reduction. IEEE Trans. Knowl. Data Eng. 35(3), 2590\u20132609 (2023)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"11","key":"4814_CR40","doi-asserted-by":"publisher","first-page":"5321","DOI":"10.1109\/TKDE.2021.3052710","volume":"34","author":"J Dietrich","year":"2022","unstructured":"Dietrich, J., Chang, L., Qian, L., Henry, L.M., McCartin, C., Scholz, B.: Efficient sink-reachability analysis via graph reduction. IEEE Trans. Knowl. Data Eng. 34(11), 5321\u20135335 (2022)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"4814_CR41","doi-asserted-by":"crossref","unstructured":"Valstar, L.D.J., Fletcher, G.H.L., Yoshida, Y.: Landmark indexing for evaluation of label-constrained reachability queries. In: Proceedings of the International Conference on Management of Data, SIGMOD, pp. 345\u2013358. ACM (2017)","DOI":"10.1145\/3035918.3035955"},{"issue":"6","key":"4814_CR42","doi-asserted-by":"publisher","first-page":"812","DOI":"10.14778\/3380750.3380753","volume":"13","author":"Y Peng","year":"2020","unstructured":"Peng, Y., Zhang, Y., Lin, X., Qin, L., Zhang, W.: Answering billion-scale label-constrained reachability queries within microsecond. Proc. VLDB Endow. 13(6), 812\u2013825 (2020)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"4814_CR43","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s00778-021-00695-0","volume":"31","author":"Y Peng","year":"2022","unstructured":"Peng, Y., Lin, X., Zhang, Y., Zhang, W., Qin, L.: Answering reachability and k-reach queries on large graphs with label constraints. VLDB J. 31(1), 101\u2013127 (2022)","journal-title":"VLDB J."},{"issue":"8","key":"4814_CR44","doi-asserted-by":"publisher","first-page":"1645","DOI":"10.14778\/3529337.3529348","volume":"15","author":"X Chen","year":"2022","unstructured":"Chen, X., Peng, Y., Wang, S., Yu, J.X.: DLCR: efficient indexing for label-constrained reachability queries on large dynamic graphs. Proc. VLDB Endow. 15(8), 1645\u20131657 (2022)","journal-title":"Proc. VLDB Endow."},{"key":"4814_CR45","unstructured":"Leskovec, J., Krevl, A.: SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data (2014)"},{"key":"4814_CR46","unstructured":"Leskovec, J., Sosi\u010d, R.: SNAP: a general purpose network analysis and graph mining library in C++. http:\/\/snap.stanford.edu\/snap (2014)"},{"issue":"5439","key":"4814_CR47","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barabsi","year":"1999","unstructured":"Barabsi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999)","journal-title":"Science"}],"container-title":["Cluster Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-024-04814-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10586-024-04814-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10586-024-04814-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,20]],"date-time":"2025-05-20T21:52:38Z","timestamp":1747777958000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10586-024-04814-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,21]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["4814"],"URL":"https:\/\/doi.org\/10.1007\/s10586-024-04814-8","relation":{},"ISSN":["1386-7857","1573-7543"],"issn-type":[{"type":"print","value":"1386-7857"},{"type":"electronic","value":"1573-7543"}],"subject":[],"published":{"date-parts":[[2025,1,21]]},"assertion":[{"value":"21 June 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 October 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The study does not involve any human or animal study.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Research involving human and\/or animal rights"}}],"article-number":"178"}}