Efficient Algorithms for Parallel Bi-core Decomposition

We present new shared-memory parallel algorithms for the bi-core decomposition problem, which discovers dense subgraphs in bipartite graphs and is the bipartite analogue of the classic k-core decomposition problem. We develop a theoretically-efficient parallel bi-core decomposition algorithm that discovers a hierarchy by peeling vertices from the graph in parallel. Our algorithm improves the span (parallel running time) over the state-of-the-art parallel bi-core decomposition algorithm, while matching the state-of-the-art sequential algorithm in work. We additionally prove the bi-core decomposition problem to be P-complete, meaning that a polylogarithmic span solution is unlikely under standard assumptions. We also devise a theoretically-efficient parallel bi-core index structure to allow for fast parallel queries of vertices in given cores. Finally, we propose a novel practical optimization that prunes unnecessary computations, and we provide optimized parallel implementations of our bi-core decomposition algorithms that are scalable and fast. Using 30 cores with two-way hyper-threading, our implementation achieves up to a 4.9x speedup over the state-of-the-art parallel algorithm. Our parallel index structure can be constructed up to 27.7x faster than the state-of-the-art sequential counterpart. Due to the improved storage format of our index structure, our parallel queries are up to 116.3x faster than the state-of-the-art sequential queries.