本文研究在线流式设置下的差分隐私(DP)k-means 与 k-median 聚类问题。在在线场景中,数据点按顺序持续到达,算法需在每个时间步基于已见数据输出一组 k 个中心,以最小化聚类代价(如 k-means 的平方距离和或 k-median 的绝对距离和)。此类设置广泛应用于实时分析、监控和个性化服务,但原始数据常包含敏感信息,直接聚类可能泄露隐私。为此,作者提出一种通用归约:先将敏感的输入流转换为一个'私有流'——实质上是原始输入流的半核心集(semi-coreset)。半核心集是一种压缩表示,能够在保持聚类目标近似精度的同时,降低数据敏感性并控制内存消耗。转换后的私有流可作为任何现有非私有在线聚类算法的输入,算法以后处理方式运行,从而在不修改原算法的情况下获得差分隐私保证。该归约的关键亮点在于继承了底层非私有算法的理想属性,特别是'一致性'(consistency)——即聚类结果对数据点的插入、删除及顺序变化保持稳定,这是先前 DP 在线聚类算法未能满足的性质。理论分析显示,该方法的近似比、空间复杂度和运行时间均匹配或优于现有最优算法(Epasto et al., 2026; Dupré la Tour et al., 2024)。本文为在线差分隐私聚类提供了一个通用、可扩展且保持一致的框架,对隐私保护数据挖掘和流式处理具有重要理论价值。
💡 推荐理由: 差分隐私是保护敏感数据的关键技术。本文提出的通用归约方法让任意在线聚类算法都能获得隐私保证,且保持一致性,为流式数据场景下的隐私保护分析(如用户行为统计、网络流量检测)提供了理论支撑。安全团队可借鉴该思路设计隐私友好的数据处理管道。
🎯 建议动作: 研究跟进