Ppc: A New Cache Replacement System For Efficient Path Planning On Roads

Abstract

Owing to the wide availability of the global positioning system (GPS) and digital mapping of roads, road network navigationservices have become a basic application on many mobile devices. Path planning, a fundamental function of road network navigationservices, finds a route between the specified start location and destination. The efficiency of this path planning function is critical formobile 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 thispaper, we propose a system, namely, Path Planning by Caching (PPC), to answer a new path planning query in real time by efficientlycaching and reusing historical queried-paths. Unlike the conventional cache-based path planning systems, where a queried-path incache is used only when it matches perfectly with the new query, PPC leverages the partially matched queries to answer part(s) of thenew query. As a result, the server only needs to compute the unmatched path segments, thus significantly reducing the overall systemworkload. Comprehensive experimentation on a real road network database shows that our system outperforms the state-of-the-artpath planning techniques by reducing 32 percent of the computation latency on average.