基于BSP模型的大图处理系统数据划分模块的设计与实现

来源 :东北大学 | 被引量 : 3次 | 上传用户:fishingalone
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
由于图数据量的增长在图上计算提取知识变得越来越具有挑战性。现在的图数据集变的非常巨大,如FaceBook、twitter、人人网等的数据。传统的图处理工具难以完成这些计算。急需开发新的处理系统用于海量图数据的计算。Google基于BSP批量同步模型开发了Pregel大图处理系统。这为设计开发图处理系统提供了思路。而当今最为流行的云计算技术为此提供了技术支持。然而任何图处理系统都不能避免一个早已存在的问题即图分割的问题。特别是云计算环境下分布式并行处理需要对处理的数据进行划分为多个分区。数据被分割为多个分区由集群中的计算节点并行处理。如何实现一个好的划分依然是一个难点和极大的挑战。为了解决上述问题,我们借鉴分布式平行处理系统云计算编程模型Hadoop设计思路,基于BSP模型开发了一个可以进行大图处理的图处理系统。本文主要讨论系统其中数据划分模块设计与实现。本文主要贡献如下。第一,我们分析图计算特点,借鉴现有图处理系统的设计思路设计实现了数据划分模块。提供了完善的用户接口,用户可以灵活的设置。可以选择使用默认的划分策略或者根据接口定制他们自己的划分算法。已经整合到系统中并且工作良好;第二,我们实现了三个图数据划分算法,即基于MD5Hash的数据划分算法、针对取模Hash基于虚拟分区的平衡优化算法、Range划分算法;第三,我们实现了对多存储系统输入格式的支持。对比分析HDFS和HBase的存储设计的相似性,整合了HDFS及HBase输入格式并提供了统一的接口设计。提供了默认的输入格式,同时用户根据他们的需求定制自己的输入格式;第四,为图算法的实现提供了必备的支撑部件,如,基于RPC的多线程数据并行发送、环形缓冲区、全局同步及优化器等。实验结果和实际应用表明实现的大图处理系统中数据划分模块达到了系统设计的目标。具有良好的可扩展性和稳定性。我们从负载均衡、通信开销、时间开销三个方面对比分析了三种不同的数据划分算法的性能。结果表明优化的hash相对与未优化的具有较好的性能。数据集较好局部聚集特性的情况下Range划分算法性能最优。
其他文献
随着多核处理器的计算性能突飞猛进,成本不断降低,多核处理器已经广泛应用于嵌入式系统。另一方面,随着嵌入式系统性能的发展,图像处理技术也越来越多的应用于嵌入式系统。图像处
随着Internet技术的发展,WWW上积累了大量数据,成为世界上最大的数据源。但Web信息多以HTML格式发布,缺乏语义信息,造成大量的Web数据不能直接为应用程序直接使用。为了使大量的W
人类从自然界获得解决科学难题的灵感,借鉴自然界自身的规律,解决人类面临的科学问题已经成为现代科学研究中的一个非常新的研究思路。 本文就是在认识生物免疫系统运行机理
为了解决软件开发的复杂性问题,该文研究了模型驱动开发的核心思想,提出了一种敏捷模型驱动的多元层次软件开发方法.这种开发框架把软件开发划分为参考模型的元模型,参考模型
当今社会是一个信息社会,信息数据正以超乎人们想象的速度增长。信息对于人们来说是越来越重要,面对各种各样、庞大复杂的信息和数据,怎样安全地保存、及时地传输、快速地恢
Anycast是IPv6中提出的一种新型的网络服务,它在主机自动配置、网络负载均衡等方面的应用都非常广泛。对Anycast路由协议进行研究是确保Anycast服务能否实现的关键,Anycast路由
网络与信息安全问题已经日益突出,黑客入侵、信息泄密以及病毒泛滥所带来的危害引起了世界各地的高度重视。世界各国开始将网络与信息安全提高到国家安全的高度加以重视和研
随着互联网时代信息技术的深入应用,信息的来源日益增多,数据规模呈现急剧增长的趋势。面对海量的数据,越来越多的企业或组织开始重视数据的存储应用,数据仓库在这方面的应用
随着校园网的迅猛发展,基于校园网的应用越来越多,黑客攻击事件频有发生.如何确保校园网信息的真实、完整、保密和不可否认等信息安全问题己成为广泛关注的焦点.采用PKI技术
软件复用是解决软件危机,提高软件生产效率和质量的现实可行的技术。领域工程是可复用资源基础设施建设的主要技术手段。领域分析是领域工程的前期阶段,是获取领域需求规约的关