Direction-optimizing Breadth-First Search
By Scott Beamer, Krste Asanovic, David A. Patterson. International Conference for High Performance Computing, Networking, Storage and Analysis, 2012
586 citations recorded by the source corpus.
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.
Subfields: Aerospace Engineering, Artificial Intelligence, Computer Vision and Pattern Recognition
View Paper: https://www.semanticscholar.org/paper/6bc45efd5b27f661b1cbbab8998b87a34da5967e
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Aerospace Engineering
In Artificial Intelligence
- Krste Asanovic
- David A. Patterson
- Scott Beamer
- Yuan Xie
- John Douglas Owens
- Yangzihao Wang
- Andrew A. Davidson
- Yuduo Wu
In Computer Vision and Pattern Recognition
- Krste Asanovic
- David A. Patterson
- Scott Beamer
- Yuan Xie
- John Douglas Owens
- Jishen Zhao
- Shuangchen Li
Citations in the corpus
- The GAP Benchmark Suite (2015, methodology): “We also describe the required evaluation methodologies and provide rationale for our decisions.”
- Pinatubo: A processing-in-memory architecture for bulk bitwise operations in emerging non-volatile memories (2016, background): “Bitwise operations are very important and widely used by database [26], graph processing [5], bio-informatics [21], and image processing [6].”
- X-Stream: edge-centric graph processing using streaming partitions (2013, unknown): “[18] demonstrated that for scale-free graphs large speedups can be obtained in the later execution stages of BFS by iterating over the set of target vertices rather than the set of source vertices.”
- Gunrock: a high-performance graph processing library on the GPU (2015, background): “[1] described a “pull”-style advance on CPUs: instead of starting with a frontier of active vertices, pull starts with a frontier of unvisited vertices, generating the new frontier by filtering the unvisited frontier for vertices that have neighbors in the current frontier.”