Cache-Based Shortest Path Query Algorithm for Time-Varying Road Networks

As one of the fundamental operations in graph theory, the shortest path query has been extensively applied to the related applications based on road networks, including GPS navigation and personalized recommendation. In view of the high computational cost and slow query speed faced by the use of servers in the road network to query the shortest path online, the existing solutions usually utilize caching technology to optimize their performance. Considering that the edge weight of the road network has the characteristics of frequent changes, the existing related work failed to effectively realize the rapid update of cached data, then ignored the timeliness of the shortest path in the cache, which led to a decrease in the cache hit ratio. In view of this, we first propose a new cache storage structure that effectively balances the relationship between the overall query speed of the shortest path and the cache data update speed; Secondly, we propose a cache storage strategy that combines path sharing abilities and path diversity to optimize cache revenue and improve cache hit ratio; Finally, we propose a cache-based time-varying shortest path query (CTSPQ) algorithm based on the storage structure to improve the speed of querying the shortest path in the cache. A great deal of experiments on real data sets prove the effectiveness and scalability of the proposed techniques.