Graph Partitioning Strategies for Efficient BFS in Shared-nothing Parallel Systems*
par Victor Muntés-Mulero UPC, Barcelona

Jeudi 24 mars à 14h
Salle des Séminaires, LIRMM

Résumé
The increasing interest for analyzing graph-like information in many different areas has reinforced the need for handling massive graphs very efficiently. Despite the diversity of scenarios, a comprehensive analysis of the great majority of the queries performed on massive graphs reveals a subset of fundamental common operations upon which most complex queries rely. Among these operations, the Breath-First Search algorithm (BFS) is widely used in numerous applications (finding the shortest distance between two vertices, finding the set of vertices at a certain distance of a given source or computing the diameter of a graph).
In this talk, we focus on the parallelization of the BFS operation on very large graphs containing up to millions of vertices and edges. We aim at studying the effect of different graph partitioning methods on the overall communication when executing a BFS traversal on very large graphs. For this, we propose two new heuristic strategies which aim at reducing the number of vertices whose traversal produces communication between nodes. We also show how other queries based on BFS benefit from the different partitionings.

*Joint work with Norbert Martınez-Bazan, Josep-Lluıs Larriba-Pey, Esther Pacitti, and Patrick Valduriez