Abstract
Computing the shortest path between two vertices is a fundamental problem in road networks. Most of the existing works assume that the edges in the road networks have no labels, but in many real applications, the edges have labels and label constraints may be placed on the edges appearing on a valid shortest path. Hence, we study the label-constrained shortest path queries in this paper. In order to process such queries efficiently, we adopt an index-based approach and propose a novel index structure, \(\textsf{LSD}\)-\(\textsf{Index}\), based on tree decomposition. With \(\textsf{LSD}\)-\(\textsf{Index}\), we design efficient query processing and index construction algorithms with good performance guarantees. Moreover, due to the dynamic properties of real-world networks, we also devise index maintenance algorithms that can maintain the index efficiently. To evaluate the performance of proposed methods, we conduct extensive experimental studies using large real road networks including the whole USA road network. Compared with the state-of-the-art approach, the experimental results demonstrate that our algorithm not only achieves up to two orders of magnitude speedup in query processing time but also consumes much less index space. Meanwhile, the experimental results also show that the index can also be efficiently constructed and maintained for dynamic graphs.
Similar content being viewed by others
References
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–154. SIAM (2014)
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM J. Algebraic Discret. Methods 8(2), 277–284 (1987)
Bast, H., Delling, D., Goldberg, A.V., Müller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., Werneck, R.F.: Route planning in transportation networks. In: Algorithm Engineering—Selected Results and Surveys, vol. 9220, pp. 19–80 (2016)
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–94 (2000)
Bonchi, F., Gionis, A., Gullo, F., Ukkonen, A.: Distance oracles in edge-labeled graphs. In: Proceedings of EDBT, pp. 547–558 (2014)
Chang, L., Yu, J.X., Qin, L., Cheng, H., Qiao, M.: The exact distance to destination in undirected world. VLDB J. 21(6), 869–888 (2012)
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–349 (2020)
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–1657 (2022)
Dibbelt, J., Strasser, B., Wagner, D.: Customizable contraction hierarchies. J. Exp. Algorithmics (JEA) 21, 1–49 (2016)
Djikstra, E.: A note on two problems in connection with graphs. Numer. Math. 1, 269–271 (1959)
Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395–412 (1969)
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: Proceedings of WEA, pp. 319–333 (2008)
Goldberg, A.V., Harrelson, C.: Computing the shortest path: a search meets graph theory. In: Proceedings of SODA, pp. 156–165 (2005)
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–12 (2016)
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–107 (1968)
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–1197 (2016)
Jin, R., Hong, H., Wang, H., Ruan, N., Xiang, Y.: Computing label-constraint reachability in graph databases. In: Proceedings of SIGMOD, pp. 123–134 (2010)
Jung, S., Pramanik, S.: An efficient path computation model for hierarchically structured topographical road maps. IEEE TKDE 14(5), 1029–1046 (2002)
Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: computational experiments. Electron. Notes Discret. Math. 8, 54–57 (2001)
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–588 (2014)
Li, H., Ge, Y., Hong, R., Zhu, H.: Point-of-interest recommendations: learning potential check-ins from friends. In: Proceedings of SIGKDD, pp. 975–984 (2016)
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–457 (2017)
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–1381 (2020)
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–1021 (2017)
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–1141 (2019)
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–1099 (2020)
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–724. ACM (2018)
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–254. Springer, Berlin (2018)
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–615 (2020)
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–825 (2020)
Rice, M.N., Tsotras, V.J.: Graph indexing of road networks for shortest path queries with label restrictions. Proc. VLDB Endow. 4(2), 69–80 (2010)
Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory Ser. B 36(1), 49–64 (1984)
Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309–322 (1986)
Sanders, P., Schultes, D.: Highway hierarchies hasten exact shortest path queries. In: Proceedings of ESA, pp. 568–579 (2005)
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–358 (2017)
Wei, F.: TEDI: efficient shortest path query answering on graphs. In: Proceedings of SIGMOD, pp. 99–110. ACM (2010)
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–417 (2012)
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–621. Springer, Berlin (2019)
Xu, G., Xu, Y.: GPS: Theory, Algorithms and Applications. Springer, Berlin (2016)
Xu, J., Jiao, F., Berger, B.: A tree-decomposition approach to protein structure prediction. In: Proceedings of CSB, pp. 247–256. IEEE (2005)
Yuan, L., Qin, L., Lin, X., Chang, L., Zhang, W.: Diversified top-k clique search. VLDB J. 25(2), 171–196 (2016)
Yuan, L., Qin, L., Lin, X., Chang, L., Zhang, W.: Effective and efficient dynamic graph coloring. Proc. VLDB Endow. 11(3), 338–351 (2017)
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–935 (2017)
Zhang, X., Özsu, M.T.: Correlation constraint shortest path over large multi-relation graphs. Proc. VLDB Endow. 12(5), 488–501 (2019)
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–2005. ACM (2022)
Zhang, M., Li, L., Hua, W., Zhou, X.: Efficient 2-hop labeling maintenance in dynamic small-world networks. In: ICDE, pp. 133–144 (2021)
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–698 (2022)
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–868 (2013)
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–66 (2014)
Acknowledgements
Long Yuan is supported by National Key RD Program of China 2022YFF0712100, NSFC61902184 and Science and Technology on Information Systems Engineering Laboratory WDZC20205250411.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zhang, J., Yuan, L., Li, W. et al. Label-constrained shortest path query processing on road networks. The VLDB Journal 33, 569–593 (2024). https://doi.org/10.1007/s00778-023-00825-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-023-00825-w