面向BSP模型的图数据划分算法的设计与实现

摘要

随着社会的发展，各种各样的图数据集变的越来越大，如微博、Twitter、人人网等社交网络及通信网络等。传统的图处理工具很难完成这些基于大数据集上的计算，因此，急需开发一种新的处理系统用于海量图数据的计算。Google基于BSP模型提出的Pregel大图处理系统，为设计和开发大规模图处理系统提供了思路，著名的云计算为此提供了技术支持。图数据划分对基于BSP编程模型的大规模图处理系统是一个不能避免的问题。特别在云计算环境下，更需要将图数据划分为多个分区，交由集群中的计算节点并行处理。然而，传统的图划分技术大多需要多次迭代，时间复杂度过高，且结果不保留顶点到分区的映射，所以并不适用于BSP模型下的图数据划分。因此，如何实现一个好的快速的划分，具有极大的挑战。
　　为此，在之前的工作中，项目组基于BSP模型、借鉴云计算编程模型Hadoop，开发了一个可以进行大图计算的图处理系统BC-BSP。本文主要设计并实现系统的数据划分模块下的数据划分算法。主要贡献如下：(1)提出一个BSP作业运行代价模型，据此分析了作业运行时各个阶段的时间开销由哪些因素决定。(2)设计实现了三个算法:一，基于采样直方图的数据划分算法(S amp le)。提交作业时，从输入数据集采样一定数量的记录，并据此建立直方图。划分数据时，将落在相应直方图中的数据放到直方图对应的分区中。这样，近似保证了分区内顶点数的均衡。这种划分算法能将同一网站的所有页面划分到一个分区。二，针对出度的均衡Hash数据划分算法(BHP)。该算法引入了虚拟桶的概念，使用贪心算法将虚拟桶重组为分区，保证了每个分区负载均衡。同时，本地化算法减小了数据加载时的数据迁移开销。三，边聚簇的BHP数据划分算法(ECBHP)。该算法使用EC启发式规则，评估了虚拟桶到各分区的拓扑密度，据此进行虚拟桶的重组，保证分区内的图顶点具有较高的耦合度，分区间具有较低的耦合度。
　　将本文提出的三种数据划分算法应用于BC-BSP系统中，通过实验证明，三种算法完成了BC-BSP系统中图划分模块的功能，具有良好的可扩展性和稳定性。实验表明，Sample算法较Hash算法达到了分区内顶点数的均衡，作业运行时间比Hash算法提高了10％以上。BHP和ECBHP划分算法相较于前两种算法实现了边数的平衡，同时有效的减少了交互边的数量，在作业运行时间上，比Hash算法提高了30％以上。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 国内外研究现状

1．3 本文主要工作

1．4 本文组织结构

第2章 相关技术概述

2．1 Hadoop简介

2．1．1 分布式文件系统

2．1．2 MapReduce编程模型

2．1．3 Zookeeper

2．2 BSP模型

2．2．1 BSP模型介绍

2．2．2 BSP模型特点及评价

2．3 图划分技术概述

2．3．1 图的基本概念

2．3．2 图划分问题描述

2．3．3 经典的图划分算法及负载均衡算法介绍

2．3．4 大图处理系统中图划分技术介绍

2．4 本章小结

第3章 BC-BSP系统及数据划分模块简介

3．1 系统体系结构

3．2 系统处理流程

3．3 数据划分子模块

3．4 本章小结

第4章 基于采样直方图的数据划分算法

4．1 算法概述

4．2 直方图和Trie树的创建

4．2．1 基于采样的直方图的创建

4．2．2 Trie树的创建

4．3 Sample划分算法

4．3．1 算法详述

4．3．2 Sample划分算法复杂度分析

4．4 采样量的确定

4．5 实验与分析

4．5．1 参数确定

4．5．2 负载均衡测试

4．6 本章小结

第5章 针对出度的均衡Hash划分 算法

5．1 经典随机Hash划分算法介绍

5．2 BSP作业运行的代价模型

5．3 实现负载均衡的Hash数据划分算法

5．3．1 BHP划分算法简介

5．3．2 BHP戈U分算法详述

5．3．3 BHP划分算法复杂度分析

5．4 边聚簇的BHP数据划分算法

5．4．1 EC启发式规则

5．4．2 ECBHP划分算法详述

5．4．3 ECBHP划分算法复杂度分析

5．5 BHP和ECBHP划分算法与随机Hash算法的性能分析

5．6 实验与分析

5．6．1 分区扩大倍数测试

5．6．2 负载均衡测试

5．7 本章小结

第6章 划分算法在BC-BSP系统的性能评估

6．1 PageRank测试算法

6．2 实验环境和测试数据

6．3 不同划分算法的性能评估

6．3．1 通信代价测试

6．3．2 时间测试

6．4 本章小结

第7章 总结与展望

7．1 本文工作总结

7．2 未来工作展望

参考文献

致谢

攻硕期间发表的论文和参加的项目