{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T01:22:19Z","timestamp":1783646539145,"version":"3.55.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T00:00:00Z","timestamp":1678838400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T00:00:00Z","timestamp":1678838400000},"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":["The VLDB Journal"],"published-print":{"date-parts":[[2023,11]]},"DOI":"10.1007\/s00778-023-00789-x","type":"journal-article","created":{"date-parts":[[2023,3,15]],"date-time":"2023-03-15T05:34:08Z","timestamp":1678858448000},"page":"1263-1287","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["When hierarchy meets 2-hop-labeling: efficient shortest distance and path queries on road networks"],"prefix":"10.1007","volume":"32","author":[{"given":"Dian","family":"Ouyang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0903-1503","authenticated-orcid":false,"given":"Dong","family":"Wen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,3,15]]},"reference":[{"key":"789_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: A hub-based labeling algorithm for shortest paths in road networks. In Proc. of ISEA\u201911, pages 230\u2013241, (2011)","DOI":"10.1007\/978-3-642-20662-7_20"},{"key":"789_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Delling, D., Goldberg, A.V., Werneck, R.F.: Hierarchical hub labelings for shortest paths. In Proc. of ESA\u201912, pages 24\u201335, (2012)","DOI":"10.1007\/978-3-642-33090-2_4"},{"key":"789_CR3","doi-asserted-by":"crossref","unstructured":"Abraham, I., Fiat, A., Goldberg, A.V., Werneck, R.F.F.: Highway dimension, shortest paths, and provably efficient algorithms. In M.\u00a0Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 782\u2013793. SIAM, (2010)","DOI":"10.1137\/1.9781611973075.64"},{"key":"789_CR4","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Kawarabayashi, K.-i., Kawata, Y.: Fast shortest-path distance queries on road networks by pruned highway labeling. In Proc. of ALENEX\u201914, pages 147\u2013154, (2014)","DOI":"10.1137\/1.9781611973198.14"},{"issue":"2","key":"789_CR5","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algeb. Discret. Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algeb. Discret. Methods"},{"issue":"2","key":"789_CR6","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algeb. Discret. Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algeb. Discret. Methods"},{"key":"789_CR7","doi-asserted-by":"crossref","unstructured":"Arz, J., Luxen, D., Sanders, P.: Transit node routing reconsidered. In Proc. of SEA\u201913, pages 55\u201366, (2013)","DOI":"10.1007\/978-3-642-38527-8_7"},{"key":"789_CR8","doi-asserted-by":"crossref","unstructured":"Bast, H., Delling, D., Goldberg, A.V., M\u00fcller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route planning in transportation networks. In Algorithm Engineering - Selected Results and Surveys, pages 19\u201380. (2016)","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"789_CR9","unstructured":"Bast, H., Funke, S., Matijevi\u0107, D.: Transit: ultrafast shortest-path queries with linear-time preprocessing. In 9th DIMACS Implementation Challenge\u2014Shortest Path, (2006)"},{"key":"789_CR10","doi-asserted-by":"crossref","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In Proceedings of the Nine Workshop on Algorithm Engineering and Experiments, ALENEX 2007, New Orleans, Louisiana, USA, January 6, 2007. SIAM, (2007)","DOI":"10.1137\/1.9781611972870.5"},{"key":"789_CR11","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The lca problem revisited. In Proc. of LASTI\u201900, pages 88\u201394, (2000)","DOI":"10.1007\/10719839_9"},{"issue":"1\u20132","key":"789_CR12","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybern."},{"issue":"6","key":"789_CR13","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"789_CR14","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In Graph-Theoretic Concepts in Computer Science, pages 1\u201314, (2006)","DOI":"10.1007\/11917496_1"},{"issue":"6","key":"789_CR15","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1007\/s00778-012-0274-x","volume":"21","author":"L Chang","year":"2012","unstructured":"Chang, L., Yu, J.X., Qin, L., Cheng, H., Qiao, M.: The exact distance to destination in undirected world. VLDB J. 21(6), 869\u2013888 (2012)","journal-title":"VLDB J."},{"key":"789_CR16","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In D.\u00a0Eppstein, editor, Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA, pages 937\u2013946. ACM\/SIAM, (2002)"},{"issue":"4","key":"789_CR17","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/16M1067196","volume":"47","author":"AE Feldmann","year":"2018","unstructured":"Feldmann, A.E., Fung, W.S., K\u00f6nemann, J., Post, I.: A (1+$$\\epsilon $$)-embedding of low highway dimension graphs into bounded treewidth graphs. SIAM J. Comput. 47(4), 1667\u20131704 (2018)","journal-title":"SIAM J. Comput."},{"key":"789_CR18","doi-asserted-by":"crossref","unstructured":"Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proc. of WEA\u201908, pages 319\u2013333, (2008)","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"789_CR19","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the shortest path: A search meets graph theory. In Proc. of SODA\u201905, pages 156\u2013165, (2005)"},{"key":"789_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01917434","volume":"8","author":"R Halin","year":"1976","unstructured":"Halin, R.: S-functions for graphs. J. Geom. 8, 171\u2013186 (1976)","journal-title":"J. Geom."},{"issue":"5","key":"789_CR21","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1109\/TKDE.2002.1033772","volume":"14","author":"S Jung","year":"2002","unstructured":"Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans. Knowl. Data Eng. 14(5), 1029\u20131046 (2002)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"789_CR22","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/S1571-0653(05)80078-2","volume":"8","author":"AMCA Koster","year":"2001","unstructured":"Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. Electron. Notes Discrete Math. 8, 54\u201357 (2001)","journal-title":"Electron. Notes Discrete Math."},{"key":"789_CR23","doi-asserted-by":"crossref","unstructured":"Li, Y., U, L.H., Yiu, M.L., Kou, N.M.: An experimental study on hub labeling based shortest path algorithms. Proc. VLDB Endow., 11(4):445\u2013457, (2017)","DOI":"10.1145\/3186728.3164141"},{"key":"789_CR24","doi-asserted-by":"crossref","unstructured":"Mozes, S., Sommer, C.: Exact distance oracles for planar graphs. In Proc. of SODA\u201912, pages 209\u2013222, (2012)","DOI":"10.1137\/1.9781611973099.19"},{"key":"789_CR25","doi-asserted-by":"crossref","unstructured":"Ouyang, D., Qin, L., Chang, L., Lin, X., Zhang, Y., Zhu, Q.: When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks. In SIGMOD, pages 709\u2013724, (2018)","DOI":"10.1145\/3183713.3196913"},{"issue":"1","key":"789_CR26","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors iii: Planar tree-width. J. Comb. Theory, Ser. B 36(1), 49\u201364 (1984)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"789_CR27","doi-asserted-by":"crossref","unstructured":"Samet, H., Sankaranarayanan, J., Alborzi, H.: Scalable network distance browsing in spatial databases. In Proc. of SIGMOD\u201908, pages 43\u201354, (2008)","DOI":"10.1145\/1376616.1376623"},{"key":"789_CR28","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In Proc. of ESA\u201905, pages 568\u2013579, (2005)","DOI":"10.1007\/11561071_51"},{"issue":"8","key":"789_CR29","doi-asserted-by":"publisher","first-page":"1158","DOI":"10.1109\/TKDE.2010.75","volume":"22","author":"J Sankaranarayanan","year":"2010","unstructured":"Sankaranarayanan, J., Samet, H.: Query processing using distance oracles for spatial networks. IEEE Trans. Knowl. Data Eng. 22(8), 1158\u20131175 (2010)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"1","key":"789_CR30","first-page":"1210","volume":"2","author":"J Sankaranarayanan","year":"2009","unstructured":"Sankaranarayanan, J., Samet, H., Alborzi, H.: Path oracles for spatial networks. PVLDB 2(1), 1210\u20131221 (2009)","journal-title":"PVLDB"},{"issue":"5","key":"789_CR31","first-page":"406","volume":"5","author":"L Wu","year":"2012","unstructured":"Wu, L., Xiao, X., Deng, D., Cong, G., Zhu, A.D., Zhou, S.: Shortest path and distance queries on road networks: an experimental evaluation. PVLDB 5(5), 406\u2013417 (2012)","journal-title":"PVLDB"},{"key":"789_CR32","doi-asserted-by":"crossref","unstructured":"Zhu, A.D., Ma, H., Xiao, X., Luo, S., Tang, Y., Zhou, S.: Shortest path and distance queries on road networks: Towards bridging theory and practice. In Proc. of SIGMOD\u201913, pages 857\u2013868, (2013)","DOI":"10.1145\/2463676.2465277"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00789-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-023-00789-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00789-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T10:08:15Z","timestamp":1697796495000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-023-00789-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,15]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["789"],"URL":"https:\/\/doi.org\/10.1007\/s00778-023-00789-x","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,15]]},"assertion":[{"value":"10 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 December 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}