Concise caching of driving instructions

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

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

5 Citations (Scopus)

Abstract

2014 ACM. Online driving direction services offer fundamental functionality to mobile users, and such services see substantial and increasing loads as mobile access continues to proliferate. Cache servers can be deployed in order to reduce the resulting network traffic. We define so-called concise shortest paths that are equivalent to driving instructions. A concise shortest path occupies much less space than a shortest path; yet it provides sufficient navigation information to mobile users. Then we propose techniques that enable the caching of concise shortest paths in order to improve the cache hit ratio. Interestingly, the use of concise shortest paths in caching has two opposite effects on the cache hit ratio. The cache can accommodate a larger number of concise paths, but each individual concise path contains fewer nodes and so may answer fewer shortest path queries. The challenge is to strike a balance between these two effects in order to maximize the overall cache hit ratio. In this paper, we revisit two classes of caching methods and develop effective caching techniques for concise paths. Empirical results on real trajectory-induced workloads confirm the effectiveness of the proposed techniques.
Original languageEnglish
Title of host publication22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014
PublisherAssociation for Computing Machinery
Pages23-32
Number of pages10
Volume04-07-November-2014
ISBN (Electronic)9781450331319
DOIs
Publication statusPublished - 4 Nov 2014
Event22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014 - Dallas, United States
Duration: 4 Nov 20147 Nov 2014

Conference

Conference22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2014
CountryUnited States
CityDallas
Period4/11/147/11/14

Keywords

  • Caching
  • Road networks
  • Shortest paths

ASJC Scopus subject areas

  • Earth-Surface Processes
  • Computer Science Applications
  • Modelling and Simulation
  • Computer Graphics and Computer-Aided Design
  • Information Systems

Cite this