BHP：面向BSP模型的负载均衡Hash图数据划分

• 作者: 于戈 冷芳玲 周爽 王志刚 邓超 郭磊涛 鲍玉斌
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: BSP模型 图划分 分布式系统 负载均衡 虚拟桶
• 年，卷（期）: 2014,（1）
• 所属期刊栏目: 数据库技术
• 页码范围: 40-50
• 页数: 11页
• 分类号: TP311
• 字数: 9279字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1305052

摘要

图数据划分是基于BSP（bulk synchronous parallel）编程模型的大规模图处理系统中一个关键技术问题。传统的图划分技术需要多次迭代，时间复杂度过高，且划分结果不具有图顶点到分区的映射信息，因此这些算法并不适用于BSP模型下的数据划分。提出了一种新的面向BSP模型的负载均衡Hash数据划分算法（balanced Hash partition，BHP）。为了实现各个分区的出边数尽可能均衡，该算法引入了虚拟桶的概念，通过贪婪算法将虚拟桶重组为实际分区，保证了每个实际分区负载均衡，同时数据本地化策略使本分片上的数据尽可能地保留在本节点上，从而减小在数据加载时的数据迁移开销。从三个方面对比了BHP算法和经典Hash算法的性能，结果表明BHP算法能够提高作业的执行效率，减少消息发送的数量，有效解决了经典Hash算法的负载不均衡和分区间交互边过多的问题，当数据量变大时，效果尤为明显。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	于戈	东北大学信息科学与工程学院	426	6587	38.0	64.0
2	鲍玉斌	东北大学信息科学与工程学院	85	1496	22.0	36.0
3	冷芳玲	东北大学信息科学与工程学院	16	146	7.0	12.0
4	王志刚	东北大学信息科学与工程学院	5	49	3.0	5.0
5	邓超	中国移动通信研究院业务支撑研究所	5	39	3.0	5.0
6	周爽	东北大学信息科学与工程学院	3	14	1.0	3.0
7	郭磊涛	中国移动通信研究院业务支撑研究所	1	14	1.0	1.0