May, 2018

对数直径轮并行图连通性

PDF
TL;DR研究在 MPC 模型下对图连通性问题进行优化，通过图直径参数化时间复杂度，得到了对于直径为 D 的图的时间复杂度为 O (logDloglog (m/n) n)、总内存为 Θ(m) 的连通性算法，并扩展到生成森林、DFS 序列、最小生成森林和瓶颈生成森林等相关图问题，并指出这些问题的类似界限推导可以应用于更快的布尔矩阵乘法算法。
graph connectivitydiametermemoryspanning forestmatrix multiplication
发现论文，激发创造
  • 并行匹配算法的圆形压缩

    该篇论文探讨了在大规模计算框架中对于最大匹配问题的解决方法，最终在机器拥有稍微低于线性内存的条件下，实现了近乎指数级的算法复杂度优化。

    Jul, 2017

  • 随机、大规模和高效行走

    本研究提出一组技术，允许在每台机器的空间强烈次线性的情况下，在 Massive Parallel Computation（MPC）模型中高效生成许多独立的随机游走，从而突破了 PageRank 等在有向和无向图的应用中遇到的局限性。

    Jul, 2019

  • 局部收缩算法实现大规模连通性分量

    该研究设计了一个分布式算法用于计算连接组件问题，并在 MapReduce 中提供了可扩展的实现。该算法在所有图形上显示 O (log n) 收敛，并对某些随机图形类具有高概率 O (log log n) 并行运行时间。在实践方面，该算法优于现有的 MapReduce 算法，并且在拥有数万亿边缘的图形上具有可扩展性。

    Jul, 2018

  • 分布式最小割近似

    本文通过分布式算法研究了在标准同步消息传递模型下，计算近似的最小边割问题，提出了随机分层技术作为分析随机边采样的一种简单方法，并给出了两个分布式算法的时间复杂度，同时还强化了上一篇研究的下界。

    May, 2013

  • 局部边翻转法扩展算子

    本文针对给定 n 个节点和 d 个邻居的无向图，提出了一种分布式的算法，使用随机翻转来改进图的连通性以获得新的拓展图，且经研究表明可以在 O（n ^ 2 d ^ 2 log n）的步骤内实现高概率有效。

    Oct, 2015

  • 稀疏网络中分布式距离计算的近线性下界

    本篇研究提出了一种构建稀疏图的新技术，能够证明计算 CONGEST 模型中距离的轮廓复杂度的近似线性下界，它能够计算直径、半径和所有偏心距的近似值，并且这些下界能够比以前的下界有所改善。

    May, 2016

  • 多项式对数轮次内求解相关聚类问题的三因素近似算法失效

    本文研究了用于相关聚类问题的并行算法，其中每个不同实体的每对实体都标记为相似或不相似，旨在将实体分成簇以最小化与标签的不一致性，提出了首个多项式对数深度并行算法，并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解，可以将其转换为 (m1.5) 时间顺序算法和带有 (m1.5) 总内存的多项式对数轮次亚线性内存计算算法。

    Jul, 2023

  • 单连接聚类在 l_p 距离下的大规模并行算法和难度

    介绍了用 Apache Spark 实现的高效的大规模并行算法来计算单链接聚类问题，该算法在 Hamming 距离，L1，L2 和 L∞ 距离下均能实现单轮 MPC，和（除了 Hamming 距离的精确算法外）都能实现（1+ε）- 近似，同时证明了在标准 MPC 难度假设下，o（log n）轮算法的常数近似难度结果。

    Oct, 2017

  • 通过随机 $2$-Out 缩减加速边连通性算法

    使用基于 2 出边采样的简单新的随机收缩方法解决全局最小割问题，进而获得更好的边连通性、分布式算法和并行计算等方面的表现。

    Sep, 2019

  • 广播 CONGEST 网络中确定性子图检测

    本文提出了一种对于分布式计算中的广播 CONGEST 模型进行子图查找和枚举的简单确定性算法，并且给出了性能上限及其紧密性的证明。

    May, 2017