A Log-based Dynamic Repartition Method For Vertex-cut Model In Pregel-like System

MPhil Thesis Defence


Title: "A Log-based Dynamic Repartition Method For Vertex-cut Model In 
Pregel-like System"

By

Mr. Chengxi YANG


Abstract

With the social networks growing, graph datasets have become tremendous. 
We have found that partitioning a large graph into several partitions to 
execute some graph algorithms would improve the performance of the 
procedure. Distributed systems such as Pregel, Giraph, etc. are widely 
used. In these systems, usually one working node is associated with one 
partition. In this literature, static and dynamic graph partitions are 
studied. The static one corresponds to the initialization before the 
runtime of the processing of algorithm, while the dynamic one means that 
the dynamic repartitioning of the graph will be executed when the 
algorithm is executing.

We propose and implement an efficient dynamic repartition method on 
Giraph. The key of our method is to achieve a balanced workload of the 
working nodes, based on the historical information. In addition, we point 
out that a static locally greedy initialization performs better than the 
hash initialization method when considering the total execution time. 
Extensive experiments were conducted on both the real and the synthetic 
datasets.


Date:			Monday, 12 December 2016

Time:			10:00am - 12:00noon

Venue:			Room 2129C
 			Lift 19

Committee Members:	Dr. Raymond Wong (Supervisor)
 			Dr. Wilfred Ng (Chairperson)
 			Dr. Pan Hui


**** ALL are Welcome ****