Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/39836
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.
URI: http://hdl.handle.net/10397/39836
ISBN: 978-1-4503-1247-9
DOI: 10.1145/2213836.2213872
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

13
Citations as of Feb 25, 2017

Page view(s)

20
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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