Breadth-first search (BFS) is an important kernel used by many graph algorithms. It is only a traversal order, and depending on what is recorded, it can return connectivity, distance, or parenthood. Due to its simplicity and importance to graph workloads, it has been used as the first and main kernel in the Graph 500 competition.
A typical BFS implementation will examine every edge in a directed graph once (twice if undirected). Most of these edge examinations will fail because the other end of the edge has already been visited. The bottom-up approach can be drastically faster by checking many fewer edges. It is only advantageous when the frontier constitutes a large fraction of the graph, and this typically happens during the middle steps of a BFS on low-diameter graphs (such as social networks).
To get the best performance, we combine the novel bottom-up approach with the classical top-down approach. Since our hybrid switches approaches on a step-level granularity, and it uses each for when they are advantageous, it is called Direction-Optimizing BFS.
The direction-optimizing approach was conceived in time for the November 2011 Graph500 rankings, and it allowed a quad-socket Intel server to beat small clusters and specialized hardware such as the Cray XMT and the Convey HC-1. The algorithm was initially disclosed in a technical report [1] and later formally presented at Supercomputing 2012 [2].
We redesigned our algorithm to run on a cluster to perform BFS on larger graphs. Our implementation [3] is built on top of the CombBLAS framework.
Graph500 Finishes
Adoption of Direction-Optimizing Approach in Graph500