eCite Digital Repository
Window-based streaming graph partitioning algorithm
Citation
Patwary, MAK and Garg, SK and Kang, BH, Window-based streaming graph partitioning algorithm, Proceedings of the 2019 Australasian Computer Science Week Multiconference (ACSW 2019), 29-31 January 2019, Sydney, Australia, pp. 1-10. ISBN 978-1-4503-6603-8 (2019) [Refereed Conference Paper]
Copyright Statement
Copyright 2019 Association for Computing Machinery
DOI: doi:10.1145/3290688.3290711
Abstract
In the recent years, the scale of graph datasets has increased to such a degree that a single machine is not capable of efficiently processing large graphs. Thereby, efficient graph partitioning is necessary for those large graph applications. Traditional graph partitioning generally loads the whole graph data into the memory before performing partitioning; this is not only a time consuming task but it also creates memory bottlenecks. These issues of memory limitation and enormous time complexity can be resolved using stream-based graph partitioning. A streaming graph partitioning algorithm reads vertices once and assigns that vertex to a partition accordingly. This is also called an one-pass algorithm. This paper proposes an efficient window-based streaming graph partitioning algorithm called WStream. The WStream algorithm is an edge-cut partitioning algorithm, which distributes a vertex among the partitions. Our results suggest that the WStream algorithm is able to partition large graph data efficiently while keeping the load balanced across different partitions, and communication to a minimum. Evaluation results with real workloads also prove the effectiveness of our proposed algorithm, and it achieves a significant reduction in load imbalance and edge-cut with different ranges of dataset.
Item Details
| Item Type: | Refereed Conference Paper |
|---|---|
| Keywords: | streaming, graph partitioning |
| Research Division: | Information and Computing Sciences |
| Research Group: | Distributed computing and systems software |
| Research Field: | Networking and communications |
| Objective Division: | Information and Communication Services |
| Objective Group: | Communication technologies, systems and services |
| Objective Field: | Satellite technologies, networks and services |
| UTAS Author: | Patwary, MAK (Mr Md Anwarul Patwary) |
| UTAS Author: | Garg, SK (Dr Saurabh Garg) |
| UTAS Author: | Kang, BH (Professor Byeong Kang) |
| ID Code: | 132279 |
| Year Published: | 2019 |
| Web of Science® Times Cited: | 7 |
| Deposited By: | Information and Communication Technology |
| Deposited On: | 2019-05-01 |
| Last Modified: | 2020-05-18 |
| Downloads: | 0 |
Repository Staff Only: item control page