Dynamic Graph Partitioning Scheme for Supporting Load Balancing in Distributed Graph Environments

As dynamic graph data have been actively used, incremental graph partition schemes have been studied to efficiently store and manage large graphs. In this paper, we propose a vertex-cut based novel incremental graph partitioning scheme that supports load balancing in a distributed environment. The p...

Full description

Saved in:
Bibliographic Details
Published in:IEEE access 2021, Vol.9, p.65254-65265
Main Authors: Choi, Dojin, Han, Jinsu, Lim, Jongtae, Han, Jinsuk, Bok, Kyoungsoo, Yoo, Jaesoo
Format: Article
Language:English
Subjects:
Distributed databases
Distributed processing
graph partitioning
graph stream
Graphs
hot data
Indexes
Load balancing
Load management
Load modeling
Partitioning
Partitions (mathematics)
Performance evaluation
Real-time systems
Stress concentration
Throughput
vertex-cut partitioning
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:As dynamic graph data have been actively used, incremental graph partition schemes have been studied to efficiently store and manage large graphs. In this paper, we propose a vertex-cut based novel incremental graph partitioning scheme that supports load balancing in a distributed environment. The proposed scheme chooses the load of each node that considers its storage utilization and throughput as the partitioning criterion. The proposed scheme defines hot data that means a particular vertex frequently searched among graphs requested by queries. We manage and utilize hot data for graph partitioning. Finally, we perform vertex-cut based dynamic graph partitioning by using a vertex replication index, the load each node, and hot data to distribute the load evenly in a distributed environment. In order to verify the superiority of the proposed partitioning scheme, we compare it with the existing partitioning schemes through a variety of performance evaluations.
ISSN:2169-3536
2169-3536
DOI:10.1109/ACCESS.2021.3075457