ICMLJun, 2021

常数轮并行下的相关聚类

PDF
TL;DR本文提出了一种基于大规模并行计算 (MPC) 的算法，用于解决相关聚类问题。该算法的主要目标是利用签名图对图进行分区以最小化争议数量。在实验中，该算法同时试图减少节点内存的使用率。我们的算法是第一个在亚线性存储器中运行且使用有限的 MPC 轮数可以证明近似计算聚类问题方法的一种。
发现论文，激发创造
  • 多项式对数轮次内求解相关聚类问题的三因素近似算法失效

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

    Jul, 2023

  • 定数个簇的相关聚类

    研究聚类分析中的一种新方法 —— 相关聚类或定性信息聚类，探讨了最大化协议的问题和最小化分歧的问题，重点研究了聚类数为常数 k 的情况，发现该问题具有多项式时间近似解，为解决最小化分歧问题做了大量的技术工作。

    Apr, 2005

  • 大规模图上的并行相关聚类

    本文提出了 C4 和 ClusterWild！两个用于并行相关聚类的算法，并在实验中证明了它们在精度和运行时间方面的优势。

    Jul, 2015

  • 使用同簇查询的近似相关聚类

    该研究介绍了一种半监督聚类框架及其在相关性聚类问题中的应用，提出了一种有效的近似算法，并给出了同类查询数量的上下界。

    Dec, 2017

  • 数据流中的相关聚类

    本文研究动态数据流模型下相关聚类问题，结合线性草图和凸规划与抽样技术提出 O (n・polylog n)-space 近似算法，解决了自然问题。

    Dec, 2018

  • 相关聚类推广

    LambdaCC 和 MotifCC 是两种变体的相关聚类问题，应用于网络分析和社区检测，我们提出了两种非平凡的逼近算法来解决该问题，其中我们提出了两个算法来改善先前的逼近结果，同时还研究了在构造两个簇的限制下的逼近结果，其中 MotifCC 应用于超图设置。

    Sep, 2018

  • 并行匹配算法的圆形压缩

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

    Jul, 2017

  • 多割最小最大相关聚类

    本文提供了第一个问题的非平凡近似算法，来解决最小化每个子群组的最大不一致数的最小化最大相关聚类问题，并对 multicut 问题得出了相应的结果。

    Jun, 2019

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

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

    Oct, 2017

  • 最小最大相关聚类的 4 近似算法

    我们介绍了一种用于最小最大相关聚类问题的下界技术，并基于此技术提出了一种完全图的组合 4 近似算法。我们通过贪婪连接启发式算法扩展了这个算法，并在几个基准数据集上实证表明它提高了解决方案的质量和运行时间，改进了现有的技术水平。

    Oct, 2023