Parallel array-Based single- and multi-Source breadth first searches on large dense graphs

One of the fundamental algorithms in analytical graph databases is breadth-first search (BFS). It is the basis of reach-ability queries, centrality computations, neighborhood enumeration, and many other commonly-used algorithms. We take the idea of purely array-based BFSs introduced in the sequential multi-source MS-BFS algorithm and extend this approach to multi-threaded single- and multi-source BFSs. Replacing the typically used queues with fixed-sized arrays, we eliminate major points of contention which other BFS algorithms experience. To ensure equal work distribution between threads, we co-optimize work stealing parallelization with a novel vertex labeling. Our BFS algorithms have excellent scaling behavior and take advantage of multi-core NUMA architectures. We evaluate our proposed algorithms using real-world and synthetic graphs with up to 68 billion edges. Our evaluation shows that the proposed multi-threaded single- and multi-source algorithms scale well and provide significantly better performance than other state-of-the-art BFS algorithms.