Effective shortest travel-time path caching and estimating for location-based services

For location-based services (LBS), the path with the shortest travel time is much more meaningful than the one with the shortest network distance, as it considers the live traffics in road networks. Usually, there are two ways for an LBS provider to provide the shortest travel-time paths for its queries, i.e., computing by itself or retrieving from external Web mapping services. However, both of these two ways are expensive, like costly computation and long latency. To accelerate shortest path query processing, we design an effective cache of shortest travel-time paths for LBS providers in this paper. Unlike the conventional path caching techniques, where the caches are only suitable for distance-based paths, our proposed cache is dynamic and can support travel-time-based paths. More importantly, a new cache operation, namely path join, is devised to estimate the path information for a query based on the cached paths, when the cache can not answer the query directly. Experimental results on a real Web mapping service and datasets confirm the effectiveness of the proposed techniques.