101. Network-Optimized Distributed Memory Parallel Breadth-First Search
Authors: Praveen Sharma (University of Southern California)
Abstract: Graphs are a very common modeling tool used for many applications including mapping relations in physical, social or information systems. In the worst case, the complexity of Breadth-first search (BFS) is linear in the number of edges and vertices, and the conventional top-down approach always takes as much time as the worst case. The bottom-up approach recently proposed manages to cut down the complexity all the way to the number of vertices in the best case, which is typically at least an order of magnitude less than the number of edges. However these algorithms can better exploit the network usage in terms of the time spent transmitting. In this paper, we propose an improved version of the direction-optimized distributed breadth-first search algorithm to further reduce the network traffic and improve performance in a multi-processor environment. Our implementation reduces network traffic by 11% and results in general speedups of 6-9%.
Two-page extended abstract: pdf