An Improved Algorithm to Enhance the Utilization of Shortest Path Caches
Xiaohua Li, Shimeng Wang, Bin Wang, Xiaochun Yang, Ge Yu · 2013
The caching has been developed for shortest path queries. At present, existing methods for the shortest path caching include the dynamic cache method Least-Recently-Used (LRU), the static cache method Highest-Query-Frequency (HQF), as well as a recently proposed method Shortest "Path" Cache (SPC). It is commonly known that LRU and HQF are not efficient enough for the shortest path caching. To the best of our knowledge, SPC is the state-of-art technique in the shortest path caching. However, in their method, they fully rely on the information from the historical log, making their method over fit the historical log. In this regard, this paper proposes an improved cache loading method, in which we try to cover as many paths as possible. At the same time, the cache utilization is maximized. Experiments on benchmark datasets demonstrate that the proposed approach has a better perfrmance than that of SPC, improve the cache utilization and decrease the query process time.