University of Illinois Urbana-Champaign

An experimental comparison of partitioning strategies in distributed graph processing

Verma, Shiv

Content Files
VERMA-THESIS-2017.pdf

Permalink

https://hdl.handle.net/2142/97724

Description

Title
An experimental comparison of partitioning strategies in distributed graph processing
Author(s)
Verma, Shiv
Issue Date
2017-04-24
Director of Research (if dissertation) or Advisor (if thesis)
Gupta, Indranil
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Date of Ingest
2017-08-10T20:33:03Z
Keyword(s)
  • Distributed
  • Graph
  • Processing
  • Partitioning
Abstract
In this thesis, 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 two common systems (PowerLyra and GraphX).
Graduation Semester
2017-05
Type of Resource
text
Permalink
http://hdl.handle.net/2142/97724
Copyright and License Information
Copyright 2017 Shiv Verma

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois
Dissertations and Theses - Computer Science
Dissertations and Theses from the Siebel School of Computer Science