Abstract
Shortest path algorithm is a foundation to various location-based services (LBS) and has been extensively studied in the literature. However, server-side shortest path calculation faces a severe scalability issue when the business expands and a huge amount of requests are submitted to the server simultaneously. Although a straightforward solution widely-adopted in current industry is to deploy more processing resources, in this work, we aim to improve the efficiency algorithmically by answering queries in a batch and reusing shareable computations. In particular, we generalize the goal-directed A* algorithm to correctly solve the batch processing problem with localized destinations. We further propose two decomposition algorithms to deal with scenarios where the destinations are sparse. Extensive evaluations on a real-world road network verify the superiority of our algorithm compared with state-of-the-art methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Goldberg, A.V., Harrelson, C.: Computing the shortest path: a search meets graph theory. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 156–165. Society for Industrial and Applied Mathematics (2005)
Geisberger, R., Sanders, P., Schultes, D., Delling, D.: Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 319–333. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-68552-4_24
Möhring, R.H., Schilling, H., Schütz, B., Wagner, D., Willhalm, T.: Partitioning graphs to speedup Dijkstra’s algorithm. J. Exp. Algorithm. (JEA) 11, 2–8 (2007)
Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338–1355 (2003)
Akiba, T., Iwata, Y., Yoshida, Y.: Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 349–360. ACM (2013)
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 the 2018 International Conference on Management of Data, pp. 709–724. ACM (2018)
Samet, H., Sankaranarayanan, J., Alborzi, H.: Scalable network distance browsing in spatial databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, pp. 43–54. ACM (2008)
Wang, S., Xiao, X., Yang, Y., Lin, W.: Effective indexing for approximate constrained shortest path queries on large road networks. Proc. VLDB Endow. 10(2), 61–72 (2016)
Wang, S., Lin, W., Yang, Y., Xiao, X., Zhou, S.: Efficient route planning on public transportation networks: a labelling approach. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 967–982. ACM (2015)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Cooke, K.L., Halsey, E.: The shortest route through a network with time-dependent internodal transit times. J. Math. Anal. Appl. 14(3), 493–498 (1966)
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)
Li, L., Hua, W., Du, X., Zhou, X.: Minimal on-road time route scheduling on time-dependent graphs. Proc. VLDB Endow. 10(11), 1274–1285 (2017)
Li, L., Zheng, K., Wang, S., Hua, W., Zhou, X.: Go slow to go fast: minimal on-road time route scheduling with parking facilities using historical trajectory. VLDB J. Int. J. Very Large Data Bases 27(3), 321–345 (2018)
Goldberg, A.V., Kaplan, H., Werneck, R.F.: Reach for a: efficient point-to-point shortest path algorithms. In: Proceedings of the Meeting on Algorithm Engineering & Expermiments, pp. 129–143. Society for Industrial and Applied Mathematics (2006)
Wagner, D., Willhalm, T., Zaroliagis, C.: Geometric containers for efficient shortest-path computation. J. Exp. Algorithm. (JEA) 10, 1–3 (2005)
Fu, A.W.-C., Wu, H., Cheng, J., Wong, R.C.-W.: IS-LABEL: an independent-set based labeling scheme for point-to-point distance querying. Proc. VLDB Endow. 6(6), 457–468 (2013)
Li, Y., Yiu, M.L., Kou, N.M., et al.: An experimental study on hub labeling based shortest path algorithms. Proc. VLDB Endow. 11(4), 445–457 (2017)
Jiang, M., Fu, A.W.-C., Wong, R.C.-W., Xu, Y.: Hop doubling label indexing for point-to-point distance querying on scale-free networks. Proc. VLDB Endow. 7(12), 1203–1214 (2014)
Sankaranarayanan, J., Alborzi, H., Samet, H.: Efficient query processing on spatial networks. In: Proceedings of the 13th Annual ACM International Workshop on Geographic Information Systems, pp. 200–209. ACM (2005)
Qi, Z., Xiao, Y., Shao, B., Wang, H.: Toward a distance oracle for billion-node graphs. Proc. VLDB Endow. 7(1), 61–72 (2013)
Reza, R.M., Ali, M.E., Hashem, T.: Group processing of simultaneous shortest path queries in road networks. In: 2015 16th IEEE International Conference on Mobile Data Management (MDM), vol. 1, pp. 128–133. IEEE (2015)
Mahmud, H., Amin, A.M., Ali, M.E., Hashem, T., Nutanong, S.: A group based approach for path queries in road networks. In: Nascimento, M.A., et al. (eds.) SSTD 2013. LNCS, vol. 8098, pp. 367–385. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40235-7_21
Acknowledgment
This research is partially supported by the Australian Research Council (Grants No. DP150103008 and DP170101172).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhang, M., Li, L., Hua, W., Zhou, X. (2019). Batch Processing of Shortest Path Queries in Road Networks. In: Chang, L., Gan, J., Cao, X. (eds) Databases Theory and Applications. ADC 2019. Lecture Notes in Computer Science(), vol 11393. Springer, Cham. https://doi.org/10.1007/978-3-030-12079-5_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-12079-5_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-12078-8
Online ISBN: 978-3-030-12079-5
eBook Packages: Computer ScienceComputer Science (R0)