TY - GEN
T1 - Efficient cache-supported path planning on roads (Extended abstract)
AU - Zhang, Ying
AU - Hsueh, Yu Ling
AU - Lee, Wang Chien
AU - Jhang, Yi Hao
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/5/16
Y1 - 2017/5/16
N2 - Owing to the wide availability of the global positioning system (GPS) and digital mapping of roads, road network navigation services have become a basic application on many mobile devices. Path planning, a fundamental function of road network navigation services, finds a route between the specified start location and destination. The efficiency of this path planning function is critical for mobile users on roads due to various dynamic scenarios, such as a sudden change in driving direction, unexpected traffic conditions, lost or unstable GPS signals, and so on. In these scenarios, the path planning service needs to be delivered in a timely fashion. In this paper, we propose a system, namely, Path Planning by Caching (PPC), to answer a new path planning query in real time by efficiently caching and reusing historical queried-paths. Unlike the conventional cachebased path planning systems, where a queried-path in cache is used only when it matches perfectly with the new query, PPC leverages the partially matched queries to answer part(s) of the new query. Comprehensive experimentation on a real road network database shows that our system outperforms the stateof-The-Art path planning techniques by reducing 32% of the computation latency on average.
AB - Owing to the wide availability of the global positioning system (GPS) and digital mapping of roads, road network navigation services have become a basic application on many mobile devices. Path planning, a fundamental function of road network navigation services, finds a route between the specified start location and destination. The efficiency of this path planning function is critical for mobile users on roads due to various dynamic scenarios, such as a sudden change in driving direction, unexpected traffic conditions, lost or unstable GPS signals, and so on. In these scenarios, the path planning service needs to be delivered in a timely fashion. In this paper, we propose a system, namely, Path Planning by Caching (PPC), to answer a new path planning query in real time by efficiently caching and reusing historical queried-paths. Unlike the conventional cachebased path planning systems, where a queried-path in cache is used only when it matches perfectly with the new query, PPC leverages the partially matched queries to answer part(s) of the new query. Comprehensive experimentation on a real road network database shows that our system outperforms the stateof-The-Art path planning techniques by reducing 32% of the computation latency on average.
UR - http://www.scopus.com/inward/record.url?scp=85021217944&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85021217944&partnerID=8YFLogxK
U2 - 10.1109/ICDE.2017.14
DO - 10.1109/ICDE.2017.14
M3 - Conference contribution
AN - SCOPUS:85021217944
T3 - Proceedings - International Conference on Data Engineering
SP - 15
EP - 16
BT - Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017
PB - IEEE Computer Society
T2 - 33rd IEEE International Conference on Data Engineering, ICDE 2017
Y2 - 19 April 2017 through 22 April 2017
ER -