Abstract
The advancement of mobile technologies and map-based applications enables a user to access a wide variety of location-based services that range from information queries to navigation systems. Due to the popularity of map-based applications among the users, the service provider often requires to answer a large number of simultaneous (or contemporary) queries. Thus, processing queries efficiently on spatial networks (i.e., road networks) have become an important research area in recent years. In this paper, we focus on path queries that find the shortest path between a source and a destination of the user. In particular, we address the problem of finding the shortest paths for a large number of simultaneous path queries in road networks. Traditional systems that consider one query at a time are not suitable for many applications due to high computational and service cost overhead. We propose an efficient group based approach that provides a practical solution with reduced cost. The key concept of our approach is to group queries that share a common travel path and then compute the shortest path for the group. Experimental results show the effectiveness and efficiency of our group based approach.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Google maps/google earth apis terms of service, http://code.google.com/apis/maps/terms.htm
Ali, M.E., Tanin, E., Zhang, R., Kulik, L.: A motion-aware approach for efficient evaluation of continuous queries on 3d object databases. VLDB J. 19(5), 603–632 (2010)
Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In: ALENEX (2007)
BingMaps, http://www.bing.com/maps/
Bullen, P.S.: Handbook of means and their inequalities (1987)
Delling, D., Goldberg, A.V., Werneck, R.F.F.: Faster batched shortest paths in road networks. In: ATMOS, pp. 52–63 (2011)
Delling, D., Wagner, D.: Landmark-based routing in dynamic graphs. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 52–65. Springer, Heidelberg (2007)
Demiryurek, U., Banaei-Kashani, F., Shahabi, C.: Efficient K-nearest neighbor search in time-dependent spatial networks. In: Bringas, P.G., Hameurlain, A., Quirchmayr, G. (eds.) DEXA 2010, Part I. LNCS, vol. 6261, pp. 432–449. Springer, Heidelberg (2010)
Giannikis, G., Alonso, G., Kossmann, D.: Shareddb: Killing one thousand queries with one stone. PVLDB 5(6), 526–537 (2012)
Lee, J.G., Han, J.: Trajectory clustering: A partition-and-group framework. In: SIGMOD, pp. 593–604 (2007)
Goldberg, A.V., Harrelson, C.: Computing the shortest path: A search meets graph theory. In: SODA, pp. 156–165 (2005)
Goldberg, A.V., Kaplan, H., Werneck3, R.F.: Efficient point-to-point shortest path algorithms. Tech. Report (2005)
GoogleMaps, http://maps.google.com
Gunturi, V.M.V., Nunes, E., Yang, K., Shekhar, S.: A critical-time-point approach to all-start-time lagrangian shortest paths: A summary of results. In: Pfoser, D., Tao, Y., Mouratidis, K., Nascimento, M.A., Mokbel, M., Shekhar, S., Huang, Y. (eds.) SSTD 2011. LNCS, vol. 6849, pp. 74–91. Springer, Heidelberg (2011)
Koenig, S., Likhachev, M., Furcy, D.: Lifelong planning A*. Artificial Intelligence 155, 93–146 (1968)
Levandoski, J.J., Mokbel, M.F., Khalefa, M.E.: Preference query evaluation over expensive attributes. In: CIKM, pp. 319–328 (2010)
Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., Thrun, S.: Anytime dynamic A*: An anytime, replanning algorithm. In: ICAPS (2005)
Mahmud, H., Amin, A.M., Ali, M.E., Hashem, T.: Shared execution of path queries on road networks. CoRR, abs/1210.6746 (2012)
Malviya, N., Madden, S., Bhattacharya, A.: A continuous query system for dynamic route planning. In: ICDE, pp. 792–803 (2011)
MapQuest, http://www.mapquest.com
Nilson, N.J., Hart, P.E.: A formal basis of the heuristic determination of minimum cost paths 4(2), 100–107 (1968)
Russell, S., Norvig, P.: Artificial Intelligence a modern approach, 2nd edn. (2006)
Samet, H., Sankaranarayanan, J., Alborzi, H.: Scalable network distance browsing in spatial databases. In: SIGMOD, pp. 43–54 (2008)
Sankaranarayanan, J., Samet, H., Alborzi, H.: Path oracles for spatial networks. PVLDB 2(1), 1210–1221 (2009)
Schultes, D., Sanders, P.: Dynamic highway-node routing. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol. 4525, pp. 66–79. Springer, Heidelberg (2007)
Terrovitis, M., Bakiras, S., Papadias, D., Mouratidis, K.: Constrained shortest path computation. In: Medeiros, C.B., Egenhofer, M., Bertino, E. (eds.) SSTD 2005. LNCS, vol. 3633, pp. 181–199. Springer, Heidelberg (2005)
Terrovitis, M., Bakiras, S., Papadia, D., Mouratidis, K.: Shortest path and distance queries on road networks: An experimental evaluation. In: PVLDB, pp. 406–417 (2012)
Thomsen, J.R., Yiu, M.L., Jensen, C.S.: Effective caching of shortest paths for location-based services. In: SIGMOD, pp. 313–324 (2012)
Zhang, D., Chow, C.-Y., Li, Q., Zhang, X., Xu, Y.: SMashQ: spatial mashup framework for k-nn queries in time-dependent road networks. Distributed and Parallel Databases, 259–287 (2013)
Zwick, U.: Exact and approximate distances in graphs - A survey. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 33–48. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mahmud, H., Amin, A.M., Ali, M.E., Hashem, T., Nutanong, S. (2013). A Group Based Approach for Path Queries in Road Networks. In: Nascimento, M.A., et al. Advances in Spatial and Temporal Databases. SSTD 2013. Lecture Notes in Computer Science, vol 8098. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40235-7_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-40235-7_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40234-0
Online ISBN: 978-3-642-40235-7
eBook Packages: Computer ScienceComputer Science (R0)