Direction-optimizing breadth-first search

Issue title: Selected Papers from Super Computing 2012

Article type: Research Article

Authors: Beamer, Scott^; | Asanović, Krste | Patterson, David

Affiliations: Electrical Engineering and Computer Sciences Department, University of California, Berkeley, CA, USA. E-mails: {sbeamer, krste, pattrsn}@eecs.berkeley.edu

Note: [] Corresponding author. E-mail: sbeamer@eecs.berkeley.edu

Abstract: 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 propose a hybrid approach that is advantageous for low-diameter graphs, which combines 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. 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 2.4–4.6 on graphs from real social networks when compared to a strong baseline. We also typically double the performance of prior leading shared memory (multicore and GPU) implementations.

Keywords: Graph algorithms, breadth-first search

DOI: 10.3233/SPR-130370

Journal: Scientific Programming, vol. 21, no. 3-4, pp. 137-148, 2013