Handling limits of high degree vertices in graph processing using MapReduce and Pregel

Mohamad Al Hajj Hassan (1) , Mostafa Bamha (2)

1 LIU - Lebanese International University
2 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans

Even if Pregel scales better than MapReduce in graph processing by reducing iteration's disk I/O, while offering an easy programming model using " think like vertex " approach, large scale graph processing is still challenging in the presence of high degree vertices: Communication and load imbalance among processing nodes can have disastrous effects on performance. In this paper, we introduce a scalable MapReduce graph partitioning approach for high degree vertices using a master/slave partitioning allowing to balance communication and computation among processing nodes during all the stages of graph processing. Cost analysis and performance tests of this partitioning are given to show the effectiveness and the scalability of this approach in large scale systems.

Mots clés: Graph processing; High degree vertices; Data skew; MapReduce programming model; Pregel; Distributed file systems

Domaines: Informatique

Mohamad Al Hajj Hassan, Mostafa Bamha. Handling limits of high degree vertices in graph processing using MapReduce and Pregel . [Research Report] Université Orléans, INSA Centre Val de Loire, LIFO EA 4022, France. 2017. ⟨hal-01468723⟩