Bilkent University
Department of Computer Engineering
CS 590 SEMINAR
Streaming graph partitioning algorithm in multicore systems
Nazanin Jafari
MS Student
Computer Engineering Department
Bilkent University
Size of the graphs are growing each day and it is difficult to process them on a single machine, therefore, we need to partition them across the cluster of commodity machines. Streaming graph partitioning is a way to partition the large size graphs into partitions on the fly. Which means that we do not need to store the whole graph into memory beforehand thus we partition the graph as we get the graph info in random order. Two main characteristics of good graph partitioning are assigning vertices adjacent to each other in the same partition and having the equal number of vertices in all partitions. These two characteristics are usually in conflict and introducing an algorithm to provide these two characteristics at the same time is challenging. In this work, we propose a novel approach by taking into consideration the state of the art streaming partitioning algorithm (Linear Deterministic Greedy algorithm) to have the initial good quality partition. Then we apply the multilevel method to improve the partition quality. Additionally, we propose the parallel version of this method to increase the speed of partitioning.
DATE: 30 October, 2017, Monday @ 15:40
PLACE: EA-409