基于Grid网格划分的改进路网最短路径查询

• 作者: 于戈 李晓华 杨晓春 王士猛
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 路网 最短路径 缓存 代价模型 划分
• 年，卷（期）: 2014,（9）
• 所属期刊栏目: 计算机软件与数据库
• 页码范围: 1937-1942
• 页数: 6页
• 分类号: TP311
• 字数: 6694字
• 语种: 中文

摘要

最短路径查询作为图数据库管理的一项重要课题在近些年来受到国内外学者的广泛关注.在现实应用中有效地利用缓存进行路网上最短路径查询成为一个重要的研究问题,而现有方法在缓存有限的条件下均不能高效地响应用户查询请求.针对上述问题本文提出了一种有效的用于支持路网最短路径查询的缓存代价模型,设计了缓存构造算法,进而高效的选择那些不同且能满足更多查询请求的最短路径放入缓存.基于此模型,利用Grid对大图进行划分,提高了查询效率,节省了辅助的存储空间和查询处理代价.最后采用真实数据集进行性能分析,实验结果显示本文提出的方法更有效.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	于戈	东北大学信息科学与工程学院软件研究所	426	6587	38.0	64.0
2	杨晓春	东北大学信息科学与工程学院软件研究所	65	1090	16.0	32.0
3	李晓华	东北大学信息科学与工程学院软件研究所	15	76	5.0	7.0
4	王士猛	东北大学信息科学与工程学院软件研究所	2	8	2.0	2.0