Efficient Evaluation of Shortest Travel-Time Path Queries in Road Networks by Optimizing Waypoints in Route Requests Through Spatial Mashups
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.
Spatial mashups Location-based services Direction sharing Waypoints Web mapping services
Detian Zhang Chi-Yin Chow Qing Li An Liu
School of Digital Media,Jiangnan University,Wuxi,China Department of Computer Science,City University of Hong Kong,Kowloon Tong,Hong Kong Department of Computer Science,City University of Hong Kong,Kowloon Tong,Hong Kong;Multimedia Softwa School of Computer Science,Soochow University,Suzhou,China
国际会议
International Asia-Pacific Web Conference(第18届国际亚太互联网大会)
苏州
英文
104-115
2016-09-23（万方平台首次上网日期，不代表论文的发表时间）