Files
Abstract
Distributed vertex-centric graph processing systems have acquired significant popularity in recent years for processing massive graphs. The manner in which graph data is partitioned and placed on the computational nodes has considerable impact on the performance of distributed vertex-centric clusters. In this dissertation, we propose a novel model for analyzing the performance of such clusters when different partitioning strategies are applied to the computation of various graph algorithms and also propose various metrics for measuring performance of such clusters. Moreover, in this research we consider partitioning of many real world graph data sets, which are dynamic and can essentially be modeled as Time-Evolving Graphs (TEGs). We propose a unique, continuous and multi-cost sensitive approach for partitioning dynamic graphs. Our approach incorporates novel cost functions that take into account major factors that impact the performance of big graph processing clusters. We also present incremental algorithms to efficaciously handle various types of graph dynamics.