计算机科学与探索Issue(1)：40-50,11.DOI:10.3778/j.issn.1673-9418.1305052
BHP：面向BSP模型的负载均衡Hash图数据划分
BHP:BSP Model Oriented Hash Graph Data Partition with Load Balancing
摘要
Abstract
Graph data partition is a critical technical problem in the large-scale graph processing system based on bulk synchronous parallel (BSP) model. Traditional graph partition technology requires many iterations, the time com-plexity is too high, and the partition results don’t have the mapping information from vertexes to partitions. So those algorithms are not suitable for partitioning graph data for the BSP model based systems. This paper presents a new Hash partition algorithm that implements load balance, called balanced Hash partition (BHP). In order to achieve the balance of the number of out degrees in each partition as much as possible, the concept of virtual bucket is introduced. Then these virtual buckets are reorganized into desired partitions by using a greedy algorithm. In this way, the algorithm can ensure the load balance of each partition. At the same time, the data localization strategy makes the data on the split locate on the corresponding node as much as possible. So, the overhead of data migration during the data loading can be reduced. This paper does some experiments to compare the performance between BHP and the classic Hash algorithm from multiple aspects. The results show that the BHP algorithm can improve the job executing efficiency,reduce the number of sending messages, and effectively solve the problems of load imbalance and too many interac-tive edges among partitions.关键词
BSP模型/图划分/分布式系统/负载均衡/虚拟桶Key words
bulk synchronous parallel (BSP)/graph partition/distributed system/load balance/virtual bucket分类
信息技术与安全科学引用本文复制引用
周爽,鲍玉斌,王志刚,冷芳玲,于戈,邓超,郭磊涛..BHP：面向BSP模型的负载均衡Hash图数据划分[J].计算机科学与探索,2014,(1):40-50,11.基金项目
The National Natural Science Foundation of China under Grant Nos.61033007,61173028(国家自然科学基金) （国家自然科学基金）
the Fundamental Research Funds for the Central Universities of China under Grant No. N100704001(中央高校基本科研业务费专项资金) （中央高校基本科研业务费专项资金）
the Ministry of Education of China and China Mobile Foundation under Grant No. MCM20125021(教育部-中国移动科研基金) （教育部-中国移动科研基金）
