Comparison of Edge Partitioners for Graph Processing

Hlib Mykhailenko 1 Fabrice Huet 2 Giovanni Neglia 1
1 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
2 SCALE - Safe Composition of Autonomous applications with Large-SCALE Execution environment
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Deploying graph on a cluster requires its partitioning into a number of subgraphs, and assigning them to different machines. Two partitioning approaches have been proposed: vertex partitioning and edge partitioning. In the edge partitioning approach edges are allocated to partitions. Recent studies show that, for power-law graphs, edge partitioning is more effective than vertex partitioning. In this paper we provide an overview of existing edge partitioning algorithms. However, based only on published work, we cannot draw a clear conclusion about the relative performances of these partitioners. For this reason, we compare all the edge partition-ers currently available for GraphX. Our preliminary results suggest that Hybrid-Cut partitioner provides the best performance.
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01401338
Contributor : Hlib Mykhailenko <>
Submitted on : Wednesday, November 23, 2016 - 10:58:07 AM
Last modification on : Thursday, December 6, 2018 - 8:56:01 AM
Long-term archiving on : Tuesday, March 21, 2017 - 3:16:57 AM

File

surveyHAL.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01401338, version 1

Collections

Citation

Hlib Mykhailenko, Fabrice Huet, Giovanni Neglia. Comparison of Edge Partitioners for Graph Processing. CSCI 2016 - International Conference on Computational Science and Computational Intelligence, Dec 2016, Las Vegas, United States. ⟨hal-01401338⟩

Share

Metrics

Record views

265

Files downloads

332