The search functionality is under construction.
The search functionality is under construction.

An Efficient Method for Graph Repartitioning in Distributed Environments

He LI, YanNa LIU, XuHua WANG, LiangCai SU, Hang YUAN, JaeSoo YOO

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Information Vol.E103-D No.7 pp.1773-1776
Publication Date
2020/07/01
Publicized
2020/04/20
Online ISSN
1745-1361
DOI
10.1587/transinf.2020EDL8018
Type of Manuscript
LETTER
Category
Data Engineering, Web Information Systems

Authors

He LI
  Xidian University
YanNa LIU
  Xidian University
XuHua WANG
  Xidian University
LiangCai SU
  Xidian University
Hang YUAN
  Xidian University
JaeSoo YOO
  Chungbuk National University

Keyword