Shuo Shang
Ke Deng
ABSTRACT
A point detour is a temporary deviation from a user preferred path P (not necessarily a shortest network path) for visiting a data point such as a supermarket or McDonald's. The goodness of a point detour can be measured by the additional traveling introduced, called point detour cost or simply detour cost. Given a preferred path to be traveling on, Best Point Detour (BPD) query aims to identify the point detour with the minimum detour cost. This problem can be frequently found in our daily life but is less studied. In this work, the efficient processing of BPD query is investigated with support of devised optimization techniques. Furthermore, we investigate continuous-BPD query with target at the scenario where the path to be traveling on continuously changes when a user is moving to the destination along the preferred path. The challenge of continuous-BPD query lies in finding a set of update locations which split P into partitions. In the same partition, the user has the same BPD. We process continuous-BPD query by running BPD queries in a deliberately planned strategy. The efficiency study reveals that the number of BPD queries executed is optimal. The efficiency of BPD query and continuous-BPD query processing has been verified by extensive experiments.
- Z. Chen, H. T. Shen, X. Zhou, and J. X. Yu. Monitoring path nearest neighbor in road networks. In Proceedings of SIGMOD, pages 591--602, 2009. Google Scholar
Digital Library
- H.-J. Cho and C.-W. Chung. An efficient and scalable approach to cnn queries in a road network. In Proceedings of VLDB, pages 865--876, 2005. Google ScholarDigital Library
- K. Deng, X. Zhou, H. T. Shen, K. Xu, and X. Lin. Surface k-nn query processing. In Proceedings of ICDE, page 78, 2006. Google ScholarDigital Library
- E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Math, 1:269--271, 1959.Google ScholarDigital Library
- H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. Sondag. Adaptive fastest path computation on a road network: A traffic mining approach. In Proceedings of VLDB, pages 794--805, 2007. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM Trans. Database Syst., 24(2):265--318, 1999. Google ScholarDigital Library
- H. Jagadish, B. Ooi, K.-L. Tan, C. Yu, and R. Zhang. idistance: An adaptive b+-tree based indexing method for nearest neighbour search. TODS, 30(2):364--397, 2005. Google ScholarDigital Library
- C. S. Jensen, J. Kolarvr, T. B. Pedersen, and I. Timko. Nearest neighbor queries in road networks. In Proceedings of ACM GIS, pages 1--8, 2003. Google ScholarDigital Library
- M. Kolahdouzan and C. Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of VLDB, pages 840--851, 2004. Google ScholarDigital Library
- F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S.-H. Teng. On trip planning queries in spatial databases. In Proceedings of SSTD, pages 273--290, 2005. Google ScholarDigital Library
- K. Mouratidis, D. Papadias, and M. Hadjieleftheriou. Conceptual partitioning: an efficient method for continuous nearest neighbor monitoring. In Proceedings of SIGMOD, pages 634--645, 2005. Google ScholarDigital Library
- N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proceedings of SIGMOD, pages 71--79, 1995. Google ScholarDigital Library
- H. Samet, J. Sankaranarayanan, and H. Alborzi. Scalable network distance browsing in spatial databases. In Proceedings of SIGMOD, pages 43--54, 2008. Google ScholarDigital Library
- C. Shahabi, M. R. Kolahdouzan, and M. Sharifzadeh. A road network embedding technique for k-nearest neighbor search in moving object databases. In Proceedings of ACM GIS, pages 94--100, 2002. Google ScholarDigital Library
- M. Sharifzadeh, M. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. In VLDB Journal, pages 765--787, 2008. Google ScholarDigital Library
- S. Shekhar and J. S. Yoo. Processing in-route nearest neighbor queries: a comparison of alternative approaches. In Proceedings of ACM GIS, pages 9--16, 2003. Google ScholarDigital Library
- Y. Tao, D. Papadias, and Q. Shen. Continuous nearest neighbor search. In Proceedings of VLDB, pages 287--298, 2002. Google ScholarDigital Library
- J. S. Yoo and S. Shekhar. In-route nearest neighbor queries. In GeoInformatica, volume 9, pages 117--137, 2005. Google ScholarDigital Library
Index Terms
- Best point detour query in road networks
Recommendations
Monitoring path nearest neighbor in road networks
SIGMOD '09: Proceedings of the 2009 ACM SIGMOD International Conference on Management of dataThis paper addresses the problem of monitoring the k nearest neighbors to a dynamically changing path in road networks. Given a destination where a user is going to, this new query returns the k-NN with respect to the shortest path connecting the ...
Monitoring minimum cost paths on road networks
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsOn a road network, the minimum cost path (or min-cost path for short) from a source location to a destination is a path with the smallest travel cost among all possible paths. Despite that min-cost path queries on static networks have been well studied, ...
A Group Based Approach for Path Queries in Road Networks
SSTD 2013: Proceedings of the 13th International Symposium on Advances in Spatial and Temporal Databases - Volume 8098The 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 ...
Comments