Theoretically and Practically Efficient Parallel Nucleus Decomposition
Theoretically and Practically Efficient Parallel Nucleus Decomposition
复制标题
DOI：
10.14778/3494124.3494140
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Jessica Shi;Laxman Dhulipala;Julian Shun
中科院分区：
文献类型：
--
作者：
Jessica Shi;Laxman Dhulipala;Julian Shun
本文研究了核分解问题，这已被证明是有用的，在寻找密集的子结构图。我们提出了一种新的并行算法，是有效的理论和实践。我们的算法实现了与最佳顺序算法相匹配的工作复杂度，同时还具有较低的深度（并行运行时间），这大大改进了现有的唯一并行核分解算法（Sariyüce等人，PVLDB 2018）。我们的算法的理论效率的关键是一个新的引理，结合使用理论上有效的并行算法的团列表和桶剥离集团时所做的工作量的界限。我们介绍了几个新的实用优化，包括一个新的多级哈希表结构，以存储信息的集团空间效率和技术，用于遍历这种结构的高速缓存效率。在一个具有双向超线程的30核机器上，我们在Sariyüce等人的最先进的并行核分解算法上实现了高达55倍的加速比，以及高达40倍的自相关并行加速比。我们能够有效地计算更大的核分解比以前的工作在几百万规模的图形的第一次。
This paper studies the nucleus decomposition problem, which has been shown to be useful in finding dense substructures in graphs. We present a novel parallel algorithm that is efficient both in theory and in practice. Our algorithm achieves a work complexity matching the best sequential algorithm while also having low depth (parallel running time), which significantly improves upon the only existing parallel nucleus decomposition algorithm (Sariyüce et al. , PVLDB 2018). The key to the theoretical efficiency of our algorithm is a new lemma that bounds the amount of work done when peeling cliques from the graph, combined with the use of a theoretically-efficient parallel algorithms for clique listing and bucketing. We introduce several new practical optimizations, including a new multi-level hash table structure to store information on cliques space-efficiently and a technique for traversing this structure cache-efficiently. On a 30-core machine with two-way hyper-threading on real-world graphs, we achieve up to a 55x speedup over the state-of-the-art parallel nucleus decomposition algorithm by Sariyüce et al. , and up to a 40x self-relative parallel speedup. We are able to efficiently compute larger nucleus decompositions than prior work on several million-scale graphs for the first time.