With the social networks growing, graph datasets have become tremendous. We have found that partitioning a large graph into several partitions to execute some graph algorithms would improve the performance of the procedure. Distributed systems such as Pregel, Giraph, etc. are widely used. In these systems, usually one working node is associated with one partition. In this literature, static and dynamic graph partitions are studied. The static one corresponds to the initialization before the runtime of the processing of algorithm, while the dynamic one means that the dynamic repartitioning of the graph will be executed when the algorithm is executing.

We propose and implement an efficient dynamic repartition method on Giraph. The key of our method is to achieve a balanced workloa...[ Read more ]

With the social networks growing, graph datasets have become tremendous. We have found that partitioning a large graph into several partitions to execute some graph algorithms would improve the performance of the procedure. Distributed systems such as Pregel, Giraph, etc. are widely used. In these systems, usually one working node is associated with one partition. In this literature, static and dynamic graph partitions are studied. The static one corresponds to the initialization before the runtime of the processing of algorithm, while the dynamic one means that the dynamic repartitioning of the graph will be executed when the algorithm is executing.

We propose and implement an efficient dynamic repartition method on Giraph. The key of our method is to achieve a balanced workload of the working nodes, based on the historical information. In addition, we point out that a static locally greedy initialization performs better than the hash initialization method when considering the total execution time. Extensive experiments were conducted on both the real and the synthetic datasets.