TY - GEN
T1 - Efficient evaluation of shortest travel-time path queries in road networks by optimizing waypoints in route requests through spatial mashups
AU - Zhang, Detian
AU - Chow, Chi Yin
AU - Li, Qing
AU - Liu, An
PY - 2016/1/1
Y1 - 2016/1/1
N2 - 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.
AB - 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.
KW - Direction sharing
KW - Location-based services
KW - Spatial mashups
KW - Waypoints
KW - Web mapping services
UR - http://www.scopus.com/inward/record.url?scp=84989350605&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-45814-4_9
DO - 10.1007/978-3-319-45814-4_9
M3 - Conference article published in proceeding or book
AN - SCOPUS:84989350605
SN - 9783319458137
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 104
EP - 115
BT - Web Technologies and Applications - 18th Asia-Pacific Web Conference, APWeb 2016, Proceedings
A2 - Liu, Guanfeng
A2 - Li, Feifei
A2 - Shim, Kyuseok
A2 - Zheng, Kai
PB - Springer-Verlag
T2 - 18th Asia-Pacific Web Conference on Web Technologies and Applications, APWeb 2016
Y2 - 23 September 2016 through 25 September 2016
ER -