IEICE TRANSACTIONS on Information
An Efficient Method for Graph Repartitioning in Distributed Environments
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
He LI, YanNa LIU, XuHua WANG, LiangCai SU, Hang YUAN, JaeSoo YOO, "An Efficient Method for Graph Repartitioning in Distributed Environments" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 7, pp. 1773-1776, July 2020, doi: 10.1587/transinf.2020EDL8018.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020EDL8018/_p
Copy
@ARTICLE{e103-d_7_1773,
author={He LI, YanNa LIU, XuHua WANG, LiangCai SU, Hang YUAN, JaeSoo YOO, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient Method for Graph Repartitioning in Distributed Environments},
year={2020},
volume={E103-D},
number={7},
pages={1773-1776},
abstract={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.},
keywords={},
doi={10.1587/transinf.2020EDL8018},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - An Efficient Method for Graph Repartitioning in Distributed Environments
T2 - IEICE TRANSACTIONS on Information
SP - 1773
EP - 1776
AU - He LI
AU - YanNa LIU
AU - XuHua WANG
AU - LiangCai SU
AU - Hang YUAN
AU - JaeSoo YOO
PY - 2020
DO - 10.1587/transinf.2020EDL8018
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2020
AB - 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.
ER -
English
