Please use this identifier to cite or link to this item:
Title: Effective caching of shortest paths for location-based services
Authors: Thomsen, JR
Yiu, ML 
Jensen, CS
Keywords: Caching
Shortest path
Issue Date: 2012
Source: Proceedings of the ACM Conference on Management of Data (SIGMOD), Scottsdale, Arizona, USA, May 2012, p. 313-324 How to cite?
Abstract: 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.
ISBN: 978-1-4503-1247-9
DOI: 10.1145/2213836.2213872
Appears in Collections:Conference Paper

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Jul 5, 2018

Page view(s)

Last Week
Last month
Citations as of Jul 10, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.