DPSW-Sketch: 隐私差分化滑动窗口频率估计的草图框架（技术报告）
原文中文，约1300字，阅读约需3分钟。
📝
内容提要
本文介绍了DS-FD算法及其在滑动窗口模型中的应用，证明了其在空间限制上的最优性。同时提出了动态RSS方法和混合化草图算法，以优化频率估计和数据流处理，强调隐私保护与效用的平衡。实验结果表明，这些算法在性能上优于传统方法。
🔎
延伸解读
滑动窗口模型下的空间最优性
文章证明DS-FD算法在归一化、基于序列的滑动窗口上达到最优O(d/ε)空间限制，并给出了基于时间和非归一化滑动窗口的匹配上下界。这表明该算法在不同滑动窗口模型中具有广泛适用性和理论最优性，为隐私差分化的频率估计提供了严格的空间效率保证。
动态RSS方法提升子集选择效率
针对数据流上代表性子集选择问题，文章提出动态RSS方法，在具有一般d-背包约束的滑动窗口上最大化子模函数。基于KnapWindow和KnapWindowPlus框架，实验显示在保持高质量解的同时，运行时间比批处理基线减少两个数量级以上，显著优化了流处理效率。
混合化草图算法与隐私保护平衡
文章结合联邦学习和安全加密协议，提出混合化草图算法，用于多轮次频率估计，并探讨草图大小的实际设置。同时，通过分布式算法实现隐私保护的高频数据发现，实验证明在强隐私保障下仍具有良好的效用，体现了隐私与效用之间的平衡。
❓
Q&A
DS-FD算法的空间限制是什么？
DS-FD算法在归一化的基于序列的滑动窗口上实现了最优的O(d/ε)空间限制。
动态RSS方法的主要功能是什么？
动态RSS方法优化了数据流中的代表性子集选择，显著减少了运行时间。
混合化草图算法是如何处理频率估计问题的？
混合化草图算法基于联邦学习和安全加密协议，能更准确地处理多轮次的频率估计问题。
这篇文章如何平衡隐私保护与效用？
文章提出了一种隐私保护的方法，强调隐私和效用之间的平衡，实验证明其具有良好的效用和强隐私保障。
DS-FD算法的广泛性和最优性是如何验证的？
DS-FD算法的广泛性和最优性通过理论和实证验证得以确认。
实验结果显示这些算法的性能如何？
实验结果表明，这些算法在性能上优于传统方法。
🏷️
