eCite Digital Repository

SDP: Scalable Real-time Dynamic Graph Partitioner

Citation

Patwary, MAK and Garg, S and Battula, SK and Kang, BH, SDP: Scalable Real-time Dynamic Graph Partitioner, IEEE Transactions on Services Computing ISSN 1939-1374 (2021) [Refereed Article]

Copyright Statement

Copyright 2021 IEEE

DOI: doi:10.1109/TSC.2021.3137932

Abstract

The time-evolving large graph has received attention due to it's participation in real-world applications such as social networks and PageRank calculation. It is necessary to partition a large-scale dynamic graph in a streaming manner in order to overcome the memory bottleneck while partitioning the computational load. Reducing network communication and balancing the load between the partitions are the criteria for achieving effective run-time performance in graph partitioning. Moreover, an optimal resource allocation is needed to utilise the resources while storing the graph streams into the partitions. A number of existing partitioning algorithms have been proposed to address the above problem. However, these partitioning methods are incapable of scaling the resources and handling the stream of data in real-time. In this study, we propose a dynamic graph partitioning method called Scalable Dynamic Graph Partitioner(SDP) using the streaming partitioning technique. The SDP contributes a novel vertex assigning method, communication-aware balancing method, and a scaling technique in order to produce an efficient dynamic graph partitioner. Experiment results show that the proposed method achieves up to 90% reduction of communication cost and 60%-70% balancing the load dynamically, compared with previous algorithms. Moreover, the proposed algorithm significantly reduces the execution time during partitioning.

Item Details

Item Type:Refereed Article
Keywords:cloud computing, graph analysis, dynamic graph, streaming partitioning, scalable
Research Division:Information and Computing Sciences
Research Group:Distributed computing and systems software
Research Field:Distributed systems and algorithms
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Computer systems
UTAS Author:Patwary, MAK (Mr Md Anwarul Patwary)
UTAS Author:Garg, S (Dr Saurabh Garg)
UTAS Author:Kang, BH (Professor Byeong Kang)
ID Code:148546
Year Published:2021
Deposited By:Information and Communication Technology
Deposited On:2022-01-21
Last Modified:2022-05-18
Downloads:0

Repository Staff Only: item control page