Research On Shortest Path Caching Method For Time-Varying Road Network

As one of the hot research issues in graph theory,the shortest path has been widely used in path planning,GPS navigation and other related applications based on the timevarying road network,which plays an important role in people’s daily travel.However,the traditional online shortest path query algorithm generally has the problems of high computational cost and the inability to take into account the validity and timeliness of query results.As technology in network service,caching plays an important role in reducing query response time and improving system performance.The current shortest path caching algorithm for time-varying road networks has a low cache hit ratio because it relies too much on historical log information,therefore,the timeliness of the data is neglected and the utilization ratio data can not be guaranteed.We are devoted to exploring the shortest path cache construction scheme to further improve the overall performance of the shortest path query problem in timevarying road networks based on the current research experiences and achievements.This paper contribution mainly includes the following 4 aspects:1.We first designed a cache-based shortest path query framework called CTSPQ,which measures the sharing power of data in the cache via the shortest path cache revenue model,and propose a named AMPS storage format to store cached data.2.We introduced the KD-tree index to standardize the mapping nodes,proposed a GC Caching strategy based on the greedy strategy to cache the shortest path,and introduced a join operation to evaluate the query requests in the cache that cannot directly answer the shortest path.3.Our proposed GS strategy introduces a diversity technique to optimize the GC strategy based on local matching of cache paths to return partial results of query requests.And a Z-curve index is introduced in the cache to map the cached data and perform bulk queries in combination with query direction and path consistency.4.We have conducted extensive experiments on GC and GS methods,and verified that the accuracy of the above two strategies is up to 80% or more with an allowable query result error of 10%;the hit ratio and response time of GS and GC strategies are2.5-10 times and 0.5-2 times higher than those of SPC algorithms,respectively;compared with EPC algorithms,the hit ratio metrics of GC and GS algorithms are significantly better than 10-50 times better than the EPC algorithm.