Abstract
Real-world road-planning applications often result in the formulation of new variations of the nearest neighbor (NN) problem requiring new solutions. In this paper, we study an unexplored form of NN queries named optimal sequenced route (OSR) query in both vector and metric spaces. OSR strives to find a route of minimum length starting from a given source location and passing through a number of typed locations in a particular order imposed on the types of the locations. We first transform the OSR problem into a shortest path problem on a large planar graph. We show that a classic shortest path algorithm such as Dijkstra’s is impractical for most real-world scenarios. Therefore, we propose LORD, a light threshold-based iterative algorithm, which utilizes various thresholds to prune the locations that cannot belong to the optimal route. Then we propose R-LORD, an extension of LORD which uses R-tree to examine the threshold values more efficiently. Finally, for applications that cannot tolerate the Euclidean distance as estimation and require exact distance measures in metric spaces (e.g., road networks) we propose PNE that progressively issues NN queries on different point types to construct the optimal route for the OSR query. Our extensive experiments on both real-world and synthetic datasets verify that our algorithms significantly outperform a disk-based variation of the Dijkstra approach in terms of processing time (up to two orders of magnitude) and required workspace (up to 90% reduction on average).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Ascheuer N., Jünger M. and Reinelt G. (2000). A branch and cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Comput. Optim. Appl. 17(1): 61–84
Biggs N., Lloyd E.K. and Wilson R.J. (1986). Graph theory. Clarendon Press, Oxford, 1736–1936
Chan, E.P.F., Zhang, N.: Finding shortest paths in large network systems. In: Proceedings of the 9th ACM international symposium on Advances in geographic information systems, pp. 160–166. ACM Press (2001).http://www.doi.acm.org/10.1145/512161.512197
Cormen T.H., Leiserson C.E. and Rivest R.L. (1990). Introduction to algorithms. MIT Press/McGraw-Hill, New York
Hadjieleftheriou, M., Kollios, G., Bakalov, P., Tsotras, V.J.: Complex spatio-temporal pattern queries. In: Böhm, K., Jensen, C.S., Haas, L.M., Kersten, M.L., Larson, P.Å., Ooi, B.C. (eds.) Proceedings of the 31st International Conference on Very Large Data Bases: VLDB’05, pp. 877–888 (2005)
Hjaltason,G.R., Samet,H.: Distance browsing in spatial databases. ACM Trans. Database Syst.24(2), 265–318 (1999). http://www.doi.acm.org/10.1145/320248.320255
Hutchinson, D., Maheshwari, A., Zeh, N.: An external memory data structure for shortest path queries. Discret. Appl. Math. 126(1), 55–82 (2003). http://www.dx.doi. org/10.1016/S0166-218X(02)00217-2
Jensen, C.S., Kolář, J., Pedersen, T.B., Timko, I.: Nearest neighbor queries in road networks. In: Proceedings of the 11th ACM international symposium on Advances in geographic information systems, pp. 1–8. ACM Press (2003).http://www.doi.acm.org/10.1145/956676.956677
Kolahdouzan, M.R., Shahabi, C.: Voronoi-based K nearest neighbor search for spatial network databases. In: Nascimento, M.A., Özsu, M.T., Kossmann, D., Miller, R.J., Blakeley, J.A., Schiefer, K.B. (eds.) Proceedings of the 30th International Conference on Very Large Data Bases: VLDB’04, pp. 840–851 (2004)
Li, F., Cheng, D., Hadjieleftheriou, M., Kollios, G., Teng, S.H.: On trip planning queries in spatial databases. In: , C.B., Egenhofer, M., Bertino E. (eds.) Proceedings of the 9th International Symposium on Spatial and Temporal Databases: SSTD’05. Lecture Notes in Computer Science, vol. 3633, pp. 273–290. Springer, Berlin Heidelberg New York (2005)
Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query processing in spatial network databases. In: Freytag, J.C., Lockemann, P.C., Abiteboul, S., Carey, M.J., Selinger, P.G., Heuer, A. (eds.) Proceedings of the 29th International Conference on Very Large Data Bases: VLDB’03, pp. 802–813 (2003)
Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 22-25, 1995, pp. 71–79. ACM Press (1995)
Tao, Y., Zhang, J., Papadias, D., Mamoulis, N.: An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces. IEEE Trans. Knowl. Data Eng. 16(10), 1169–1184 (2004). http://www.dx.doi.org/10.1109/TKDE.2004.48
Terrovitis, M., Bakiras, S., Papadias, D., Mouratidis, K.: Constrained shortest path computation. In: Medeiros, C.B., Egenhofer, M., Bertino E. (eds.) Proceedings of the 9th International Symposium on Spatial and Temporal Databases: SSTD’05. Lecture Notes in Computer Science, vol. 3633, pp. 181–199. Springer, Berlin Heidelberg New York (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sharifzadeh, M., Kolahdouzan, M. & Shahabi, C. The optimal sequenced route query. The VLDB Journal 17, 765–787 (2008). https://doi.org/10.1007/s00778-006-0038-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-006-0038-6