分布式大规模图数据流式划分算法FENNEL的改进

发布时间：2017-09-24 13:28

  本文关键词：分布式大规模图数据流式划分算法FENNEL的改进

  更多相关文章： 图划分 流式数据 FENNEL 并发改进 树形网络

【摘要】：图划分在分布式计算和大规模图数据处理等方面有着重大的意义。当图数据规模较小时,静态图划分算法(如METIS)能有效处理,获得较小的切边率;但是随着应用快速发展,图数据规模的急剧增长给静态图划分算法造成显著挑战,因其处理速度及可扩展性较差而难以处理千万级以上大规模的流式图数据。流式图划分算法的出现很好的解决了上述问题。FENNEL算法对多种流式图划分算法进行了统一的建模,其切边率要优于目前主流的流式图划分算法,且较为接近学术界公认优秀的静态图划分系统METIS,而其运行速度却比METIS快。不过,FENNEL算法是一种串行的流式划分算法,扩展能力受限,如何提高其并发性而且减少因并发性提高而带来的切边率影响就成为改进所面临的主要挑战。本项研究通过对FENNEL的处理模型进行分析,找出FENNEL现有分布式部署方法中,星形串行网络模型存在的处理效率低、可扩展性差等问题,并针对这两方面的问题,提出了一种并发改进方案,以及一种树形网络拓扑结构,并进行理论推导,以求证其可改善系统并发性及扩展性。然后,对各种类型的图数据进行串行、并发模型的对比测试,测试数据表明了在原生图数据以及图数据随机到达的情况下,FENNEL并发改进方案可以保证几乎不影响图划分切边率,同时有效的加快图划分的速率,但是其速率会随着工作节点数量的增加而减低;而树形网络拓扑结构能通过调整并发度来有效提高图划分速率,且其速率几乎不会受到工作节点数量的影响。不过,对于按照广度优先搜索顺序进行预处理后的图数据,即图节点按照邻接关系顺序进行划分处理,并发方法将显著提高其切边率。
【关键词】：图划分 流式数据 FENNEL 并发改进 树形网络
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-8
• 1 绪论8-14
• 1.1 研究背景8-9
• 1.2 研究现状9-12
• 1.3 本文的研究内容12
• 1.4 本文的组织结构12-14
• 2 FENNEL算法14-23
• 2.1 图划分相关定义和基本知识14
• 2.2 常见流式图划分算法14-16
• 2.3 流式图划分算法FENNEL16-21
• 2.4 FENNEL的分布式部署21-22
• 2.5 本章小结22-23
• 3 分布式FENNEL的改进23-33
• 3.1 FENNEL的分布式模型23-25
• 3.2 顶点数据发送的并发改进25-29
• 3.3 星形网络到树形网络的改进29-32
• 3.4 本章小结32-33
• 4 设计实现33-41
• 4.1 顶点数据发送的并发改进设计实现33-37
• 4.2 树形网络拓扑结构的设计实现37-40
• 4.3 本章小结40-41
• 5 测试结果及分析41-52
• 5.1 星形网络并发性改进相关测试分析41-47
• 5.2 树形网络的相关测试与分析47-49
• 5.3 并发改进对BFS图数据划分准确性测试及分析49-51
• 5.4 本章小结51-52
• 6 总结与展望52-54
• 6.1 工作总结52
• 6.2 研究展望52-54
• 致谢54-55
• 参考文献55-58

【相似文献】

中国期刊全文数据库 前10条

1 冷明平;孙凌宇;郭恺强;边计年;朱平;;赋权超图划分算法的电路划分实验比较研究[J];计算机工程与应用;2012年16期

2 许金凤;董一鸿;王诗懿;何贤芒;陈华辉;;大规模图数据划分算法综述[J];电信科学;2014年07期

3 李莉杰;陈端兵;王冠楠;;有向网络重叠社区的快速划分算法[J];计算机科学;2014年S1期

4 卢风顺;宋君强;张理论;张卫民;任开军;朱小谦;;面向全球数值天气预报模式的加权等积并行数据划分算法[J];计算机研究与发展;2012年04期

5 喻云峰;赖海涛;;一种基于随机搜索的黑洞二划分算法实现[J];科技广场;2006年04期

6 李晨;葛声;;一种重叠可信社团划分算法的设计与实现[J];微计算机信息;2011年09期

7 李孝伟;陈福才;刘力雄;;一种融合节点与链接属性的社交网络社区划分算法[J];计算机应用研究;2013年05期

8 牛建军;刘上乾;韩宝君;任宝文;;同心圆检测中的区域划分算法[J];光子学报;2006年12期

9 吕德奎;;聚合算法在电力GIS中的应用[J];电力信息化;2012年05期

10 王晓芳;贾宗维;;一种新的图划分算法在PPI网络模块化中的研究[J];山西农业大学学报(自然科学版);2012年06期

中国重要会议论文全文数据库 前4条

1 王玲娜;李兴明;;基于最小支撑树的通用区域划分算法[A];2008年中国西部青年通信学术会议论文集[C];2008年

2 徐丹丹;章勇;;一种基于节点度更新的簇划分算法[A];2008通信理论与技术新发展——第十三届全国青年通信学术会议论文集（下）[C];2008年

3 刘培强;谢青松;朱大铭;;用于基因表达谱数据聚类分析的贪心图划分算法研究[A];2006年全国理论计算机科学学术年会论文集[C];2006年

4 刘华伟;全庆一;;能量有效的基于连通度的分布式簇划分算法[A];2011年全国通信安全学术会议论文集[C];2011年

中国硕士学位论文全文数据库 前10条

1 许金凤;大规模动态自适应图划分算法[D];宁波大学;2015年

2 周爽;面向BSP模型的图数据划分算法的设计与实现[D];东北大学;2013年

3 吴磊;复杂网络的社团划分算法研究[D];太原理工大学;2016年

4 宋俐;基于模糊聚类的社团划分算法研究[D];太原理工大学;2016年

5 刘文杰;基于点分割的平衡图划分算法研究及其在Spark上的实现[D];兰州大学;2016年

6 吴迪;基于微博关注及转发关系的社区划分算法的改进与实现[D];吉林大学;2016年

7 滕跃;面向胚胎型仿生硬件的电路划分算法研究[D];哈尔滨工业大学;2016年

8 康晓慧;复杂网络重叠社团划分算法研究与实现[D];电子科技大学;2016年

9 顾宏博;基于云聚合理论的社区划分算法与应用研究[D];南京邮电大学;2016年

10 徐仁和;社交网络的非重叠社团划分算法研究[D];重庆大学;2016年

，

本文编号：911694