基于点分割的平衡图划分算法研究及其在Spark上的实现

发布时间：2017-07-16 17:06

  本文关键词：基于点分割的平衡图划分算法研究及其在Spark上的实现

  更多相关文章： 大数据 图划分 分布式计算 Spark 点分割

【摘要】：近年来,随着数据量的爆发式增长,相应地兴起了对大数据处理平台的研究热潮,Hadoop的出现使人们从传统的并行计算模型转向对Mapreduce计算模型的研究。为了满足数据挖掘和交互式实时查询的计算需求,进一步提高数据处理能力和效率,UC berkeley大学高性能计算实验室开发了Spark计算平台,Spark引入了RDD(Resilient Distributed Datasets)数据模型,大大提高了交互式计算和迭代计算的计算速度,使得Spark成为大数据处理的利器。大数据的核心处理之一就是图数据的处理,其中平衡图划分是图数据处理的一个重要组成部分。众所周知,平衡图划分是一个NP完全问题,应用非常广泛,研究领域包括生物网络,大规模集成电路设计,并行编程,负载均衡以及在线社交网络分析等。传统的图划分算法很多属于全局算法,即算法执行过程中需要遍历全图,过于依赖全图知识,不适合对大规模图数据的处理。基于对全图访问代价过大的考虑,2013年由Rahimian等人提出的一个去中心局部搜索算法JA-BE-JA,不需要进行中央协调,只通过局部知识来进行图的划分,极大的减少了集群中节点的通信开销,大大提高了该算法的可扩展性和对大规模图数据的处理能力。然而,JA-BE-JA算法仍然基于边分割的设计思想,最近研究发现对于自然图的处理,通过边分割虽然保证了各子集中节点数的平衡,但是各个子集中边的数量相差较大,同时该算法在多次迭代过程中容易陷入局部最优解。于是本文提出了基于点分割的改进算法JA-BE-JA-VC(Vertex-Cut),新的算法采用了点分割的思想,子集的平衡性由每个分区中边的个数来维持,而不是单纯把节点数来作为平衡性的标准。新的算法在对自然图划分时,划分产生的子集规模更加平衡。同时引入了模拟退火技术,增加了算法求解过程中的概率突跳性,避免陷入局部最优陷阱。本文最后对算法进行了评估,结果表明新算法不仅能够维持分区规模的平衡,同时对点的切分次数也相对较低,尤其对于服从幂律分布的现实数据进行处理时,基于点分割的算法设计思想具有很重要的借鉴意义。
【关键词】：大数据 图划分 分布式计算 Spark 点分割
【学位授予单位】：兰州大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP301.6
【目录】：

• 中文摘要3-4
• Abstract4-8
• 第一章 绪论8-14
• 1.1 研究背景及意义8-10
• 1.2 国内外研究现状10-12
• 1.3 论文的主要内容12
• 1.4 论文的组织结构12-14
• 第二章 相关理论技术14-33
• 2.1 图划分算法14-19
• 2.1.1 图划分的概念14-15
• 2.1.2 图划分算法分类15-19
• 2.2 Spark计算平台19-33
• 2.2.1 简介与组织架构20-21
• 2.2.2 弹性分布式数据集21-25
• 2.2.3 共享变量25-26
• 2.2.4 Spark编程接口26-29
• 2.2.5 工作原理29-31
• 2.2.6 Spark并行化技术31-33
• 第三章 JA-BE-JA算法及其改进33-45
• 3.1 JA-BE-JA算法33-36
• 3.1.1 JA-BE-JA基本思想33-34
• 3.1.2 交换节点选择策略34-35
• 3.1.3 JA-BE-JA存在的不足35-36
• 3.2 JA-BE-JA局部最优解的优化改进36-37
• 3.3 基于点分割的JA-BE-JA算法37-40
• 3.4 算法并行化实现40-45
• 第四章 实验与结果分析45-51
• 4.1 实验环境45-46
• 4.2 实验数据46
• 4.3 算法评估46-51
• 4.3.1 参数T和 δ 对算法的影响47-48
• 4.3.2 分区数k对算法的影响48-49
• 4.3.3 算法比较实验49-51
• 第五章 总结与展望51-53
• 5.1 工作总结51
• 5.2 未来展望51-53
• 参考文献53-57
• 研究生期间参与的项目57-58
• 致谢58

【相似文献】

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

1 郑丽丽;;图划分算法综述[J];科技信息;2014年04期

2 英海燕;高级综合中基于团划分算法的资源分配[J];现代情报;2003年12期

3 蒿杰;彭思龙;;多级划分算法的后处理与评价方法[J];小型微型计算机系统;2010年01期

4 居继龙，，李增瑞，李孝勖，任朗;时域有限差分方法中的网格非均匀划分算法[J];北京广播学院学报(自然科学版);1995年03期

5 肖侬，胡守仁，高洪奎，韩冰，宋辉;一个基于对象的程序划分算法[J];电子学报;1997年05期

6 徐久强;崔行兵;于群;赵海;;基于子团规模的社团划分算法与地理位置[J];东北大学学报(自然科学版);2012年11期

7 呙嘉妮,胡久乡,卢正鼎;有限元网格自动生成的并行区域划分算法[J];华中理工大学学报;1999年07期

8 张鲁峰,何连跃,李思昆;基于优化合并准则的团划分算法[J];电子学报;2001年08期

9 南国芳;李敏强;寇纪淞;;电路划分算法改进[J];电子测量技术;2006年01期

10 孙雨耕，宋学军，吴雪，许小满;电网络图主划分算法改进[J];天津大学学报;1995年05期

中国重要会议论文全文数据库 前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];南京邮电大学;2015年

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

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

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

7 马静;基于社交网络的社团划分算法研究[D];山东师范大学;2011年

8 韩明伟;超大规模集成电路划分算法研究[D];西安电子科技大学;2008年

9 辛娟娟;社区划分算法的研究与应用[D];北京林业大学;2015年

10 杜鹏飞;基于边的相似性的复杂网络社团划分算法研究[D];山东师范大学;2014年

本文编号：549664