一种基于Hadoop的大规模图最短路径查询方法

• 作者: 单晓欢 宋宝燕 张瑞浩 段琼琼
• 来源期刊: 辽宁大学学报（自然科学版）
• 学科: 工学
• 关键词: Hadoop MapReduce 图分割 最短路径 分布式
• 年，卷（期）: 2016,（2）
• 所属期刊栏目: 数学与信息技术
• 页码范围: 109-113
• 页数: 5页
• 分类号: TP311
• 字数: 3192字
• 语种: 中文

摘要

图的最短路径查询作为图论的经典问题,广泛应用于现实世界的许多应用中.然而随着图的规模日益增大,传统单机环境下的查询算法已无法满足大规模图的处理需求.为解决上述问题,提出基于Hadoop的大规模图最短路径查询方法(D-CH方法):首先利用经典的图分割算法(CNM算法)将存储于Hadoop分布式文件系统(HDFS)中的大规模图进行分割,给出了适于后续算法的标记分割结果;然后将查询区分为分割后子图内查询和子图间查询,基于MapReduce编程模型分别给出相应的并行化查询处理算法.实验结果表明,D-CH方法对大规模图的最短路径查询具有良好的执行效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	宋宝燕	辽宁大学信息学院	87	360	11.0	15.0
2	张瑞浩	辽宁大学信息学院	5	2	1.0	1.0
3	单晓欢	辽宁大学信息学院	8	9	2.0	2.0
4	段琼琼	辽宁大学信息学院	1	1	1.0	1.0