Effective caching of shortest paths for location-based services

Jeppe Rishede Thomsen, Man Lung Yiu, Christian S. Jensen

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

45 Citations (Scopus)


Web search is ubiquitous in our daily lives. Caching has been extensively used to reduce the computation time of the search engine and reduce the network traffic beyond a proxy server. Another form of web search, known as online shortest path search, is popular 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 essential 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 algorithm 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 effectiveness of our proposed techniques.
Original languageEnglish
Title of host publicationSIGMOD '12 - Proceedings of the International Conference on Management of Data
Number of pages12
Publication statusPublished - 28 Jun 2012
Event2012 ACM SIGMOD International Conference on Management of Data, SIGMOD '12 - Scottsdale, AZ, United States
Duration: 21 May 201224 May 2012


Conference2012 ACM SIGMOD International Conference on Management of Data, SIGMOD '12
Country/TerritoryUnited States
CityScottsdale, AZ


  • caching
  • shortest path

ASJC Scopus subject areas

  • Software
  • Information Systems

Cite this