An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing

Verma, Shiv; Leslie, Luke M.; Shin, Yosub; Gupta, Indranil

Permalink

https://hdl.handle.net/2142/91657 Copy

Description

Title

An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing

Author(s)

• Verma, Shiv
• Leslie, Luke M.
• Shin, Yosub
• Gupta, Indranil

Issue Date

2016-10-14

Keyword(s)

• Graph
• Partitioning
• Distributed Systems
• Evaluation
• Analysis

Abstract

In this paper, we study the problem of choosing among partitioning strategies in distributed graph processing systems.To this end, we evaluate and characterize both the performance and resource usage of different partitioning strategies under various popular distributed graph processing systems, applications, input graphs, and execution environments. Through our experiments, we found that no single partitioning strategy is the best fit for all situations, and that the choice of partitioning strategy has a significant effect on resource usage and application run-time. Our experiments demonstrate that the choice of partitioning strategy depends on (1) the degree distribution of input graph, (2) the type and duration of the application, and (3) the cluster size. Based on our results, we present rules of thumb to help users pick the best partitioning strategy for their particular use cases. We present results from each system, as well as from all partitioning strategies implemented in one common system (PowerLyra).

Type of Resource

• text
• image

Language

en

Permalink

http://hdl.handle.net/2142/91657

Owning Collections