Efficient Cache-Supported Path Planning on Roads

Ying Zhang, Yu-Ling Hsueh, Wang-Chien Lee, Yi-Hao JhangIEEE TKDE 2015 · DOI

Abstract

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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">timely</i> fashion. In this paper, we propose a system, namely, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Path Planning by Caching (PPC)</i> , to answer a new path planning query in real time by efficiently caching and reusing historical queried-paths. Unlike the conventional cache-based 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. As a result, the server only needs to compute the unmatched path segments, thus significantly reducing the overall system workload. Comprehensive experimentation on a real road network database shows that our system outperforms the state-of-the-art path planning techniques by reducing 32 percent of the computation latency on average.
BibTeX
@article{zhang2015efficient,
  author = {Ying Zhang and Yu-Ling Hsueh and Wang-Chien Lee and Yi-Hao Jhang},
  title = {{Efficient Cache-Supported Path Planning on Roads}},
  journal = {IEEE Transactions on Knowledge and Data Engineering},
  year = {2015},
  doi = {10.1109/tkde.2015.2507581},
}

Loading related content...

Figure