Description
This report provides a summary of an efficient breadth-first search implementation that is advantageous for social networks. This implementation uses a hybrid approach, combining a conventional top-down algorithm along with a novel bottom-up algorithm. The bottom-up algorithm can dramatically reduce the number of edges examined, which in turn accelerates the search as a whole. This hybrid approach is used to make a fast implementation for the Graph500 Benchmark [2], achieving 5.1 GTEPs at scale=28 (256M vertices with 4B undirected edges) on a quad-socket 40-core Intel Xeon compute node. It ranks 19th out of 50 on the November 2011 Graph500 Rankings.