Direction-Optimizing Breadth-First Search
Open Access
- 1 January 2013
- journal article
- Published by Hindawi Limited in Scientific Programming
- Vol. 21 (3-4), 137-148
- https://doi.org/10.1155/2013/702694
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
Funding Information
- Microsoft (024263, 024894, DIG07-10227, HR0011-11-C-0100)