Dynamic k-center Clustering with Lifetimes¶

会议: NeurIPS 2026
arXiv: 2603.23348
领域: 优化/理论
关键词: 动态聚类, k-center, 生命周期模型, 确定性近似算法, 亚线性内存

一句话总结¶

本文提出了兼顾任意增删与先验存续期的「生命周期动态聚类模型（dynamic setting with lifetimes）」，针对度量空间 $k$-center 问题设计了首个近似比达理论下界的确定性 $(2+\varepsilon)$ 近似算法（摊还更新时间 $\widetilde{O}(k/\varepsilon)$），并为有序流提出了仅需 $\widetilde{O}(k/\varepsilon)$ 亚线性工作内存的确定性 $(6+\varepsilon)$ 近似算法。

研究背景与动机¶

$k$-center 聚类作为无监督学习和数据概括的核心基准，旨在从度量空间中选取至多 $k$ 个聚类中心，使得所有数据点到其最近中心的最大距离最小。在现实分布式学习系统、电商仓储调度、在线社区活跃用户分析及证书吊销监测等场景中，数据分布呈高度动态演化特征。过去针对动态聚类的研究主要被割裂在两个极端假设之中：其一是滑动窗口模型（sliding window），强制假定数据集只保留最近到达的 $N$ 个点，具有固定的 FIFO 生存期；其二是全动态模型（fully dynamic），允许任意到达与删除但假定删除操作突发且不可预知。前者难以刻画非严格等长时效的复杂时效数据，而后者面对任意删除往往被迫引入代价极高的再聚类机制，其随机化或最坏情况更新时间居高不下，且面对度量自适应敌手时理论保证往往受限。

这种割裂背后的核心矛盾在于：现实系统中的动态数据在到来时往往已明确包含其有效时限（例如带有固定有效期的 TLS 证书透明度日志、预订出库时间的仓储货品、固定租期的订阅账户等），现存框架要么彻底忽略了该预验时效信息（退化为全动态模型，付出高昂的 $O(k^2)$ 或多项式级更新代价），要么强加严苛的窗口大小一致性假设。如果直接将滑动窗口算法迁移到生命周期动态场景，一旦删除次序与到达次序倒错便会导致几何覆盖保证完全失效；而套用现存全动态算法，不仅算法复杂度随聚类中心数二次方暴涨，更需付出全量活动数据存储的高昂代价，无法在海量流式时效数据中高效落地。

本文的核心思路是利用到达时已知的生命周期（lifetimes）打破动态度量维护的被动响应僵局，提出生命周期动态聚类模型（dynamic setting with lifetimes）。核心 idea：通过利用到达时已知的删除时间，将簇内点划分为先于中心过期的消亡点（vanishing）与后于中心过期的持久点（persistent），并借助反转重聚类策略（reclustering）与吸引子-长寿代表元机制，分别在全量活跃内存下达到几乎紧致的 $(2+\varepsilon)$ 确定性近似（$\widetilde{O}(k/\varepsilon)$ 摊还更新时间），并在 $H$-有序流下实现极度紧凑的 $\widetilde{O}(k/\varepsilon)$ 亚线性工作内存与 $(6+\varepsilon)$ 近似。

方法详解¶

整体框架¶

算法的整体工作流围绕离散化的最优半径网格 $\Gamma$ 展开。设度量空间最小点对距离为 $d_{\min}$，最大距离为 $d_{\max}$，空间高宽比 $\Delta = d_{\max}/d_{\min}$。算法以几何步长 $(1+\beta)$ 维护猜测半径集合 $\Gamma$，在对数尺度上离散搜索最优聚类半径。对于全内存高精度算法，维护全量活动点并根据已知生存期划分各层级代表簇；对于轻量化内存受限算法，则针对每个网格半径维护一组几何吸引子（attractors）以及各吸引子所覆盖范围内的最长寿代表元（representatives），无需保留全量点集。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["动态数据流输入<br/>点 p 伴随到达时间与删除时间"] --> Split["多网格半径离散化处理<br/>每个候选半径 γ ∈ Γ 并行评估"]
    Split --> AlgChoice{"算法分支模式"}
    AlgChoice -->|全量内存/高精度| P1["中心寿命优先分配与分区<br/>持久点 P 与消亡点 V 双计数器追踪"]
    P1 --> P2["逆向重心自适应重聚类<br/>条件触发 Reclustering 级联清退"]
    AlgChoice -->|受限内存/亚线性| S1["吸引子-代表元贪心维护<br/>仅保留各区域最长寿候选点"]
    S1 --> S2["临界清理机制 Cleanup<br/>基于 H-有序度驱逐过期代表元"]
    P2 --> Out1["Query: 判定 U_γ 为空的最小网格<br/>输出 (2+ε) 近似解 C_γ"]
    S2 --> Out2["Query: 贪心 2γ-Cover 覆盖 R_γ<br/>输出 (6+ε) 近似解 C_γ"]

关键设计¶

1. 寿命感知的中心优选与消亡/持久点划分：规避重复再指派开销

在动态维护网格半径 $\gamma$ 的 $k$-center 簇划分时，删除操作最核心的开销源于「聚类中心被删除」导致的整簇点重新寻找中心。若新选中心寿命较短，其频繁过期将引发级联式重聚类波动。为此，算法对每个候选半径 $\gamma$，维护簇集合 $\mathcal{D}^\gamma = (D_1^\gamma, \dots, D_{\ell^\gamma}^\gamma)$ 与未聚类候选点集 $U^\gamma$。在分配点时，不仅优先将点划分至有效距离内的最小索引簇，且在选取新中心时强制选取删除时间最晚（$t_{\rm del}$ 最大）的点。

基于此，算法将每个簇 $D_i^\gamma$ 严格解耦为两组互斥集合：持久点集 $P_i^\gamma := \{x \in D_i^\gamma \colon t_{\rm del}(c_i^\gamma) < t_{\rm del}(x)\}$ 与消亡点集 $V_i^\gamma := \{x \in D_i^\gamma \colon t_{\rm del}(c_i^\gamma) \ge t_{\rm del}(x)\}$。消亡点的删除时间早于或等于其中心，因而永远不会经历其中心失效导致的重指派事件；相反，只有持久点在其所属中心过期时才需要迁移至更高索引簇。通过在各簇内维护持久点与消亡点计数器，算法将潜在失效风险精确量化，为平摊时间复杂度奠定了基础结构。

2. 势能驱动的阈值自适应重聚类：平摊更新时间从 $O(k^2)$ 降至 $O(k)$

为防止对抗序列下多次中心被删导致反复将大量持久点向后重聚类（最坏情况下 $O(n)$ 次更新可诱发 $\Theta(n^2)$ 复杂度），算法引入了严格的自适应重聚类触发准则。在每一次插入或删除操作末尾，触发 Reclustering 检查，寻找满足如下不等式的最小索引 $h$：

\[\sum_{j=h}^{\ell^\gamma} |P_j^\gamma| > |U^\gamma| + \sum_{j=h}^{\ell^\gamma} |V_j^\gamma|\]

一旦找到该临界索引 $h$，算法立即将未分配集合 $U^\gamma$ 与后续簇 $\bigcup_{j=h}^{\ell^\gamma} D_j^\gamma$ 中的全部点归并为一个临时池 $U'$，清空 $h$ 之后的所有簇，并从 $U'$ 中反复贪心挑选生存期最长的点作为新中心重新覆盖，直到形成新的 $\ell^\gamma - h + 1$ 个簇或 $U'$ 被掏空。由于重聚类后的新中心均具有该子区域内的极大生存期，所有被重新吸收的点在其新中心下立即全部转化为消亡点（$V$ 属性），且根据消亡单调性引理，点一旦变为消亡态就绝不会回退为持久态。该势能单调减少机制证明了任何点作为消亡点在删除前最多贡献 $O(k)$ 次状态检查，从而将单次网格更新操作从经典全动态算法的 $O(k^2)$ 压低至 $O(k)$。

3. 吸引子与孤儿代表元拓扑维护：在有限内存下锁定几何近似

在严苛内存限制下，算法舍弃对全量活跃点集 $X_t$ 的保存，转而维护至多 $k+1$ 个彼此相距大于 $2\gamma$ 的独立吸引子集合 $A^\gamma$，并为每个活跃吸引子 $a_i^\gamma$ 仅维护单个具有最晚删除时间的代表元 $r_i^\gamma = \mathrm{rep}^\gamma(a_i^\gamma)$。当新点 $p$ 到来时，若距离现有吸引子集合均大于 $2\gamma$，则自身成为新吸引子及自身代表元；若落在某个吸引子 $2\gamma$ 邻域内且其删除时间长于当前记录的代表元，则直接替换代表元。

当吸引子失效而其代表元尚未到期时，代表元转化为孤儿代表元（$R_{\rm orph}^\gamma$）。为了避免孤儿代表元无限膨胀挤占内存，算法设计了 Cleanup 机制：当 $|A^\gamma| = k+1$ 时，这 $k+1$ 个点构成无解证书（证明在半径 $\gamma$ 下至少需要 $k+1$ 个球），在此期间 $\gamma$ 不可能作为最优半径，因此可以安全清退所有在当前吸引子集合最小删除时间 $t_{\min} = \min_{a \in A^\gamma} t_{\rm del}(a)$ 之前过期的代表元。

4. 基于数据流乱序度（$H$-ordering）的亚线性内存界定

为了度量删除到达顺序的偏离程度，论文首次形式化提出了数据流的 $H$-ordered 概念：对于任意两个点 $p, q$，若 $t_{\rm arr}(p) < t_{\rm arr}(q)$ 且在它们之间有至少 $H$ 个点到达，则必有 $t_{\rm del}(p) < t_{\rm del}(q)$。该参数为真实业务提供了精细建模手段（例如批处理并发窗口或网络抖动窗口大小即为 $H$），而在滑动窗口模型下 $H=0$。算法无需预先知道 $H$ 的具体数值，理论证明在此约束下孤儿代表元数量被严格锁定为 $O(H)$，从而使得数据结构的总点数被限制在 $O(\min\{k+H, |X_t|\})$。当数据流具有良好时序局部性（$H = O(k)$）时，空间复杂度完全脱离活动点全集大小，实现强亚线性空间占用。

一个完整示例¶

考虑 $k=2$、选定半径猜测 $\gamma=1.0$ 的度量空间。 1. 点 $p_1$ 到达（$t_{\rm arr}=1, t_{\rm del}=10$）：初始化为首个吸引子 $a_1$ 及代表元 $r_1=p_1$。 2. 点 $p_2$ 到达（$t_{\rm arr}=2, t_{\rm del}=15$），且 $d(p_2, p_1)=1.2 \le 2\gamma$：$p_2$ 被 $a_1$ 吸引。由于 $t_{\rm del}(p_2) > t_{\rm del}(r_1)$，代表元更新为 $r_1=p_2$，$p_1$ 被安全逐出内存，仅保留 $a_1$ 与 $r_1$。 3. 点 $p_3$ 到达（$t_{\rm arr}=3, t_{\rm del}=8$），$d(p_3, a_1)=3.0 > 2\gamma$：$p_3$ 无法被 $a_1$ 覆盖，创建新吸引子 $a_2=p_3$ 与 $r_2=p_3$。此时 $|A^\gamma|=2 \le k$。 4. 点 $p_4$ 到达（$t_{\rm arr}=4, t_{\rm del}=12$），距离 $a_1, a_2$ 均大于 $2\gamma$：新增吸引子 $a_3=p_4$。此时 $|A^\gamma|=3 = k+1$。触发 Cleanup：计算 $t_{\min} = \min\{t_{\rm del}(a_1), t_{\rm del}(a_2), t_{\rm del}(a_3)\} = \min\{10, 8, 12\} = 8$。 5. 查询时刻 $t=5$：若 $a_2$ 在此期间过期，代表元池保留充分的几何隔离证书，若 $|A^\gamma| \le k$，对现存代表元集合运行贪心 $2\gamma$-覆盖即可保证对全量隐式点集的最大距离不超过 $6\gamma$。

实验关键数据¶

主实验¶

论文对提出算法与已有全动态算法（Fully Dynamic）及过期流算法（Expiration Streaming）在理论渐近指标上进行了全面对比评估。

算法机制	适用环境 / 假设	近似比 (Approximation Ratio)	每次更新时间 (Update Time)	工作内存占用 (Space Complexity)	敌手模型假设
Chan et al. (WWW 2018)	全动态 (Fully Dynamic)	$2+\varepsilon$	$O\left(\frac{\log \Delta}{\varepsilon} k^2\right)$ 摊还	$O\left(\frac{\log \Delta}{\varepsilon} \\|X_t\\|\right)$	仅非适应性 (Oblivious)
Bateni et al. (SODA 2023)	全动态 (Fully Dynamic)	$2+\varepsilon$	$O\left(\frac{\log \Delta}{\varepsilon} \log \\|X_t\\| (k + \log \\|X_t\\|)\right)$ 摊还	$O\left(\frac{\log \Delta}{\varepsilon} \\|X_t\\|\right)$	仅非适应性 (Oblivious)
Blank et al. (ICALP 2026)	到期流 (Expiration Streaming)	$6k + 2 + \varepsilon$	$O\left(\frac{\log \Delta}{\varepsilon} k^4\right)$ 最坏情况	$O\left(\frac{\log \Delta}{\varepsilon} k^3\right)$	适应性 (Adaptive)
本文高精度算法 (Sec 3)	带生命周期动态 (Lifetimes)	$2+\varepsilon$	$O\left(\frac{\log \Delta}{\varepsilon} k + \max_t \log \\|X_t\\|\right)$ 摊还	$O\left(\frac{\log \Delta}{\varepsilon} \\|X_t\\|\right)$	度量适应性 (Metric-Adaptive)
本文空间高效算法 (Sec 4)	$H$-有序动态流 (Lifetimes)	$6+\varepsilon$	$O\left(\frac{\log \Delta}{\varepsilon} \min\{k+H, \\|X_t\\|\}\right)$ 最坏情况	$O\left(\frac{\log \Delta}{\varepsilon} \min\{k+H, \\|X_t\\|\}\right)$	度量适应性 (Metric-Adaptive)

消融实验¶

消融分析聚焦于核心组件（重聚类机制、中心生命周期优选策略、乱序参数 $H$ 对内存的约束能力）对算法时间与空间开销的敏感性。

配置变体	核心变动说明	运行时间规模 / 内存状态	理论分析与说明
完整算法 1 (Full Model)	启用中心寿命贪心选择 + 条件 Reclustering	$O(n k)$ 总操作数，摊还 $\widetilde{O}(k)$	势能严格单调，消亡点最多触发一次重新规整
消融 Reclustering (w/o Reclustering)	禁用式 (2) 触发的级联重构，仅被动删除并局部填补	最坏情况总操作数退化至 $\Theta(n^2)$	见 Remark 3.1 构造序列：多次级联搬迁导致二次方开销
消融中心寿命优选 (Random Center)	出现空缺时任意挑选点作为新中心	摊还更新时间升至 $O(k^2)$	频繁产生持久点，破坏消亡单调吸收机制
空间算法：$H = 0$ (严格 FIFO / 滑动窗口)	约束点删除次序与到达次序严格单调一致	内存 $O\left(\frac{\log \Delta}{\varepsilon} k\right)$，时间最坏情况 $O(k)$	完全匹配滑动窗口模型的最优渐近理论界
空间算法：$H = O(k)$ (低抖动有序流)	允许局部窗口大小为 $O(k)$ 的有限乱序到期	内存 $O\left(\frac{\log \Delta}{\varepsilon} k\right)$，最坏情况时间 $\widetilde{O}(k)$	保持严格亚线性内存，有效覆盖工业批处理流
**空间算法：$H \ge \Omega(	X_t	)$ (极端任意乱序)**	删除时间完全无序，任意长生命周期穿插

关键发现¶

重聚类机制不可或缺：Remark 3.1 严谨证明了若缺少基于持久/消亡比率驱动的 Reclustering 过程，存在特定的度量空间点插入与删除对抗序列，使得算法在 $n$ 步操作中产生 $\Theta(n^2)$ 次点位迁移与距离计算，重聚类是平摊时间从二次方收敛到线性的决定性支柱。
确定性绕过度量自适应下界：已有全动态算法大多依赖随机化技术，且 Bateni 等人（SODA 2023）证明了在全动态模型下面对度量自适应敌手无法达到多项式对数更新时间。本文借助「预先获知生命周期」的信息优势，以纯确定性算法达成了度量自适应鲁棒性，填补了动态图与度量算法的理论空白。
常数级空间高效逼近：相较于 Blank 等人（ICALP 2026）同类到期流模型中随 $k$ 呈线性劣化的 $(6k+2+\varepsilon)$ 近似比和 $O(k^4)$ 更新时间，本文算法不仅将近似比锁定在常数级 $(6+\varepsilon)$，更在 $H=O(k)$ 下将最坏情况更新时间压缩至 $\widetilde{O}(k/\varepsilon)$。

亮点与洞察¶

提出生命周期动态模型（Lifetimes Model）：在过于严格的滑动窗口与过于宽泛的全动态之间开辟了新理论维度，切合云计算、容器调度与密码证书等现代系统的内在物理属性。
消亡态单调性（Vanishing Invariance）：精巧证明了点一旦因为中心寿命更长而进入消亡状态，在经历后续插入、删除和重聚类时永远保持消亡属性，从代数拓扑角度将双重求和复杂度限制在 $n(k+1)$ 之内。
时序偏离度 $H$-ordering 的形式化建模：将无序程度量化为一个可控参数 $H$，使理论推导能够优雅地平滑衔接严格 FIFO（$H=0$）与完全任意动态（$H=|X|$），为流算法复杂度分析提供了可广泛复用的分析工具。

局限与展望¶

依赖全域空间高宽比 $\Delta$：算法网格 $\Gamma$ 的大小依赖于 $d_{\max}/d_{\min}$，在极端稀疏或跨度极大的度量空间中会引入 $O(\log \Delta)$ 的更新时间膨胀；未来可探索无需已知高宽比的自适应动态伸缩网格。
追索次数（Recourse）尚未优化：当前两套算法在每次更新时聚类中心集合的置换数（recourse）在上界为平凡的 $O(k)$，如何结合一致性聚类（consistent clustering）技术将单步变更中心数压低到 $O(1)$ 或 $o(k)$ 仍是开放问题。
精确生命周期假设的放宽：实际生产中删除时间可能伴随预测误差；将该模型与带预测算法（algorithms with predictions）相结合，分析在误差扰动下的鲁棒性边界极具实践价值。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次系统性提出生命周期动态聚类模型并给出紧致确定性算法。
实验充分度: ⭐⭐⭐⭐ 纯理论算法论文，定理证明完备、引理推导闭环，缺失大规模实测 Benchmark。
写作质量: ⭐⭐⭐⭐⭐ 逻辑演绎层次分明，复杂数据结构的几何直觉与势能分析表述清晰。
价值: ⭐⭐⭐⭐⭐ 为流式动态学习与度量维护设立了全新基准，理论启发性极强。

算法机制	适用环境 / 假设	近似比 (Approximation Ratio)	每次更新时间 (Update Time)	工作内存占用 (Space Complexity)	敌手模型假设
Chan et al. (WWW 2018)	全动态 (Fully Dynamic)	\(2+\varepsilon\)	\(O\left(\frac{\log \Delta}{\varepsilon} k^2\right)\) 摊还	\(O\left(\frac{\log \Delta}{\varepsilon} \\|X_t\\|\right)\)	仅非适应性 (Oblivious)
Bateni et al. (SODA 2023)	全动态 (Fully Dynamic)	\(2+\varepsilon\)	\(O\left(\frac{\log \Delta}{\varepsilon} \log \\|X_t\\| (k + \log \\|X_t\\|)\right)\) 摊还	\(O\left(\frac{\log \Delta}{\varepsilon} \\|X_t\\|\right)\)	仅非适应性 (Oblivious)
Blank et al. (ICALP 2026)	到期流 (Expiration Streaming)	\(6k + 2 + \varepsilon\)	\(O\left(\frac{\log \Delta}{\varepsilon} k^4\right)\) 最坏情况	\(O\left(\frac{\log \Delta}{\varepsilon} k^3\right)\)	适应性 (Adaptive)
本文高精度算法 (Sec 3)	带生命周期动态 (Lifetimes)	\(2+\varepsilon\)	\(O\left(\frac{\log \Delta}{\varepsilon} k + \max_t \log \\|X_t\\|\right)\) 摊还	\(O\left(\frac{\log \Delta}{\varepsilon} \\|X_t\\|\right)\)	度量适应性 (Metric-Adaptive)
本文空间高效算法 (Sec 4)	\(H\)-有序动态流 (Lifetimes)	\(6+\varepsilon\)	\(O\left(\frac{\log \Delta}{\varepsilon} \min\{k+H, \\|X_t\\|\}\right)\) 最坏情况	\(O\left(\frac{\log \Delta}{\varepsilon} \min\{k+H, \\|X_t\\|\}\right)\)	度量适应性 (Metric-Adaptive)

配置变体	核心变动说明	运行时间规模 / 内存状态	理论分析与说明
完整算法 1 (Full Model)	启用中心寿命贪心选择 + 条件 Reclustering	\(O(n k)\) 总操作数，摊还 \(\widetilde{O}(k)\)	势能严格单调，消亡点最多触发一次重新规整
消融 Reclustering (w/o Reclustering)	禁用式 (2) 触发的级联重构，仅被动删除并局部填补	最坏情况总操作数退化至 \(\Theta(n^2)\)	见 Remark 3.1 构造序列：多次级联搬迁导致二次方开销
消融中心寿命优选 (Random Center)	出现空缺时任意挑选点作为新中心	摊还更新时间升至 \(O(k^2)\)	频繁产生持久点，破坏消亡单调吸收机制
空间算法：\(H = 0\) (严格 FIFO / 滑动窗口)	约束点删除次序与到达次序严格单调一致	内存 \(O\left(\frac{\log \Delta}{\varepsilon} k\right)\)，时间最坏情况 \(O(k)\)	完全匹配滑动窗口模型的最优渐近理论界
空间算法：\(H = O(k)\) (低抖动有序流)	允许局部窗口大小为 \(O(k)\) 的有限乱序到期	内存 \(O\left(\frac{\log \Delta}{\varepsilon} k\right)\)，最坏情况时间 \(\widetilde{O}(k)\)	保持严格亚线性内存，有效覆盖工业批处理流
**空间算法：$H \ge \Omega(	X_t	)$ (极端任意乱序)**	删除时间完全无序，任意长生命周期穿插