{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T02:21:25Z","timestamp":1771554085719,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T00:00:00Z","timestamp":1771545600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T00:00:00Z","timestamp":1771545600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2026,10]]},"DOI":"10.1007\/s11704-025-50122-8","type":"journal-article","created":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T01:51:13Z","timestamp":1771552273000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reachability-state encoding: bridging tradeoffs between the minimal storage and the fastest query for reachability query"],"prefix":"10.1007","volume":"20","author":[{"given":"Hu-Quan","family":"Kang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xing-Li","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhou-Yang","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yu-Ang","family":"Ding","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi-Ming","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luo-Yi","family":"Fu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jia-Xin","family":"Ding","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin-Bing","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,20]]},"reference":[{"key":"50122_CR1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"M Newman","year":"2010","unstructured":"Newman M. Networks: An Introduction. Oxford: Oxford University Press, 2010"},{"key":"50122_CR2","first-page":"61","volume-title":"Proceedings of Companion of 2023 International Conference on Management of Data","author":"C Zhang","year":"2023","unstructured":"Zhang C, Bonifati A, \u00d6zsu M T. An overview of reachability indexes on graphs. In: Proceedings of Companion of 2023 International Conference on Management of Data. 2023, 61\u201368"},{"issue":"9","key":"50122_CR3","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1145\/3434642","volume":"64","author":"S Sakr","year":"2021","unstructured":"Sakr S, Bonifati A, Voigt H, Iosup A, Ammar K, Angles R, Aref W, Arenas M, Besta M, Boncz P A, Daudjee K, Valle E D, Dumbrava S, Hartig O, Haslhofer B, Hegeman T, Hidders J, Hose K, Iamnitchi A, Kalavri V, Kapp H, Martens W, \u00d6zsu M T, Peukert E, Plantikow S, Ragab M, Ripeanu M R, Salihoglu S, Schulz C, Selmer P, Sequeda J F, Shinavier J, Sz\u00e1rnyas G, Tommasini R, Tumeo A, Uta A, Varbanescu A L, Wu H Y, Yakovets N, Yan D, Yoneki E. The future is big graphs: a community view on graph processing systems. Communications of the ACM, 2021, 64(9): 62\u201371","journal-title":"Communications of the ACM"},{"issue":"4","key":"50122_CR4","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1145\/3186728.3164139","volume":"11","author":"S Sahu","year":"2017","unstructured":"Sahu S, Mhedhbi A, Salihoglu S, Lin J, \u00d6zsu M T. The ubiquity of large graphs and surprising challenges of graph processing. Proceedings of the VLDB Endowment, 2017, 11(4): 420\u2013431","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"2","key":"50122_CR5","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s00778-019-00548-x","volume":"29","author":"S Sahu","year":"2020","unstructured":"Sahu S, Mhedhbi A, Salihoglu S, Lin J, \u00d6zsu M T. The ubiquity of large graphs and surprising challenges of graph processing: extended survey. The VLDB Journal, 2020, 29(2): 595\u2013618","journal-title":"The VLDB Journal"},{"issue":"1\u20133","key":"50122_CR6","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. Theoretical Computer Science, 1988, 58(1\u20133): 325\u2013346","journal-title":"Theoretical Computer Science"},{"key":"50122_CR7","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1145\/1989323.1989419","volume-title":"Proceedings of 2011 ACM SIGMOD International Conference on Management of Data","author":"S J van Schaik","year":"2011","unstructured":"van Schaik S J, de Moor O. A memory efficient reachability data structure through bit vector compression. In: Proceedings of 2011 ACM SIGMOD International Conference on Management of Data. 2011, 913\u2013924"},{"key":"50122_CR8","first-page":"1","volume":"74","author":"E Nuutila","year":"1995","unstructured":"Nuutila E. Efficient transitive closure computation in large digraphs. Acta Polytechnica Scandinavica: Mathematics and Computing in Engineering, 1995, 74: 1\u2013124","journal-title":"Acta Polytechnica Scandinavica: Mathematics and Computing in Engineering"},{"issue":"2","key":"50122_CR9","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/66926.66950","volume":"18","author":"R Agrawal","year":"1989","unstructured":"Agrawal R, Borgida A, Jagadish H V. Efficient management of transitive relationships in large data and knowledge bases. ACM SIGMOD Record, 1989, 18(2): 253\u2013262","journal-title":"ACM SIGMOD Record"},{"issue":"1","key":"50122_CR10","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 Transactions on Database Systems (TODS), 2011, 36(1): 7","journal-title":"ACM Transactions on Database Systems (TODS)"},{"key":"50122_CR11","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1376616.1376677","volume-title":"Proceedings of 2008 ACM SIGMOD International Conference on MANAGEMENT of Data","author":"R Jin","year":"2008","unstructured":"Jin R, Xiang Y, Ruan N, Wang H. Efficiently answering reachability queries on very large directed graphs. In: Proceedings of 2008 ACM SIGMOD International Conference on MANAGEMENT of Data. 2008, 595\u2013608"},{"key":"50122_CR12","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1145\/1247480.1247573","volume-title":"Proceedings of 2007 ACM SIGMOD International Conference on Management of Data","author":"S Tri\u00dfl","year":"2007","unstructured":"Tri\u00dfl S, Leser U. Fast and practical indexing and querying of very large graphs. In: Proceedings of 2007 ACM SIGMOD International Conference on Management of Data. 2007, 845\u2013856"},{"key":"50122_CR13","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/ICDE.2006.53","volume-title":"Proceedings of the 22nd International Conference on Data Engineering (ICDE\u201906)","author":"H Wang","year":"2006","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\u201906). 2006, 75"},{"issue":"1\u20132","key":"50122_CR14","first-page":"276","volume":"3","author":"E Bertino","year":"2010","unstructured":"Bertino E, Atzeni P, Tan K L, Chen Y, Tay Y C, Yildirim H, Chaoji V, Zaki M J. GRAIL: scalable reachability index for large graphs. Proceedings of the VLDB Endowment, 2010, 3(1\u20132): 276\u2013284","journal-title":"Proceedings of the VLDB Endowment"},{"key":"50122_CR15","first-page":"1009","volume-title":"Proceedings of 2013 IEEE 29th International Conference on Data Engineering (ICDE)","author":"S Seufert","year":"2013","unstructured":"Seufert S, Anand A, Bedathur S, Weikum G. FERRARI: flexible and efficient reachability range assignment for graph indexing. In: Proceedings of 2013 IEEE 29th International Conference on Data Engineering (ICDE). 2013, 1009\u20131020"},{"issue":"5","key":"50122_CR16","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 Journal on Computing, 2003, 32(5): 1338\u20131355","journal-title":"SIAM Journal on Computing"},{"key":"50122_CR17","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1145\/1559845.1559930","volume-title":"Proceedings of 2009 ACM SIGMOD International Conference on Management of Data","author":"R Jin","year":"2009","unstructured":"Jin R, Xiang Y, Ruan N, Fuhry D. 3-HOP: a high-compression indexing scheme for reachability query. In: Proceedings of 2009 ACM SIGMOD International Conference on Management of Data. 2009, 813\u2013826"},{"key":"50122_CR18","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1145\/1871437.1871457","volume-title":"Proceedings of the 19th ACM International Conference on Information and Knowledge Management","author":"J Cai","year":"2010","unstructured":"Cai J, Poon C K. Path-hop: efficiently indexing large graphs for reachability queries. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 2010, 119\u2013128"},{"issue":"1","key":"50122_CR19","first-page":"1","volume":"27","author":"K Hanauer","year":"2022","unstructured":"Hanauer K, Schulz C, Trummer J. O\u2019Reach: even faster reachability in large graphs. ACM Journal of Experimental Algorithmics, 2022, 27(1): 1\u201327","journal-title":"ACM Journal of Experimental Algorithmics"},{"issue":"14","key":"50122_CR20","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. Proceedings of the VLDB Endowment, 2013, 6(14): 1978\u20131989","journal-title":"Proceedings of the VLDB Endowment"},{"key":"50122_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1145\/2463676.2465286","volume-title":"Proceedings of 2013 ACM SIGMOD International Conference on Management of Data","author":"J Cheng","year":"2013","unstructured":"Cheng J, Huang S, Wu H, Fu A W C. TF-Label: a topological-folding labeling scheme for reachability querying in a large graph. In: Proceedings of 2013 ACM SIGMOD International Conference on Management of Data. 2013, 193\u2013204"},{"key":"50122_CR22","doi-asserted-by":"publisher","first-page":"1601","DOI":"10.1145\/2505515.2505724","volume-title":"Proceedings of the 22nd ACM international conference on Information & Knowledge Management","author":"Y Yano","year":"2013","unstructured":"Yano Y, Akiba T, Iwata Y, Yoshida Y. Fast and scalable reachability queries on graphs by pruned labeling with landmarks and paths. In: Proceedings of the 22nd ACM international conference on Information & Knowledge Management. 2013, 1601\u20131606"},{"key":"50122_CR23","doi-asserted-by":"publisher","first-page":"1323","DOI":"10.1145\/2588555.2612181","volume-title":"Proceedings of 2014 ACM SIGMOD International Conference on Management of Data","author":"A D Zhu","year":"2014","unstructured":"Zhu A D, Lin W, Wang S, Xiao X. Reachability queries on large dynamic graphs: a total order approach. In: Proceedings of 2014 ACM SIGMOD International Conference on Management of Data. 2014, 1323\u20131334"},{"issue":"12","key":"50122_CR24","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. Proceedings of the VLDB Endowment, 2014, 7(12): 1191\u20131202","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"3","key":"50122_CR25","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 Transactions on Knowledge and Data Engineering, 2017, 29(3): 683\u2013697","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"50122_CR26","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1007\/978-3-030-73197-7_52","volume-title":"Proceedings of the 26th International Conference on Database Systems for Advanced Applications","author":"Q Lyu","year":"2021","unstructured":"Lyu Q, Li Y, He B, Gong B. DBL: efficient reachability queries on dynamic graphs. In: Proceedings of the 26th International Conference on Database Systems for Advanced Applications. 2021, 761\u2013777"},{"key":"50122_CR27","first-page":"67","volume-title":"Proceedings of the 39th IEEE International Conference on Data Engineering (ICDE)","author":"C Zhang","year":"2023","unstructured":"Zhang C, Bonifati A, Kapp H, Haprian V I, Lozi J P. A reachability index for recursive label-concatenated graph queries. In: Proceedings of the 39th IEEE International Conference on Data Engineering (ICDE). 2023, 67\u201381"},{"key":"50122_CR28","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/3035918.3035955","volume-title":"Proceedings of 2017 ACM International Conference on Management of Data","author":"L D J Valstar","year":"2017","unstructured":"Valstar L D J, Fletcher G H L, Yoshida Y. Landmark indexing for evaluation of label-constrained reachability queries. In: Proceedings of 2017 ACM International Conference on Management of Data. 2017, 345\u2013358"},{"issue":"6","key":"50122_CR29","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. Proceedings of the VLDB Endowment, 2020, 13(6): 812\u2013825","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"8","key":"50122_CR30","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. Proceedings of the VLDB Endowment, 2022, 15(8): 1645\u20131657","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"2","key":"50122_CR31","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/3451159","volume":"46","author":"Y Chen","year":"2021","unstructured":"Chen Y, Singh G. Graph indexing for efficient evaluation of label-constrained reachability queries. ACM Transactions on Database Systems (TODS), 2021, 46(2): 8","journal-title":"ACM Transactions on Database Systems (TODS)"},{"key":"50122_CR32","first-page":"11","volume-title":"Proceedings of the 34th ACM International Conference on Supercomputing","author":"R Jin","year":"2020","unstructured":"Jin R, Peng Z, Wu W, Dragan F, Agrawal G, Ren B. Parallelizing pruned landmark labeling: dealing with dependencies in graph algorithms. In: Proceedings of the 34th ACM International Conference on Supercomputing. 2020, 11"},{"key":"50122_CR33","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1145\/3035918.3035927","volume-title":"Proceedings of 2017 ACM International Conference on Management of Data","author":"J Zhou","year":"2017","unstructured":"Zhou J, Zhou S, Yu J X, Wei H, Chen Z, Tang X. Dag reduction: fast answering reachability queries. In: Proceedings of 2017 ACM International Conference on Management of Data. 2017, 375\u2013390"},{"key":"50122_CR34","first-page":"1543","volume-title":"Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE)","author":"J Zhou","year":"2022","unstructured":"Zhou J, Yu J X, Qiu Y, Tang X, Chen Z, Du M. Fast reachability queries answering based on RCN reduction (extended abstract). In: Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE). 2022, 1543\u20131544"},{"issue":"2","key":"50122_CR35","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan R. Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1972, 1(2): 146\u2013160","journal-title":"SIAM Journal on Computing"},{"key":"50122_CR36","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1145\/3406325.3451102","volume-title":"Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing","author":"M Bonamy","year":"2021","unstructured":"Bonamy M, Esperet L, Groenland C, Scott A. Optimal labelling schemes for adjacency, comparability, and reachability. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021, 1109\u20131117"},{"key":"50122_CR37","doi-asserted-by":"publisher","first-page":"3792","DOI":"10.1137\/1.9781611977912.134","volume-title":"Proceedings of 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"V V Williams","year":"2024","unstructured":"Williams V V, Xu Y, Xu Z, Zhou R. New bounds for matrix multiplication: from alpha to omega. In: Proceedings of 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2024, 3792\u20133835"},{"issue":"4","key":"50122_CR38","doi-asserted-by":"publisher","first-page":"174104","DOI":"10.1007\/s11704-022-1749-6","volume":"17","author":"X Liu","year":"2023","unstructured":"Liu X, Liu Y, Yin B, Yang H, Luan Z, Qian D. swSpAMM: optimizing large-scale sparse approximate matrix multiplication on Sunway Taihulight. Frontiers of Computer Science, 2023, 17(4): 174104","journal-title":"Frontiers of Computer Science"},{"issue":"2","key":"50122_CR39","first-page":"40","volume":"21","author":"U Awada","year":"2023","unstructured":"Awada U, Zhang J, Chen S, Li S, Yang S. Machine learning driven latency optimization for internet of things applications in edge computing. ZTE Communications, 2023, 21(2): 40\u201352","journal-title":"ZTE Communications"},{"issue":"2","key":"50122_CR40","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1147\/rd.232.0149","volume":"23","author":"J Rissanen","year":"1979","unstructured":"Rissanen J, Langdon G G. Arithmetic coding. IBM Journal of Research and Development, 1979, 23(2): 149\u2013162","journal-title":"IBM Journal of Research and Development"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-025-50122-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11704-025-50122-8","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-025-50122-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T01:51:15Z","timestamp":1771552275000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11704-025-50122-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,20]]},"references-count":40,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2026,10]]}},"alternative-id":["50122"],"URL":"https:\/\/doi.org\/10.1007\/s11704-025-50122-8","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,20]]},"assertion":[{"value":"6 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests or financial conflicts to disclose.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"2010502"}}