【作者】 王倩；

【导师】 鲍玉斌；

【作者基本信息】 东北大学 ， 计算机系统结构， 2014， 硕士

【摘要】 随着社会的高速发展,图数据变的越来越大,如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%左右。更多还原

【Abstract】 With the rapid development of society, data sets become bigger and bigger, such as facebook, weibo, renren and other social network and innovation gene sequence, etc. Traditional graph processing system in dealing with these based on the calculation on the large data set has obvious short, therefore, we need to develop a highly efficient and stable mass graph data processing system that is used for calculation. Graph data classification is one of the important problems that base on a BSP programming model of large-scale processing system need to be solved. Especially in cloud computing environment, due to the large data size, more graph data need to be divided into multiple partitions, and parallel processing on the cluster computing nodes. However, most existing methods of graph partition need multiple iterations, time complexity is much too high, and the result does not retain the map from vertices to the partition, which is not suitable for BSP model. In addition, in practical application, due to the graph data is basic fixed, repeated graph partition operation reduces the system efficiency. Therefore, how to achieve rapid division as well as how to manage partition has a great challenge.Therefore, we developed BC-BSP system for large computing image processing, which is based on Hadoop cloud computing programming model and the BSP model. In this thesis, we design and implement the system of data classification under the module of data partitioning, the main contributions are as follows:(1) Designed and released DHP, C-DHP graph partition algorithm that based on heuristic rules. In these two kinds of algorithm, we introduced the concept of vertex earnings. The former introduced the concept of virtual barrels, twice applicating vertex income strategies, retains the original data of local topology. The latter for DHP’s optimized:first clustering figure data, then using vertex placed strategy, at last doing the online merged, which provides support for dividing. (2) To manage the partitions, lay the foundation for mergering partitions and calculation. (3) Put forward the idea of divided one time and used multiple times and design the online combiming algorithm. We need to get assignment task when system startup, and merge partitions online, to achieve the purpose. (4) By rewriting class InputFormat, we integrate the above algorithms into BC-BSP system and realized making multiple files as one input split.Though the extensive experiments, the partition algorithm and the online combining proposed in this thesis can finish the function of graph partition of BC-BSP system.The experiment indicates that the cut in C-DHP reduced 25% than Hash, the running time was faster about 40%.更多还原