{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,28]],"date-time":"2026-08-28T16:42:16Z","timestamp":1787935336045,"version":"build-2784847793"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,12,16]],"date-time":"2023-12-16T00:00:00Z","timestamp":1702684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,16]],"date-time":"2023-12-16T00:00:00Z","timestamp":1702684800000},"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":[[2024,5]]},"DOI":"10.1007\/s00778-023-00825-w","type":"journal-article","created":{"date-parts":[[2023,12,16]],"date-time":"2023-12-16T10:02:10Z","timestamp":1702720930000},"page":"569-593","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Label-constrained shortest path query processing on road networks"],"prefix":"10.1007","volume":"33","author":[{"given":"Junhua","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9896-0805","authenticated-orcid":false,"given":"Long","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wentao","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,12,16]]},"reference":[{"key":"825_CR1","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: Proceedings ALENEX, pp. 147\u2013154. SIAM (2014)","DOI":"10.1137\/1.9781611973198.14"},{"issue":"2","key":"825_CR2","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. Algebraic Discret. Methods 8(2), 277\u2013284 (1987)","journal-title":"SIAM J. Algebraic Discret. Methods"},{"key":"825_CR3","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\u2014Selected Results and Surveys, vol. 9220, pp. 19\u201380 (2016)","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"825_CR4","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Panario, D., Viola, A. (eds.) Proceedings of LATIN 2000: Theoretical Informatics, vol. 1776, pp. 88\u201394 (2000)","DOI":"10.1007\/10719839_9"},{"key":"825_CR5","unstructured":"Bonchi, F., Gionis, A., Gullo, F., Ukkonen, A.: Distance oracles in edge-labeled graphs. In: Proceedings of EDBT, pp. 547\u2013558 (2014)"},{"issue":"6","key":"825_CR6","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":"825_CR7","doi-asserted-by":"crossref","unstructured":"Chen, Z., Yuan, L., Lin, X., Qin, L., Yang, J.: Efficient maximal balanced clique enumeration in signed networks. In: Proceedings of The Web Conference 2020, pp. 339\u2013349 (2020)","DOI":"10.1145\/3366423.3380119"},{"issue":"8","key":"825_CR8","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":"825_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2886843","volume":"21","author":"J Dibbelt","year":"2016","unstructured":"Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. J. Exp. Algorithmics (JEA) 21, 1\u201349 (2016)","journal-title":"J. Exp. Algorithmics (JEA)"},{"key":"825_CR10","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E Djikstra","year":"1959","unstructured":"Djikstra, E.: A note on two problems in connection with graphs. Numer. Math. 1, 269\u2013271 (1959)","journal-title":"Numer. Math."},{"issue":"3","key":"825_CR11","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1287\/opre.17.3.395","volume":"17","author":"SE Dreyfus","year":"1969","unstructured":"Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395\u2013412 (1969)","journal-title":"Oper. Res."},{"key":"825_CR12","doi-asserted-by":"crossref","unstructured":"Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: Proceedings of WEA, pp. 319\u2013333 (2008)","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"825_CR13","unstructured":"Goldberg, A.V., Harrelson, C.: Computing the shortest path: a search meets graph theory. In: Proceedings of SODA, pp. 156\u2013165 (2005)"},{"key":"825_CR14","doi-asserted-by":"crossref","unstructured":"Greco, S., Molinaro, C., Pulice, C.: Efficient maintenance of all-pairs shortest distances. In: Proceedings of International Conference on Scientific and Statistical Database Management, pp. 1\u201312 (2016)","DOI":"10.1145\/2949689.2949713"},{"issue":"2","key":"825_CR15","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"825_CR16","doi-asserted-by":"crossref","unstructured":"Hassan, M.S., Aref, W.G., Aly, A.M.: Graph indexing for shortest-path finding over dynamic sub-graphs. In: Proceedings of SIGMOD, pp. 1183\u20131197 (2016)","DOI":"10.1145\/2882903.2882933"},{"key":"825_CR17","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 SIGMOD, pp. 123\u2013134 (2010)","DOI":"10.1145\/1807167.1807183"},{"issue":"5","key":"825_CR18","first-page":"1029","volume":"14","author":"S Jung","year":"2002","unstructured":"Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE TKDE 14(5), 1029\u20131046 (2002)","journal-title":"IEEE TKDE"},{"key":"825_CR19","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 Discret. Math. 8, 54\u201357 (2001)","journal-title":"Electron. Notes Discret. Math."},{"key":"825_CR20","doi-asserted-by":"crossref","unstructured":"Li, Y., George, S., Apfelbeck, C., Hendawi, A.M., Hazel, D., Teredesai, A., Ali, M.H.: Routing service with real world severe weather. In: Huang, Y., Schneider, M., Gertz, M., Krumm, J., Sankaranarayanan, J. (eds.) Proceedings of SIGSPATIAL, pp. 585\u2013588 (2014)","DOI":"10.1145\/2666310.2666375"},{"key":"825_CR21","doi-asserted-by":"crossref","unstructured":"Li, H., Ge, Y., Hong, R., Zhu, H.: Point-of-interest recommendations: learning potential check-ins from friends. In: Proceedings of SIGKDD, pp. 975\u2013984 (2016)","DOI":"10.1145\/2939672.2939767"},{"key":"825_CR22","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":"825_CR23","doi-asserted-by":"crossref","unstructured":"Li, W., Qiao, M., Qin, L., Zhang, Y., Chang, L., Lin, X.: Scaling up distance labeling on graphs with core-periphery properties. In: Proceedings of SIGMOD, pp. 1367\u20131381 (2020)","DOI":"10.1145\/3318464.3389748"},{"issue":"10","key":"825_CR24","doi-asserted-by":"publisher","first-page":"1010","DOI":"10.14778\/3115404.3115407","volume":"10","author":"Y Liu","year":"2017","unstructured":"Liu, Y., Pham, T., Cong, G., Yuan, Q.: An experimental evaluation of point-of-interest recommendation in location-based social networks. Proc. VLDB Endow. 10(10), 1010\u20131021 (2017)","journal-title":"Proc. VLDB Endow."},{"key":"825_CR25","doi-asserted-by":"crossref","unstructured":"Liu, B., Yuan, L., Lin, X., Qin, L., Zhang, W., Zhou, J.: Efficient ($$\\alpha $$, $$\\beta $$)-core computation: an index-based approach. In: The World Wide Web Conference, pp. 1130\u20131141 (2019)","DOI":"10.1145\/3308558.3313522"},{"issue":"5","key":"825_CR26","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1007\/s00778-020-00606-9","volume":"29","author":"B Liu","year":"2020","unstructured":"Liu, B., Yuan, L., Lin, X., Qin, L., Zhang, W., Zhou, J.: Efficient ($$\\alpha $$, $$\\beta $$)-core computation in bipartite graphs. VLDB J. 29(5), 1075\u20131099 (2020)","journal-title":"VLDB J."},{"key":"825_CR27","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: Proceedings of SIGMOD, pp. 709\u2013724. ACM (2018)","DOI":"10.1145\/3183713.3196913"},{"key":"825_CR28","doi-asserted-by":"crossref","unstructured":"Ouyang, D., Yuan, L., Zhang, F., Qin, L., Lin, X.: Towards efficient path skyline computation in bicriteria networks. In: International Conference on Database Systems for Advanced Applications, pp. 239\u2013254. Springer, Berlin (2018)","DOI":"10.1007\/978-3-319-91452-7_16"},{"issue":"5","key":"825_CR29","doi-asserted-by":"publisher","first-page":"602","DOI":"10.14778\/3377369.3377371","volume":"13","author":"D Ouyang","year":"2020","unstructured":"Ouyang, D., Yuan, L., Qin, L., Chang, L., Zhang, Y., Lin, X.: Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees. Proc. VLDB Endow. 13(5), 602\u2013615 (2020)","journal-title":"Proc. VLDB Endow."},{"issue":"6","key":"825_CR30","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":"2","key":"825_CR31","doi-asserted-by":"publisher","first-page":"69","DOI":"10.14778\/1921071.1921074","volume":"4","author":"MN Rice","year":"2010","unstructured":"Rice, M.N., Tsotras, V.J.: Graph indexing of road networks for shortest path queries with label restrictions. Proc. VLDB Endow. 4(2), 69\u201380 (2010)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"825_CR32","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"},{"issue":"3","key":"825_CR33","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"825_CR34","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Proceedings of ESA, pp. 568\u2013579 (2005)","DOI":"10.1007\/11561071_51"},{"key":"825_CR35","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 SIGMOD, pp. 345\u2013358 (2017)","DOI":"10.1145\/3035918.3035955"},{"key":"825_CR36","doi-asserted-by":"crossref","unstructured":"Wei, F.: TEDI: efficient shortest path query answering on graphs. In: Proceedings of SIGMOD, pp. 99\u2013110. ACM (2010)","DOI":"10.1145\/1807167.1807181"},{"issue":"5","key":"825_CR37","doi-asserted-by":"publisher","first-page":"406","DOI":"10.14778\/2140436.2140438","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. Proc. VLDB Endow. 5(5), 406\u2013417 (2012)","journal-title":"Proc. VLDB Endow."},{"key":"825_CR38","doi-asserted-by":"crossref","unstructured":"Wu, X., Yuan, L., Lin, X., Yang, S., Zhang, W.: Towards efficient k-tripeak decomposition on large graphs. In: International Conference on Database Systems for Advanced Applications, pp. 604\u2013621. Springer, Berlin (2019)","DOI":"10.1007\/978-3-030-18576-3_36"},{"key":"825_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-50367-6","volume-title":"GPS: Theory, Algorithms and Applications","author":"G Xu","year":"2016","unstructured":"Xu, G., Xu, Y.: GPS: Theory, Algorithms and Applications. Springer, Berlin (2016)"},{"key":"825_CR40","doi-asserted-by":"crossref","unstructured":"Xu, J., Jiao, F., Berger, B.: A tree-decomposition approach to protein structure prediction. In: Proceedings of CSB, pp. 247\u2013256. IEEE (2005)","DOI":"10.1109\/CSB.2005.9"},{"issue":"2","key":"825_CR41","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00778-015-0408-z","volume":"25","author":"L Yuan","year":"2016","unstructured":"Yuan, L., Qin, L., Lin, X., Chang, L., Zhang, W.: Diversified top-k clique search. VLDB J. 25(2), 171\u2013196 (2016)","journal-title":"VLDB J."},{"issue":"3","key":"825_CR42","doi-asserted-by":"publisher","first-page":"338","DOI":"10.14778\/3157794.3157802","volume":"11","author":"L Yuan","year":"2017","unstructured":"Yuan, L., Qin, L., Lin, X., Chang, L., Zhang, W.: Effective and efficient dynamic graph coloring. Proc. VLDB Endow. 11(3), 338\u2013351 (2017)","journal-title":"Proc. VLDB Endow."},{"issue":"5","key":"825_CR43","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1109\/TKDE.2017.2783933","volume":"30","author":"L Yuan","year":"2017","unstructured":"Yuan, L., Qin, L., Zhang, W., Chang, L., Yang, J.: Index-based densest clique percolation community search in networks. IEEE Trans. Knowl. Data Eng. 30(5), 922\u2013935 (2017)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"5","key":"825_CR44","doi-asserted-by":"publisher","first-page":"488","DOI":"10.14778\/3303753.3303756","volume":"12","author":"X Zhang","year":"2019","unstructured":"Zhang, X., \u00d6zsu, M.T.: Correlation constraint shortest path over large multi-relation graphs. Proc. VLDB Endow. 12(5), 488\u2013501 (2019)","journal-title":"Proc. VLDB Endow."},{"key":"825_CR45","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Yu, J.X.: Relative subboundedness of contraction hierarchy and hierarchical 2-hop index in dynamic road networks. In: Ives, Z., Bonifati, A., Abbadi, A.E. (eds.) SIGMOD, pp. 1992\u20132005. ACM (2022)","DOI":"10.1145\/3514221.3517875"},{"key":"825_CR46","doi-asserted-by":"crossref","unstructured":"Zhang, M., Li, L., Hua, W., Zhou, X.: Efficient 2-hop labeling maintenance in dynamic small-world networks. In: ICDE, pp. 133\u2013144 (2021)","DOI":"10.1109\/ICDE51399.2021.00019"},{"issue":"3","key":"825_CR47","doi-asserted-by":"publisher","first-page":"686","DOI":"10.14778\/3494124.3494148","volume":"15","author":"J Zhang","year":"2022","unstructured":"Zhang, J., Yuan, L., Li, W., Qin, L., Zhang, Y.: Efficient label-constrained shortest path queries on road networks: a tree decomposition approach. Proc. VLDB Endow. 15(3), 686\u2013698 (2022)","journal-title":"Proc. VLDB Endow."},{"key":"825_CR48","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: Proceedings of SIGMOD, pp. 857\u2013868 (2013)","DOI":"10.1145\/2463676.2465277"},{"key":"825_CR49","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.is.2013.10.003","volume":"40","author":"L Zou","year":"2014","unstructured":"Zou, L., Xu, K., Yu, J.X., Chen, L., Xiao, Y., Zhao, D.: Efficient processing of label-constraint reachability queries in large graphs. Inf. Syst. 40, 47\u201366 (2014)","journal-title":"Inf. Syst."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00825-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-023-00825-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00825-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,23]],"date-time":"2024-04-23T07:04:41Z","timestamp":1713855881000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-023-00825-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,16]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["825"],"URL":"https:\/\/doi.org\/10.1007\/s00778-023-00825-w","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,16]]},"assertion":[{"value":"12 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}