Direction-optimizing breadth-first search

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.

References

1. Virat Agarwal et al. Scalable graph exploration on multicore processors. International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2010.
2. David Bader and Kamesh Madduri. Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. International Conference on Parallel Processing (ICPP), 2006.
3. David Bader and Kamesh Madduri. SNAP: Small-world network analysis and partitioning: an open-source parallel graph framework for the exploration of large-scale networks. International Parallel and Distributed Processing Symposium (IPDPS), 2008.
4. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286:509--512, Oct 1999.
5. Scott Beamer, Krste Asanović, and David Patterson. Searching for a parent instead of fighting over children: A fast breadth-first search implementation for graph500. Technical Report UCB/EECS-2011-117, EECS Department, University of California, Berkeley, 2011.
6. Paolo Boldi et al. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In International World Wide Web Conference (WWW). ACM Press, 2011.
7. Paolo Boldi and Sebastiano Vigna. The WebGraph framework I: Compression techniques. In International World Wide Web Conference (WWW), pages 595--601, Manhattan, USA, 2004. ACM Press.
8. Aydin Buluç and Kamesh Madduri. Parallel breadth-first search on distributed memory systems. International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2011.
9. Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. R-MAT: A recursive model for graph mining. SIAM Data Mining, 2004.
10. Jatin Chhugani et al. Fast and efficient graph traversal algorithm for cpus: Maximizing single-node efficiency. International Parallel and Distributed Processing Symposium, 2012.
11. Convey HC-1 family. www.conveycomputer.com/Resources/Convey_HC1_Family.pdf.
12. Timothy Davis and Yifan Hu. The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software (to appear), cise.ufl.edu/research/sparse/matrices.
13. Paul Erdos and Alfréd Réyni. On random graphs. i. Publicationes Mathematicae, 6:290--297, 1959.
14. Graph500 benchmark. www.graph500.org.
15. Sungpack Hong, Tayo Oguntebi, and Kunle Olukotun. Efficient parallel graph exploration on multi-core CPU and GPU. Parallel Architectures and Compilation Techniques (PACT), 2011.
16. Haewoon Kwak et al. What is Twitter, a social network or a news media? International World Wide Web Conference (WWW), 2010.
17. Jurij Leskovec et al. Realistic, mathematically tractable graph generation and evolution, using Kronecker multiplication. European Conference on Principles and Practice of Knowledge Discovery in Databases, 2005.
18. Y Low et al. GraphLab: A new framework for parallel machine learning. Uncertainty in Artificial Intelligence, 2010.
19. Grzegorz Malewicz et al. Pregel: A system for large-scale graph processing. International Conference on Management of Data (SIGMOD), Jun 2010.
20. Duane Merrill, Michael Garland, and Andrew Grimshaw. Scalable GPU graph traversal. Principles and Practice of Parallel Programming, 2012.
21. Alan Mislove et al. Measurement and analysis of online social networks. ACM SIGCOMM Conference on Internet Measurement (IMC), 2007.
22. David Mizell and Kristyn Maschhoff. Early experiences with large-scale Cray XMT systems. International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2009.
23. Paolo Boldi others. Ubicrawler: A scalable fully distributed web crawler. Software: Practice & Experience, 34(8):711--726, 2004.
24. Duncan Watts and Steven Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, June 1998.
25. Wikipedia page-to-page link database 2009. http://haselgrove.id.au/wikipedia.htm.
26. Christo Wilson et al. User interactions in social networks and their implications. European conference on Computer systems (EuroSys), 2009.
27. Andy Yoo et al. A scalable distributed parallel breadth-first search algorithm on BlueGene/L. International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2005.
28. Kisun You et al. Scalable HMM-based inference engine in large vocabulary continuous speech recognition. IEEE Signal Processing Magazine, 2010.

• Computer systems organization

• General and reference

  • Cross-computing tools and techniques

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

• Networks