姜少峰课题组 FOCS 2026 入选论文解读：欧氏空间中k-Means问题的全动态算法
导 读
本文为 FOCS 2026 会议接收论文 Fully Dynamic Euclidean k-Means 的解读。该工作由英国华威大学 Sayan Bhattacharya、Martín Costa、Ermiya Farokhnejad，香港科技大学金耀楠以及北京大学姜少峰、楼家宁合作完成。
该论文针对高维欧氏空间中的 k-Means 聚类问题，给出了第一个在全动态设定下，具有亚线性更新时间的常数近似算法。
论文地址：https://arxiv.org/abs/2507.11256
01
问题介绍
欧氏空间中的 -Means 聚类是数据分析、机器学习和理论计算机科学中的经典问题之一。给定一个包含 个点的数据集 ，以及聚类中心数 ，目标是寻找一个包含 个中心的集合 ，使所有数据点到其最近中心的欧氏距离平方和最小，即最小化
本文研究全动态设定下高效聚类算法的设计。在全动态设定下，数据集 会经历一系列点的插入与删除，算法需要在每次更新后快速调整中心集合 ，使其始终是当前数据集上具有理论近似保证的高质量解。
尽管动态聚类近年来取得了一系列重要进展，高维欧氏空间中的全动态聚类问题仍未得到充分理解。现有研究大多聚焦于一般度量空间，其中，已有算法能够以 的更新时间维护 -近似解[BCF25]，且这一更新时间已接近最优；事实上，在一般度量空间中，即使在静态设定下，计算 -近似解也需要 的运行时间[BCIS05]。然而，上述下界并不能排除高维欧氏空间中存在更快算法的可能性：已有研究表明，静态欧氏 -Means 问题可以在 时间内求得 -近似解，其中 [DS24, JJLL26]。这表明，通过充分利用欧氏空间的几何结构，确实有望设计出更新时间为 的动态算法。然而，此前尚不清楚如何将这些几何性质有效融入动态算法的设计。因此，如何在保持 -近似比的同时突破 的更新时间壁垒，成为全动态欧氏 -Means 算法研究中的一个重要开放问题。
02
主要结果
本文给出了首个针对高维欧氏 -Means ，同时实现常数近似和亚线性 更新时间的全动态算法。
定理 1. 对于任意 ，存在一个随机化的全动态欧氏 -Means 算法，以高概率实现 -近似、 的均摊更新时间，以及 的均摊解调整次数。
当 取固定常数时，近似比 为常数，而更新时间 关于 是亚线性的。因此，该结果首次打破了此前常数近似动态算法的 更新时间壁垒。与此同时，算法的均摊调整次数，即每次数据更新后中心集合发生变化的数量，仅为 ，几乎匹配一般度量空间中的当前最优结果[BCF25]。
这一动态结果直接导出了一个运行时间为 的静态算法；进一步结合核心集技术，可将运行时间优化至 。除近似比中关于 的多项式次数较高外，这一近似比与运行时间之间的权衡已经与当前最优的静态算法基本匹配。因此，若要在保持常数近似比的同时，将更新时间进一步降至 ，可能需要克服某种根本性障碍。
03
技术挑战：高效、鲁棒的几何数据结构
突破 更新时间壁垒的关键技术挑战在于如何充分利用欧氏空间的几何结构，设计高效的几何数据结构。与此同时，保证这些数据结构在自适应查询下仍然保持性能也十分关键。这是因为，数据结构通常并非作为独立算法运行，而是作为子程序被最终算法反复调用；在这一过程中，算法会根据此前查询的结果动态选择后续查询操作，从而导致查询序列具有自适应性。这种对自适应查询的鲁棒性要求，使得许多高维欧氏空间中常用的随机化工具难以直接应用。例如，局部敏感哈希（LSH）和随机树嵌入通常依赖输入与内部随机性之间的独立性，而自适应查询会破坏这种独立性，从而使原有的正确性保证失效。
高效的一致哈希
为此，论文采用并显著改进了一致哈希（consistent hashing）技术[CJK+22]。粗略而言，一致哈希将空间划分为若干直径受控的区域，并保证任意足够小的度量球至多与 个区域相交。与 LSH、随机树嵌入等技术不同，一致哈希所提供的保证是确定性的，因此天然能够应对自适应查询。然而，已有的一致哈希方案具有较高的计算开销：即使只计算单个点的哈希值，也需要 时间。当 较大时，这将达到关于 的高次多项式时间，难以满足动态算法的效率要求。
论文设计了一种新的一致哈希方案，在保留确定性保证和近似最优的参数的同时，将单点求值时间降至 ，并支持高效枚举与一个小度量球相交的所有哈希区域。这一改进不仅支撑了本文的动态聚类算法，也可能作为独立工具应用于其他高维几何算法。
新型数据结构1：隐式维护动态聚类
基于新的一致哈希，论文首先设计了一种用于隐式维护动态聚类的数据结构。几乎所有聚类算法都需要确定每个数据点应被分配给哪个最近中心。然而，当数据点集合 和中心集合 均动态变化时，显式维护这一分配通常代价高昂：仅插入或删除一个中心，就可能导致 个数据点同时改变所属中心。
论文的核心思想是不再逐点维护完整的分配关系，而是利用一致哈希将数据点划分到若干桶中，仅显式维护“哈希桶到中心”的分配；同一桶中的数据点则隐式继承该桶所对应的中心。尽管这种表示不显式记录每个点的所属中心，却也足以动态维护算法所需的关键统计量，例如各个近似簇的大小、簇内点到中心的距离平方和等。基于这些统计信息，该数据结构能够支持 -sampling[AV07]，即以正比于数据点到当前中心集合的距离平方的概率进行采样。 -sampling 也为论文后续关键子问题的求解提供了重要工具。
新型数据结构2: 近似度量球上的范围查询
基于新的一致哈希方案，论文还构造了一个通用的近似范围查询结构。给定查询中心 和半径 ，它可以在一个近似的度量球内计算任意可合并统计量。所谓可合并，是指两个不相交集合上的答案可以组合成并集上的答案；计数、求和、最值以及核心集都属于这一类。因此，该结构可用于估计球内点数、执行近似最近邻查询、返回球内数据的 -Means 核心集等任务，并同样在最终动态算法中承担关键角色。
04
最终算法：重新设计两个关键子过程
论文的最终算法建立在[BCF25]的一般度量动态聚类框架之上。该框架本身已经能够同时控制近似比和解调整次数，但其中若干关键步骤是针对一般度量空间设计的，运行时间至少为 。论文识别出两个决定性子过程——Restricted -Means 与 Augmented -Means——并使用新的欧氏数据结构对它们进行完全不同的实现。
Restricted k-Means：删除若干中心
Restricted -Means 给定当前中心集合 和整数 ，要求从 中删除 个中心，使删除后的聚类代价尽可能小。一般度量算法使用随机局部搜索，需要显式维护聚类，时间复杂度达到 。本文转而采用一种新的核心集方法：构造一个大小仅为 的特殊核心集，使得仅基于该核心集即可求得 restricted -means 的近似最优解。
该核心集可以通过近似最近邻查询构造，因此可直接利用上文的数据结构。随后只需在这个 大小的核心集上运行高效的（静态）欧氏聚类算法，即可在 时间内近似求解 Restricted -Means，显著优于一般度量中的 时间。
Augmented k-Means：加入若干中心
Augmented -Means 要求在当前中心集合 的基础上再加入 个中心，使新的聚类代价尽可能小。先前算法通过收缩 构造一个新的度量空间，再求解其中的 -Means；显然，这一新度量空间远非欧氏空间，无法使用任何几何结构。论文观察到，经典 -Means++[AV07]中逐步执行 -sampling 的过程可以直接给出 Augmented -Means 的良好近似。借助前述隐式聚类维护结构，每一步近似 -Sampling 都能在亚线性时间内完成，从而得到高效的动态实现。
参考文献
[AV07] David Arthur and Sergei Vassilvitskii. k-means++: The Advantages of Careful Seeding. In SODA, pages 1027–1035. SIAM, 2007.
[BCF25] Sayan Bhattacharya, Martín Costa, and Ermiya Farokhnejad. Fully Dynamic k-Median with Near-Optimal Update Time and Recourse. In STOC, pages 1166–1177. ACM, 2025.
[BCIS05] Mihai Badoiu, Artur Czumaj, Piotr Indyk, and Christian Sohler. Facility Location in Sublinear Time. In ICALP, pages 866–877. Springer, 2005.
[CJK+22] Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý, and Mingwei Yang. Streaming Facility Location in High Dimension via Geometric Hashing. In FOCS, pages 450–461. IEEE, 2022.
[DS24] Max Dupré la Tour and David Saulpic. Almost-Linear Time Approximation Algorithm to Euclidean k-Median and k-Means. CoRR, abs/2407.11217, 2024.
[JJLL26] Shaofeng H.-C. Jiang, Yaonan Jin, Jianing Lou, and Pinyan Lu. Local Search for Clustering in Almost-Linear Time. In SODA, pages 5960–5977. SIAM, 2026.