图划分对Arc-flags算法的影响

• 作者: 刘惠民 周英华 孙广中
• 来源期刊: 地球信息科学学报
• 关键词: Arc-flags算法 算法分析 图划分 最短路径 预处理
• 年，卷（期）: 2016,（11）
• 所属期刊栏目: ACM SIGSPATIAL 2015中国分会特邀稿件
• 页码范围: 1456-1464
• 页数: 9页
• 字数: 8241字
• 语种: 中文

摘要

最短路径计算作为导航的常用算法在移动互联网中扮演了重要角色,由于路网规模的增大和终端的不停移动,传统的串行最短路径算法已经无法满足实时性要求,因此预处理技术得到了广泛使用.Arc-flags是一个经典的基于预处理技术的最短路径算法,可以提供高效的在线最短路径查询服务.现有Arc-flags算法的研究主要集中在提升预处理时空效率和比较不同路网划分方式的优劣上,尚未见图划分对Arc-flags算法影响的深入研究.本文在真实路网上测试了不同的图划分数量和边界点数量等因素对Arc-flags算法的影响,主要包括预处理时间和空间的消耗、在线查询时间和搜索范围等方面,并根据实验结果和分析提出了合理的图划分建议(如选用好的图划分方法减少边界点数量等),为改进和使用Arc-flags算法提供指导.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周英华	中国科学技术大学网络信息中心	6	21	3.0	4.0