Effective shortest travel-time path caching and estimating for location-based services
Effective shortest travel-time path caching and estimating for location-based services
复制标题
基于位置的服务的有效最短旅行时间路径缓存和估计
DOI：
10.1007/s11280-018-0549-2
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Qing Li
中科院分区：
文献类型：
--
作者：
Detian Zhang;An Liu;Zhixu Li;Gangyong Jia;Fei Chen;Qing Li
对于基于位置的服务（LBS）来说，旅行时间最短的路径比网络距离最短的路径更有意义，因为它考虑了道路网络中的实时交通。通常，LBS 提供商有两种方式为其查询提供最短行程时间路径，即自行计算或从外部 Web 地图服务检索。然而，这两种方式都很昂贵，比如计算成本高、延迟长。为了加速最短路径查询处理，我们在本文中为 LBS 提供商设计了一种有效的最短旅行时间路径缓存。与传统的路径缓存技术（缓存仅适用于基于距离的路径）不同，我们提出的缓存是动态的，并且可以支持基于行进时间的路径。更重要的是，设计了一种新的缓存操作，即路径连接，当缓存无法直接回答查询时，可以根据缓存的路径估计查询的路径信息。真实网络地图服务和数据集的实验结果证实了所提出技术的有效性。
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.
登录
查看更多内容
DOI：
--
发表时间：
1967
期刊：
--
影响因子：
--
作者：
J. E. Falk;R Fletcher;M. J. D. Powell;Peter E Hart;Nils J Nilsson;Bertram Raphael
通讯作者：
J. E. Falk;R Fletcher;M. J. D. Powell;Peter E Hart;Nils J Nilsson;Bertram Raphael
DOI：
10.1007/978-3-642-15364-8_36
发表时间：
2010-08
期刊：
--
影响因子：
--
作者：
Ugur Demiryurek;F. Kashani;C. Shahabi
通讯作者：
Ugur Demiryurek;F. Kashani;C. Shahabi
DOI：
10.1145/954339.954341
发表时间：
2003-12
期刊：
ACM Comput. Surv.
影响因子：
--
作者：
Stefan Podlipnig;L. Böszörményi
通讯作者：
Stefan Podlipnig;L. Böszörményi
DOI：
10.1007/978-3-319-68783-4_29
发表时间：
2017-10
期刊：
--
影响因子：
--
作者：
Detian Zhang;An Liu;Gangyong Jia;Fei Chen;Qing Li;Jian Li
通讯作者：
Detian Zhang;An Liu;Gangyong Jia;Fei Chen;Qing Li;Jian Li
DOI：
10.1016/j.jpdc.2012.02.007
发表时间：
2011-05
期刊：
2011 IEEE International Parallel & Distributed Processing Symposium
影响因子：
--
作者：
Daniel Delling;A. Goldberg;A. Nowatzyk;Renato F. Werneck
通讯作者：
Daniel Delling;A. Goldberg;A. Nowatzyk;Renato F. Werneck