论文标题
平行批处理$ k $ -clique计数
Parallel Batch-Dynamic $k$-Clique Counting
论文作者
论文摘要
在本文中，我们研究了$ k $ clique计数问题的新批次动态算法，这些算法是动态算法，其中更新是边缘插入和删除的批次。我们在平行环境中研究了这个问题，该问题的目标是获得较低（聚集线）深度的算法。我们的第一个结果是使用$ o（δ\ sqrt {Δ+m}）$ a摊销工作的新的平行批处理三角形，计算算法，$ o（\ log^*（δ+m）$ depth具有很高的可能性，$ o（δ+m）$（δ+m）$（δ+m）$ for $ gedue gedue gedunions或deletions $ expect。我们的第二个结果是基于平行快速矩阵乘法的代数算法。假设存在平行的快速矩阵乘法算法，则存在并行矩阵乘法常数$ω_p$，则相同的算法求解动态$ k $ -clique用$ o \ left（\ min \ left）（\ min \ left（Δm^weft） （δ +m）^{\ frac {2（k +1）ω_p} {3（ω_p +1）}}}}} \ right）\ right）$ amortized工作和$ o（\ log（δ +m））$ depth具有很高的可能性，以及$ o \ left（$ o \ weft） 1）ω_p} {3（ω_p + 1）}} \ right）$ space。使用最近开发的平行$ k $ -clique计数算法，我们还获得了一种简单的批次动态算法，用于$ k $ -clique，以$ o（m +δ）α^α^{k-4}）运行的图表上计数$α$，并且预期工作和$ O（ 空间。最后，我们提出了我们平行批处理三角计数算法的多核CPU实现。在具有双向超线程的72核机上，我们的实施实现了36.54--74.73x并行加速，并且在某些情况下，在现有的问题上实现了显着的加速，这不是理论上效率高的问题。
In this paper, we study new batch-dynamic algorithms for the $k$-clique counting problem, which are dynamic algorithms where the updates are batches of edge insertions and deletions. We study this problem in the parallel setting, where the goal is to obtain algorithms with low (polylogarithmic) depth. Our first result is a new parallel batch-dynamic triangle counting algorithm with $O(Δ\sqrt{Δ+m})$ amortized work and $O(\log^* (Δ+m))$ depth with high probability, and $O(Δ+m)$ space for a batch of $Δ$ edge insertions or deletions. Our second result is an algebraic algorithm based on parallel fast matrix multiplication. Assuming that a parallel fast matrix multiplication algorithm exists with parallel matrix multiplication constant $ω_p$, the same algorithm solves dynamic $k$-clique counting with $O\left(\min\left(Δm^{\frac{(2k - 1)ω_p}{3(ω_p + 1)}}, (Δ+m)^{\frac{2(k + 1)ω_p}{3(ω_p + 1)}}\right)\right)$ amortized work and $O(\log (Δ+m))$ depth with high probability, and $O\left((Δ+m)^{\frac{2(k + 1)ω_p}{3(ω_p + 1)}}\right)$ space. Using a recently developed parallel $k$-clique counting algorithm, we also obtain a simple batch-dynamic algorithm for $k$-clique counting on graphs with arboricity $α$ running in $O(Δ(m+Δ)α^{k-4})$ expected work and $O(\log^{k-2} n)$ depth with high probability, and $O(m + Δ)$ space. Finally, we present a multicore CPU implementation of our parallel batch-dynamic triangle counting algorithm. On a 72-core machine with two-way hyper-threading, our implementation achieves 36.54--74.73x parallel speedup, and in certain cases achieves significant speedups over existing parallel algorithms for the problem, which are not theoretically-efficient.
