For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Method for Graph Repartitioning in Distributed Environments
He LI YanNa LIU XuHua WANG LiangCai SU Hang YUAN JaeSoo YOO
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2020/07/01
Online ISSN: 1745-1361
Type of Manuscript: LETTER
Category: Data Engineering, Web Information Systems
large graph, dynamic graph, graph partitioning, graph repartitioning, graph algorithms,
Full Text: PDF(463.4KB)>>
Due to most of the existing graph repartitioning methods are known for poor efficiency in distributed environments. In this paper, we introduce a new graph repartitioning method with two phases in distributed environments. In the first phase, a local method is designed to identify all the potential candidate vertices that should be moved to the other partitions at once in each partition locally. In the second phase, a streaming graph processing model is adopted to reassign the candidate vertices to achieve lightweight graph repartitioning. During the reassignment of the vertex, we propose an objective function to balance both the load balance and the number of crossing edges among the distributed partitions. The experimental results with a large set of real word and synthetic graph datasets show that the communication cost can be reduced by nearly 1 to 2 orders of magnitude compared with the existing methods.