基于改进Hadoop的大规模图处理系统的设计与实现

论文摘要

“智能交通”和“社交网络”越来越普及,然而如何处理这些领域背后复杂图结构的问题迫在眉睫。比如,在“智能交通”中,如何计算两点之间的最短路径则可以抽象成计算大规模图中两点之间的最短路径,在“社交网络”中判断两个用户之间是否有社交关系则可以抽象为计算两个点在大规模图中是否可达等等。随着“大数据”和“云计算”的发展,图规模的结构变得越来越庞大,单个计算机节点根本无法存储大规模图结构,因此分布式存储架构被提出。对于图计算目前集中在两个计算模型中,一个是MapReduce模型,该模型将图计算分解成map阶段和reduce阶段,实现MapReduce模型的分布式框架是著名的Hadoop;另一个图计算模型是BSP模型,实现该模型的分布式框架是Hama,通过对二者的特点进行对比发现,MapReduce具有较高的抽象性和通用性,接口非常成熟,易于编程实现,但是并不支持显式的迭代和实时性计算,而BSP模型引入“超步”的概念,可以加速计算,但是却对集群中计算节点的内存性能要求比较高。因此本文将结合二者的优点对Hadoop进行改进,结合“MapReduce模型+BSP模型”的特点,使Hadoop成为一个可以进行显式迭代的图处理分布式框架。目前已经有人在Hadoop第一代上进行改进并成功的支持了显式的迭代,较好的提高了效率,但是目前第一代Hadoop用户量已经很少,Hadoop第二代通过引入Yarn较好的解决了第一代存在的两个问题。第一,扩展性问题,JobTracker兼有的资源管理功能和作业控制功能将成为制约系统扩展的瓶颈;第二,单点故障问题,JobTracker存在单点故障,出现问题之后将导致整个集群不可用;因此本文将着手在第二代Hadoop上对其进行改进,同时在改进Hadoop框架的基础上,本文实现了单源最短路径算法、可达查询算法和时间序列图中最优路径算法,将大规模图处理系统进行发布,供用户进行使用,对于研究图计算的研究人员来说将具有非常重要的价值和意义。

论文目录

摘要

abstract

第1章绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 核心技术介绍

1.3.1 MapReduce模型

1.3.2 BSP模型

1.3.3 YARN

1.3.4 HDFS

1.3.5 Maven项目管理工具

1.4 图处理算法概述

1.4.1 单源最短路径介绍

1.4.2 可达查询介绍

1.4.3 时间序列图中最优路径介绍

1.5 本文研究内容

1.6 本文组织结构

第2章大规模图处理系统的需求分析

2.1 系统功能需求分析

2.2 系统性能需求分析

2.3 本章小结

第3章大规模图处理系统的总体设计

3.1 Hadoop框架改进

3.2 大规模图处理系统总体架构设计

3.2.1 系统总体架构图

3.2.2 系统各模块功能设计

3.3 小结

第4章大规模图处理系统的详细设计

4.1 认证模块详细设计

4.2 文件校验模块详细设计

4.2.1 安全校验

4.2.2 格式校验

4.3 算法处理模块详细设计

4.3.1 单源最短路径详细设计

4.3.2 可达查询详细设计

4.3.3 时间序列图中最优路径详细设计

4.4 查询模块详细设计

4.5 下载模块详细设计

4.6 计时模块详细设计

4.7 小结

第5章系统的实现与测试

5.1 系统开发环境

5.1.1 硬件环境

5.1.2 软件环境

5.2 算法的实现与测试

5.2.1 单源最短路径的实现与测试

5.2.2 可达查询的实现与测试

5.2.3 时间序列图中最优路径的实现与测试

5.3 改进的Hadoop框架与原Hadoop框架测试结果对比

5.4 小结

第6章总结与展望

6.1 本文研究成果总结

6.2 工作中不足及展望

致谢

参考文献

攻读学位期间发表的学术论文及参加科研情况

文章来源

类型: 硕士论文

作者: 张永普

导师: 宋宝燕

关键词: 大规模图,分布式,模型,框架

来源: 辽宁大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 辽宁大学

分类号: O157.5

总页数: 72

文件大小: 3563K

下载量: 55

基于改进Hadoop的大规模图处理系统的设计与实现

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢