Effective Caching of Shortest Paths for Location-Based Services

Web search is ubiquitous in our daily lives. Caching has been ex-tensively used to reduce the computation time of the search en-gine and reduce the network traffic beyond a proxy server. Another form of web search, known as online shortest path search, is popu-lar due to advances in geo-positioning. However, existing caching techniques are ineffective for shortest path queries. This is due to several crucial differences between web search results and shortest path results, in relation to query matching, cache item overlapping, and query cost variation. Motivated by this, we identify several properties that are essen-tial to the success of effective caching for shortest path search. Our cache exploits the optimal subpath property, which allows a cached shortest path to answer any query with source and target nodes on the path. We utilize statistics from query logs to estimate the benefit of caching a specific shortest path, and we employ a greedy algo-rithm for placing beneficial paths in the cache. Also, we design a compact cache structure that supports efficient query matching at runtime. Empirical results on real datasets confirm the effective-ness of our proposed techniques. 1