Efficient Evaluation of Shortest Travel-Time Path Queries in Road Networks by Optimizing Waypoints in Route Requests Through Spatial Mashups

详细信息    查看全文

• 关键词：Spatial mashups ; Location ; based services ; Direction sharing ; Waypoints ; Web mapping services
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9931
• 期：1
• 页码：104-115
• 全文大小：274 KB
• 参考文献：1.Zhang, D., Chow, C.Y., Li, Q., Zhang, X., Xu, Y.: Efficient evaluation of k-NN queries using spatial mashups. In: SSTD (2011)
  2.Zhang, D., Chow, C.Y., Li, Q., Zhang, X., Xu, Y.: SMashQ: spatial mashup framework for k-NN queries in time-dependent road networks. Distrib. Parallel Databases DAPD 31(2), 259–287 (2013)CrossRef
  3.Zhang, D., Chow, C.Y., Li, Q., Zhang, X., Xu, Y.: A spatial mashup service for efficient evaluation of concurrent k-nn queries. IEEE Trans. Comput. (accepted to appear)
  4.Li, Y., Yiu, M.L.: Route-saver: leveraging route apis for accurate and efficient query processing at location-based services. IEEE TKDE 27(1), 235–249 (2015)
  5.ProgrammableWeb. http://​www.​programmableweb.​com/​category-api
  6.The Google Directions API. https://​developers.​google.​com/​maps/​documentation/​directions
  7.MapQuest Directions Web Service. http://​www.​mapquestapi.​com/​directions
  8.Levandoski, J.J., Mokbel, M.F., Khalefa, M.E.: Preference query evaluation over expensive attributes. In: CIKM (2010)
  9.Google Maps/Google Earth APIs Terms of Service. http://​code.​google.​com/​apis/​maps/​terms.​html
  10.Wu, L., Xiao, X., Deng, D., Cong, G., Zhu, A.D., Zhou, S.: Shortest path and distance queries on road networks: an experimental evaluation. In: VLDB (2012)
  11.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: ACM SIGMOD (2013)
  12.Sommer, C.: Shortest-path queries in static networks. ACM Comput. Surv. (CSUR) 46(4), 45:1–45:31 (2014)CrossRef MATH
  13.Demiryurek, U., Banaei-Kashani, F., Shahabi, C., Ranganathan, A.: Online computation of fastest path in time-dependent spatial networks. In: Pfoser, D., Tao, Y., Mouratidis, K., Nascimento, M.A., Mokbel, M., Shekhar, S., Huang, Y. (eds.) SSTD 2011. LNCS, vol. 6849, pp. 92–111. Springer, Heidelberg (2011)CrossRef
  14.George, B., Kim, S., Shekhar, S.: Spatio-temporal network databases and routing algorithms: a summary of results. In: Papadias, D., Zhang, D., Kollios, G. (eds.) SSTD 2007. LNCS, vol. 4605, pp. 460–477. Springer, Heidelberg (2007)CrossRef
  15.Ding, B., Yu, J.X., Qin, L.: Finding time-dependent shortest paths over large graphs. In: EDBT (2008)
  16.Bruno, N., Gravano, L., Marian, A.: Evaluating top-\(k\) queries over web-accessible databases. In: IEEE ICDE (2002)
  17.Chang, K.C.C., Hwang, S.W.: Minimal probing: supporting expensive predicates for top-\(k\) queries. In: ACM SIGMOD (2002)
  18.Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)MATH
  19.Thomsen, J.R., Yiu, M.L., Jensen, C.S.: Effective caching of shortest paths for location-based services. In: ACM SIGMOD (2012)
  20.Karger, D., Motwani, R., Ramkumar, G.: On approximating the longest path in a graph. Algorithmica 18(1), 82–98 (1997)MathSciNet CrossRef MATH
  21.The Google Places API. https://​developers.​google.​com/​places/​
  
• 作者单位：Detian Zhang (17)
  Chi-Yin Chow (18)
  Qing Li (18) (19)
  An Liu (20)
  
  17. School of Digital Media, Jiangnan University, Wuxi, China
  18. Department of Computer Science, City University of Hong Kong, Kowloon Tong, Hong Kong
  19. Multimedia Software Engineering Research Centre, City University of Hong Kong Shenzhen Research Institute, Shenzhen, Guangdong, China
  20. School of Computer Science, Soochow University, Suzhou, China
  
• 丛书名：Web Technologies and Applications
• ISBN：978-3-319-45814-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9931

文摘

In the real world, the route with the shortest travel time in a road network is more meaningful than that with the shortest network distance for location-based services (LBS). However, not every LBS provider has adequate resources to compute/estimate travel time for routes by themselves. A cost-effective way for LBS providers to estimate travel time for routes is to issue external requests to Web mapping services (e.g., Google Maps, Bing Maps, and MapQuest Maps). Due to the high cost of processing such external requests and the usage limits of Web mapping services, we take the advantage of direction sharing and waypoints supported by Web mapping services to reduce the number of external requests and the query response time for shortest travel-time route queries in this paper. We model the problem of selecting the optimal waypoints for an external route request as finding the longest simple path in a weighted bipartite digraph. As it is a NP-complete problem, we propose a greedy algorithm to find the best set of waypoints in an external route request. We evaluate the performance of our approach using real Web mapping services, a real road network, real and synthetic data sets. Experimental results show the efficiency, scalability, and applicability of our approach.