Refreshment of the shortest path cache with change of single edge
详细信息 查看全文
- 作者：Xiaohua Lia ; lixiaohua@mail.neu.edu.cn" class="auth_mail" title="E-mail the corresponding author ; Tao Qiua ; qiutaoneu@gmail.com" class="auth_mail" title="E-mail the corresponding author ; Ning Wang ; b ; ningwang@shu.edu.cn" class="auth_mail" title="E-mail the corresponding author ; Xiaochun Yanga ; yangxc@mail.neu.edu.cn" class="auth_mail" title="E-mail the corresponding author ; Bin Wanga ; binwang@mail.neu.edu.cn" class="auth_mail" title="E-mail the corresponding author ; Ge Yua ; yuge@ise.neu.edu.cn" class="auth_mail" title="E-mail the corresponding author
- 关键词：Shortest path caching ; Cache refreshment strategy ; Change of road network ; Affected shortest paths
- 刊名：Expert Systems with Applications
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：67
- 期：Complete
- 页码：1-11
- 全文大小：884 K
文摘
- •
We are the first to study the problem of refreshing a cache in a changed graph.
- •
A bitmap-based cache structure is designed to store shortest paths.
- •
Three algorithms are developed to detect affected shortest paths.
- •
Four refreshment strategies are proposed to update a cache efficiently.
- •
Extensive experiments on real data sets show the efficiency of our algorithms.