基于缓存技术的路网最短路径查询

doi:10.12068/j.issn.1005-3026.2014.02.011

东北大学学报:自然科学版 ›› 2014, Vol. 35 ›› Issue (2): 199-203.DOI: 10.12068/j.issn.1005-3026.2014.02.011

基于缓存技术的路网最短路径查询

李晓华，王士猛，杨晓春，于戈

(东北大学信息科学与工程学院，辽宁沈阳110819)

收稿日期:2013-05-24 修回日期:2013-05-24 出版日期:2014-02-15 发布日期:2013-11-22
通讯作者: 李晓华
作者简介:李晓华(1969-)，女，辽宁沈阳人，东北大学博士研究生，讲师;杨晓春(1973-)，女，辽宁沈阳人，东北大学教授，博士生导师;于戈(1962-)，男，辽宁大连人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(61322208，61272178)；国家自然科学基金海外及港澳学者合作基金资助项目(61129002)；教育部高等学校博士学科点专项科研基金资助项目(20110042110028)；中央高校基本科研业务费专项资金资助项目(N120504001，N110404015).

Cachebased Shortest Path Query in Road Network

LI Xiaohua， WANG Shimeng， YANG Xiaochun， YU Ge

School of Information Science & Engineering，Northeastern University， Shenyang 110819， China.

Received:2013-05-24 Revised:2013-05-24 Online:2014-02-15 Published:2013-11-22
Contact: LI Xiaohua
About author:-
Supported by:
-

摘要/Abstract

摘要： 分析了目前基于缓存进行路网上最短路径查询常用方法的不足，提出一种支持路网最短路径查询的缓存管理方法.该方法在缓存有限的情况下，有效地选择那些不同但能满足更多查询请求的最短路径，将其放入缓存.提出了缓存代价模型，并设计了缓存构造算法.最后采用真实数据集进行性能分析.实验测试显示，本文提出的方法比现有方法具有更高的缓存命中率，平均执行效率优于现有的处理技术.

关键词: 最短路径, 缓存, 代价模型, 路网, 命中率

Abstract: Based on the analysis of the shortcomings of the existing methods for querying shortest path in road network using cache， a new cachemanaging method was proposed. When the cache’s size was limit， the shortest paths which were expected to answer different queries as much as possible were selected effectively using the method and stored in the cache. The cache benefit model was proposed， with the cache structure designed. The experiments on real data set and the analysis demonstrate that the proposed approach can hit more paths in the cache， which results in the average high performance compared with the existing approaches.

Key words: shortest path, cache, benefit model, road network, hit ratio

中图分类号:

TP31113

李晓华，王士猛，杨晓春，于戈. 基于缓存技术的路网最短路径查询[J]. 东北大学学报:自然科学版, 2014, 35(2): 199-203.

LI Xiaohua， WANG Shimeng， YANG Xiaochun， YU Ge. Cachebased Shortest Path Query in Road Network[J]. Journal of Northeastern University Natural Science, 2014, 35(2): 199-203.

参考文献

[1] Hu H，Lee D L，Lee V.Distance indexing on road networks［C］//Proceedings of the 32nd International Conference on Very Large Data Bases.Seoul，2006:894/905.
[2] Kriegel H P，Kriger P，Renz M，et al.Hierarchical graph embedding for efficient query processing in very large traffic networks［M］//Scientific and Statistical Database Management.Berlin:Springer Berlin Heidelberg，2008:150/167.
[3] Yang X，Wang B，Wang G，et al.RSearch:enhancing keyword search in relational databases using nearly duplicate records［J］.Bulletin of the IEEE Computer Society Technical Committee on Data Engineering，2010:60/66.
[4] Liu X，Yang X.A generalization based approach for anonymizing weighted social network graphs［M］//WebAge Information Management.Berlin:Springer Berlin Heidelberg，2011:118/130.
[5] Wu L，Xiao X，Deng D，et al.Shortest path and distance queries on road networks:an experimental evaluation［J］.Proceedings of the VLDB Endowment，2012，5(5):406/417.
[6] Potamias M，Bonchi F，Castillo C，et al.Fast shortest path distance estimation in large networks［C］//Proceedings of the 18th ACM Conference on Information and Knowledge Management.New York:ACM，2009:867/876.
[7] Wei F.TEDI:efficient shortest path query answering on graphs［C］//Proceedings of the 2010 International Conference on Management of Data.New York:ACM，2010:99/110.
[8] Cheng J，Ke Y，Chu S，et al.Efficient processing of distance queries in large graphs:a vertex cover approach［C］//Proceedings of the 2012 International Conference on Management of Data.New York:ACM，2012:457/468.
[9] Markatos E P.On caching search engine query results［J］.Computer Communications，2001，24(2):137/143.
[10] Thomsen J R，Yiu M L，Jensen C S.Effective caching of shortest paths for locationbased services［C］//Proceedings of the 2012 International Conference on Management of Data.New York:ACM，2012:313/324.

[1]	林宇晗，严健，王侃侃，邓庆绪. 支持缓存划分的全局EDF实时系统调度策略[J]. 东北大学学报（自然科学版）, 2021, 42(12): 1673-1680.
[2]	张田，张子豪，田勇，王昭东. 深度学习在中厚板轧后超快速冷却系统中的研究与应用[J]. 东北大学学报:自然科学版, 2019, 40(5): 635-640.
[3]	蔡凌，汪晋宽，王兴伟，胡曦. 基于Adaboost学习的ICN自适应缓存算法[J]. 东北大学学报:自然科学版, 2019, 40(1): 21-25.
[4]	蔡凌，汪晋宽，王兴伟，韩来权. 基于缓存开销的信息中心网络缓存协作策略[J]. 东北大学学报:自然科学版, 2018, 39(2): 166-171.
[5]	江锦成，吴立新，张媛媛，刘善军. 适用于大规模网络的全源最短路径重优化算法——RASP算法[J]. 东北大学学报:自然科学版, 2017, 38(7): 1037-1042.
[6]	吴刚，邱煜晶，王国仁. 基于隐马尔可夫模型和遗传算法的地图匹配算法[J]. 东北大学学报:自然科学版, 2017, 38(4): 472-475.
[7]	鲍金玲，王斌，刘刚，杨晓春. 基于时间约束的人气最优路径搜索[J]. 东北大学学报:自然科学版, 2016, 37(5): 629-633.
[8]	杜岳峰，申德荣，张亮，于戈. 基于内容相关的条件函数依赖的一致性清洗方法[J]. 东北大学学报:自然科学版, 2016, 37(12): 1683-1687.
[9]	王丽娜，彭瑞卿，冯博，李叶. 基于地图匹配的时空轨迹匿名算法[J]. 东北大学学报:自然科学版, 2014, 35(5): 667-670.
[10]	宋晓莹;温涛;郭权;盛国军;. 基于可调发射功率的无线传感器能量空洞避免算法[J]. 东北大学学报(自然科学版), 2012, 33(12): 1706-1709.
[11]	高立群;依玉峰;郑平;程伟;. 和声搜索算法在求解最短路径问题中的应用[J]. 东北大学学报(自然科学版), 2011, 32(6): 769-772.
[12]	依玉峰;高立群;崔兆华;史圣伦;. 基于PSO的Live Wire交互式图像分割算法[J]. 东北大学学报(自然科学版), 2011, 32(2): 193-196+201.
[13]	周本海;乔建忠;林树宽;. 基于多核处理器的动态共享缓存分配算法[J]. 东北大学学报(自然科学版), 2011, 32(1): 44-47.
[14]	赵海;李占旭;宋纯贺;蒋未未;. 网孔自动搜索算法在水电仿真中的设计与实现[J]. 东北大学学报(自然科学版), 2008, 29(9): 1253-1256.
[15]	薛建生;王光兴;. 一种基于动态分级网关代理的移动IP缓存方案[J]. 东北大学学报(自然科学版), 2006, 27(4): 378-381.

基于缓存技术的路网最短路径查询

Cachebased Shortest Path Query in Road Network

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价