Near-Data Source Graph Partitioning

Recently, numerous graph partitioning approaches have been proposed to distribute a big graph to machines in a cluster for distributed computing. Due to heavy communication overhead, these graph partitioning approaches always suffered from long ingress times. Also, heavy communication overhead not only limits the scalability of distributed graph-parallel computing platforms but also reduces the overall performance of clusters. In order to address this problem, this work proposed a near-data source parallel graph partitioning approach noted as NDGP. In NDGP, an edge was preferentially distributed to the machine where it was stored. We implemented NDGP over two classic graph partitioning approaches, Random and Greedy, and one most recently proposed graph partitioning approach, OLPGP, and evaluated its effectiveness. Extensive experiments conducted on real-world data sets verified the effectiveness of NDGP on reducing the communication overhead in the graph partitioning process and demonstrated that NDGP does not induce additional communication and computing workload to the graph-distributed computing that follows.