Adaptive partitioning for large-scale dynamic graphs

Luis M. Vaquero*, Felix Cuadrado, Dionysios Logothetis, Claudio Martella

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

31 Citations (Scopus)

Abstract

In the last years, large-scale graph processing has gained increasing attention, with most recent systems placing particular emphasis on latency. One possible technique to improve runtime performance in a distributed graph processing system is to reduce network communication. The most notable way to achieve this goal is to partition the graph by minimizing the number of edges that connect vertices assigned to different machines, while keeping the load balanced. However, real-world graphs are highly dynamic, with vertices and edges being constantly added and removed. Carefully updating the partitioning of the graph to reflect these changes is necessary to avoid the introduction of an extensive number of cut edges, which would gradually worsen computation performance. In this paper we show that performance degradation in dynamic graph processing systems can be avoided by adapting continuously the graph partitions as the graph changes. We present a novel highly scalable adaptive partitioning strategy, and show a number of refinements that make it work under the constraints of a large-scale distributed system. The partitioning strategy is based on iterative vertex migrations, relying only on local information. We have implemented the technique in a graph processing system, and we show through three real-world scenarios how adapting graph partitioning reduces execution time by over 50% when compared to commonly used hash-partitioning.

Original languageEnglish
Title of host publication2014 IEEE 34th International Conference on Distributed Computing Systems (ICDCS 2014)
Subtitle of host publicationProceedings of a meeting held 30 June - 3 July 2014, Madrid, Spain
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages144-153
Number of pages10
ISBN (Electronic)9781479951697
ISBN (Print)9781479951703
DOIs
Publication statusPublished - Oct 2014
Event2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014 - Madrid, Spain
Duration: 30 Jun 20143 Jul 2014

Publication series

Name
ISSN (Print)1063-6927

Conference

Conference2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014
CountrySpain
CityMadrid
Period30/06/143/07/14

Keywords

  • adaptive partitioning
  • dynamic graphs
  • Graph processing

Fingerprint Dive into the research topics of 'Adaptive partitioning for large-scale dynamic graphs'. Together they form a unique fingerprint.

Cite this