Direction-Optimizing Breadth-First Search

TitleDirection-Optimizing Breadth-First Search
Publication TypeConference Paper
Year of Publication2012
AuthorsBeamer, S., Asanović K., & Patterson D.

Breadth-First Search is an important kernel used by
many graph-processing applications. In many of these emerging
applications of BFS, such as analyzing social networks, the
input graphs are low-diameter and scale-free. We present an
efficient breadth-first search algorithm that is advantageous for
low-diameter graphs. We adopt a hybrid approach, combining
a conventional top-down algorithm along with a novel bottomup
algorithm. The bottom-up algorithm can dramatically reduce
the number of edges examined, which in turn accelerates the
search as a whole. On a multi-socket server, our hybrid approach
demonstrates speedups of 3.3–7.8 on a range of standard
synthetic graphs and speedups of 1.4–3.8 on graphs from real
social networks compared to a strong baseline. We also show
speedups of greater than 2.3 over the state-of-the-art multicore
implementation when using the same hardware and input graphs

main.pdf336.28 KB