{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:57Z","timestamp":1781326737456,"version":"3.54.1"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No. 62502105, No. 62572140, No. U2436208, No. 62372129"],"award-info":[{"award-number":["No. 62502105, No. 62572140, No. U2436208, No. 62372129"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Guangdong S&T Program","award":["2024B0101010002"],"award-info":[{"award-number":["2024B0101010002"]}]},{"name":"Project of Guangdong Key Laboratory of Industrial Control System Security","award":["2024B1212020010"],"award-info":[{"award-number":["2024B1212020010"]}]},{"DOI":"10.13039\/501100021171","name":"Guangdong Basic and Applied Basic Research Foundation","doi-asserted-by":"crossref","award":["No. 2023A1515110592"],"award-info":[{"award-number":["No. 2023A1515110592"]}],"id":[{"id":"10.13039\/501100021171","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Science and Technology Guangzhou Education Department Foundation","award":["No. 2023KQNCX057"],"award-info":[{"award-number":["No. 2023KQNCX057"]}]},{"name":"National Key-Area Research and Development Program","award":["2022YFB2702300, YS2022YFB2700093"],"award-info":[{"award-number":["2022YFB2702300, YS2022YFB2700093"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>With the increasing complexity of urban transportation systems and the growing demand for dynamic, real-time responsiveness, Time-Dependent Minimum Travel Time Queries (TD-MTTQs) in time-dependent road networks have become a core challenge in intelligent transportation system research. To address the trade-offs between preprocessing complexity and query efficiency in existing index-based methods for large-scale road network applications, this paper proposes a 4-hop index method, TD-TNR-CH. The core methodology involves establishing local indexes from each node to its nearest critical nodes (named transit nodes) through strategic critical node selection, while simultaneously constructing query tables associated with candidate sets between these critical nodes. This architecture enables rapid computation of medium-to-long distance queries through efficient index lookups, while ensuring high responsiveness for short-distance queries via TCH-based local searches. Extensive experimental results on large-scale real-world road networks demonstrate that our method exhibits superior scalability, achieving query efficiency of up to 103 times that of the fastest existing algorithms. Furthermore, it shows exceptional stability across queries of varying distances. Additionally, leveraging its parallelized architecture, TD-TNR-CH requires only approximately 30 minutes of preprocessing time for large-scale networks, significantly outperforming comparable methods in terms of preprocessing efficiency.<\/jats:p>","DOI":"10.1145\/3769801","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Hops Can be Constrained: Efficient Distance Queries on Large Time-Dependent Road Networks"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9346-8267","authenticated-orcid":false,"given":"Weihao","family":"Yu","sequence":"first","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9472-4389","authenticated-orcid":false,"given":"Dian","family":"Ouyang","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0548-0130","authenticated-orcid":false,"given":"Fan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6339-0219","authenticated-orcid":false,"given":"Xiang","family":"Zhao","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2744-3584","authenticated-orcid":false,"given":"Shen","family":"Su","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2396-7225","authenticated-orcid":false,"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9409-5359","authenticated-orcid":false,"given":"Zhihong","family":"Tian","sequence":"additional","affiliation":[{"name":"Guangzhou University, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38527-8_7"},{"key":"e_1_2_1_3_1","volume-title":"Route planning in transportation networks. Algorithm engineering: Selected results and surveys","author":"Bast Hannah","year":"2016","unstructured":"Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias M\u00fcller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F Werneck. 2016. Route planning in transportation networks. Algorithm engineering: Selected results and surveys (2016), 19-80."},{"key":"e_1_2_1_4_1","volume-title":"9th DIMACS Implementation Challenge [1]","author":"Bast Holger","year":"2006","unstructured":"Holger Bast, Stefan Funke, and Domagoj Matijevic. 2006. Transit ultrafast shortest-path queries with linear-time preprocessing. 9th DIMACS Implementation Challenge [1] (2006), 19."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.5"},{"key":"e_1_2_1_6_1","first-page":"566","volume-title":"Science","volume":"316","author":"Bast Holger","year":"2007","unstructured":"Holger Bast, Stefan Funke, Peter Sanders, and Dominik Schultes. 2007b. Fast routing in road networks with transit nodes. Science, Vol. 316, 5824 (2007), 566-566."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972894.10"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_15"},{"key":"e_1_2_1_9_1","unstructured":"Gernot Veit Batz Robert Geisberger and Peter Sanders. 2008. Time Dependent Contraction Hierarchies-Basic Algorithmic Ideas. Technical Report. Citeseer."},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Minimum time-dependent travel times with contraction hierarchies","volume":"18","author":"Batz G Veit","year":"2013","unstructured":"G Veit Batz, Robert Geisberger, Peter Sanders, and Christian Vetter. 2013. Minimum time-dependent travel times with contraction hierarchies. Journal of Experimental Algorithmics (JEA), Vol. 18 (2013), 1-1.","journal-title":"Journal of Experimental Algorithmics (JEA)"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00035"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(66)90009-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00161"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9461-6"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22922-0_7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Edsger W Dijkstra. 2022. A note on two problems in connexion with graphs. In Edsger Wybe Dijkstra: his life work and legacy. 287-290.","DOI":"10.1145\/3544585.3544600"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353371"},{"key":"e_1_2_1_19_1","volume-title":"An appraisal of some shortest-path algorithms. Operations research","author":"Dreyfus Stuart E","year":"1969","unstructured":"Stuart E Dreyfus. 1969. An appraisal of some shortest-path algorithms. Operations research, Vol. 17, 3 (1969), 395-412."},{"key":"e_1_2_1_20_1","volume-title":"McKay","author":"Farhan Muhammad","year":"2019","unstructured":"Muhammad Farhan, Qing Wang, Yu Lin, and Brendan D. McKay. 2019. A Highly Scalable Labelling Approach for Exact Distance Queries in Complex Networks. (2019), 13-24."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19094-0_4"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"e_1_2_1_23_1","first-page":"156","volume-title":"SODA","volume":"5","author":"Goldberg Andrew V","year":"2005","unstructured":"Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory. In SODA, Vol. 5. 156-165."},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Andrew V Goldberg Haim Kaplan and Renato F Werneck. 2006. Reach for A*: Shortest Path Algorithms with Preprocessing. In The shortest path problem. 93-139.","DOI":"10.1090\/dimacs\/074\/05"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00345"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-016-0030-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.71"},{"key":"e_1_2_1_28_1","first-page":"1","article-title":"Fastest paths in time-dependent networks for intelligent vehicle-highway systems application","volume":"1","author":"Kaufman David E","year":"1993","unstructured":"David E Kaufman and Robert L Smith. 1993. Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. Journal of Intelligent Transportation Systems, Vol. 1, 1 (1993), 1-11.","journal-title":"Journal of Intelligent Transportation Systems"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-022-01269-2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00758-w"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00085"},{"key":"e_1_2_1_32_1","first-page":"300","article-title":"Fastest path query answering using time-dependent hop-labeling in road network","volume":"34","author":"Li Lei","year":"2020","unstructured":"Lei Li, Sibo Wang, and Xiaofang Zhou. 2020. Fastest path query answering using time-dependent hop-labeling in road network. IEEE Transactions on Knowledge and Data Engineering, Vol. 34, 1 (2020), 300-313.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_34_1","first-page":"1210","article-title":"Td-h2h: Shortest path query on time-dependent graphs","volume":"17","author":"Li Xinling","year":"2023","unstructured":"Xinling Li, Yishu Wang, Ye Yuan, Xiang Gu, and Guoren Wang. 2023b. Td-h2h: Shortest path query on time-dependent graphs. Journal of Frontiers of Computer Science and Technology, Vol. 17, 5 (2023), 1210-1224.","journal-title":"Journal of Frontiers of Computer Science and Technology"},{"key":"e_1_2_1_35_1","volume-title":"International Conference on Algorithms and Architectures for Parallel Processing. Springer, 18-32","author":"Liao Linbo","year":"2021","unstructured":"Linbo Liao, Shipeng Yang, Yongxuan Lai, Wenhua Zeng, Fan Yang, and Min Jiang. 2021. Efficient estimation of time-dependent shortest paths based on shortcuts. In International Conference on Algorithms and Architectures for Parallel Processing. Springer, 18-32."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20438"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.214078"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-023-00789-x"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_51"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.115"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2760880"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00255"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-017-0044-2"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342265"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00034"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00115"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020462"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505749"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2399306"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769801","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:43:10Z","timestamp":1781325790000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769801"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769801"],"URL":"https:\/\/doi.org\/10.1145\/3769801","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}