Direction-Optimizing Breadth-First Search

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

Breadth-First Search is an important kernel used bymany graph-processing applications. In many of these emergingapplications of BFS, such as analyzing social networks, theinput graphs are low-diameter and scale-free. We propose ahybrid approach that is advantageous for low-diameter graphs,which combines a conventional top-down algorithm along witha novel bottom-up algorithm. The bottom-up algorithm candramatically reduce the number of edges examined, which inturn accelerates the search as a whole. On a multi-socket server,our hybrid approach demonstrates speedups of 3.3–7.8 on a rangeof standard synthetic graphs and speedups of 2.4–4.6 on graphsfrom real social networks when compared to a strong baseline.We also typically double the performance of prior leading sharedmemory (multicore and GPU) implementations.


Research supported by Microsoft (Award #024263) andIntel (Award #024894) funding and by matching funding byU.C. Discovery (Award #DIG07-10227). Additional supportcomes from Par Lab affiliates National Instruments, Nokia,NVIDIA, Oracle, and Samsung. Partially funded by DARPAAward HR0011-11-C-0100.

Bibliographic Notes

Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis (SC12), Article No. 12, Salt Lake City, Utah

Abbreviated Authors

S. Beamer, K. Asanovi?, and D. Patterson

ICSI Research Group


ICSI Publication Type

Article in conference proceedings