论文部分内容阅读
随着社会的高速发展,图数据变的越来越大,如facebook、微博、人人网等社交网络及创新基因序列等。传统的图处理系统在处理这些基于大数据集上的计算时都存在明显的短板,因此,急需开发一种高效、稳定的处理系统用于海量图数据的计算。图数据划分是基于BSP编程模型的大规模图处理系统需要解决的重要问题之一。特别在云计算环境下,由于数据规模过大,更需要将图数据划分为多个分区,交由集群中的计算节点并行处理。然而,现有的图划分方法大多需要多次迭代,时间复杂度过高,且结果不保留顶点到分区的映射,并不适用于BSP模型下的图数据划分。此外,在实际应用中,由于图数据基本固定,重复进行图划分操作降低了系统运行效率。因此,如何实现快速的划分以及如何进行划分管理,具有极大的挑战。为此,项目组基于BSP模型、借鉴云计算编程模型Hadook,开发了可进行大图计算的图处理系统BC-BSP。本文主要设计并实现系统的数据划分模块下的数据划分算法。主要贡献如下：(1)设计基于启发式规则的划分算法DHP和C-DHP。在这两种算法中引入了顶点收益的概念。前者引入了虚拟桶的概念,两次应用顶点收益策略,达到保留原数据局部拓扑性的效果。后者对其进行了优化：首先对图数据进行聚类,再使用顶点放置收益策略进行划分,最后进行在线合并。(2)实现分区管理,为后续合并和计算打下基础。(3)设计实现了在线合并算法,并实现了分区的一次划分多次使用。在BC-BSP系统启动时获取本次作业的任务数,并将分区进行在线合并,达到一次划分、多次使用的目的。(4)通过改写InputFormat类,将上述算法集成到BC-BSP系统中,实现了将多个文件作为一个分片输入。将本文提出的数据划分算法和一次划分多次使用的思想应用于BC-BSP系统中,通过实验证明,其完成了BC-BSP系统中图划分模块的功能,具有良好的可扩展性和稳定性。实验表明C-DHP算法交互边比Hash算法减少25%以上,作业运行时间比Hash算法快40%左右。