Constructing Effective Caches of Shortest Path Queries on Road Networks

IEEE Access

Tao Qiu¹  Ning Wang²  Bin Wang³  Ge Yu³  Xiaohua Li³ 

[1] College of Computer Science, Shenyang Aerospace University, Shenyang, China;Department of Information Management, School of Management, Shanghai University, Shanghai, China;School of Computer Science and Engineering, Northeastern University, Shenyang, China;

关键词: Shortest path;    caching technology;    grid partitioning;    benefit model;    road network;   

DOI  :  10.1109/ACCESS.2020.3024664

来源: DOAJ

【 摘 要 】

How to effectively utilize caching technology to support high-performance shortest path queries on road networks has become an important research problem since the popularization of location-based services. Most of the existing methods design a statistical model to construct the cache with the shortest paths, and mainly consider the related query frequency obtained from the historical query logs. As a result, the paths in the cache may be concentrated in a few hot-spot areas of the road network, such as the prosperous areas of a city. Additionally, queries from remote areas may never be hit in the cache, which results in the cache hit ratio is not fully optimized. To address this problem, we define an effective model to quantify the effect of cached shortest paths; the model not only considers the related query frequency in the log but also the coverage of the paths on the road network. Then, we propose an efficient cache construction method to select the cached shortest paths from the query log. Furthermore, we design a hybrid index for the shortest paths in the cache, so that the efficiency of shortest path querying is significantly improved. Finally, we conduct comprehensive experimental studies on different datasets to verify that the cache hit ratio is greatly improved by using the proposed cache construction approaches.

【 授权许可】

Unknown