Graph partitioning strategies for efficient BFS in shared-nothing parallel systems

Victor Muntes-Mulero 1 Norbert Martínez-Bazán 1 Josep-Lluís Larriba-Pey 1 Esther Pacitti 2 Patrick Valduriez 2
2 ZENITH - Scientific Data Management
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Traversing massive graphs as efficiently as possible is essential for many applications. Many common operations on graphs, such as calculating the distance between two nodes, are based on the Breadth First Search traversal. However, because of the exhaustive exploration of all the nodes and edges of the graph, this operation might be very time consuming. A possible solution is distributing the graph among the nodes of a shared-nothing parallel system. Nevertheless, this operation may generate a large amount of inter-node communication. In this paper, we propose two graph partitioning techniques and improve previous distributed versions of BFS in order to reduce this communication.
Type de document :
Communication dans un congrès
WAIM: Web-Age Information Management, Jul 2010, Jiuzhaigou Valley, China. WAIM 2010 International Workshops: IWGD 2010, XMLDM 2010, WCMT 2010., LNCS (6185), pp.13-24, 2010, Revised selected papers. 〈10.1007/978-3-642-16720-1_2〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00830934
Contributeur : Maximilien Servajean <>
Soumis le : mardi 10 avril 2018 - 18:38:28
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Identifiants

Collections

Citation

Victor Muntes-Mulero, Norbert Martínez-Bazán, Josep-Lluís Larriba-Pey, Esther Pacitti, Patrick Valduriez. Graph partitioning strategies for efficient BFS in shared-nothing parallel systems. WAIM: Web-Age Information Management, Jul 2010, Jiuzhaigou Valley, China. WAIM 2010 International Workshops: IWGD 2010, XMLDM 2010, WCMT 2010., LNCS (6185), pp.13-24, 2010, Revised selected papers. 〈10.1007/978-3-642-16720-1_2〉. 〈lirmm-00830934〉

Partager

Métriques

Consultations de la notice

243