7_计算机科学与探索_2014_图划分_BHP1

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-

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

Pregel

Graph