Label-constrained shortest path query processing on road networks

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)