KDDJun, 2024

DPSW-Sketch: 隐私差分化滑动窗口频率估计的草图框架（技术报告）

PDF
TL;DR在滑动窗口模型中，提出了 DPSW-Sketch，一种基于计数最小化技术的算法，能够满足隐私性要求，并且在子线性时间和空间内近似估计任意项目的频率和重要项，实验结果显示其在效用和隐私权之间取得显著的权衡。
sliding window modelprivacyfrequency estimationheavy hittersdpsw-sketch
发现论文，激发创造
  • 滑动窗口下的最优矩阵草图

    我们介绍了 DS-FD 算法，它在归一化的、基于序列的滑动窗口上实现了最优的 O (d/ε) 空间限制。我们还提出了适用于基于时间和非归一化滑动窗口的匹配上限和下限空间限制，证明了 DS-FD 算法在各种滑动窗口模型中的广泛性和最优性。通过广泛的实验验证了我们的理论，从理论和实证两方面证实了我们算法的正确性和有效性。

    May, 2024

  • 改进的频率估计算法（带有或不带有预测）

    用机器学习技术改进估计频率的算法，特别是使用了重要元素预测的算法，在一些参数范围内以及加入重要元素预测后，理论上超越了之前算法的性能，并在实验中取得了优于其他方法的表现。

    Dec, 2023

  • 滑动窗口上高效的代表子集选择

    提出了一种在数据流上优化代表性子集选择的动态 RSS 方法，即最大化子模函数在具有一般 d - 背包约束 (SMDK) 的滑动窗口上。KnapWindow 框架（KW）利用 KnapStream 算法（KS）为 SMDK 策略中的 “添加仅” 数据流实例，提出 KnapWindowPlus 框架（KW$^{+}$）来改进 KW。实验结果表明，KW 和 KW$^{+}$ 在保持 SMDK 高质量解的同时，比批处理基线减少了两个数量级以上的运行时间。

    Jun, 2017

  • 本地、私有、高效的简明直方图协议

    本研究给出了关于差分隐私的本地模型下的频率估计的有效协议和匹配准确性下限，研究了能产生数据简明直方图表征的协议，以及在公共硬币模型下的协议。

    Apr, 2015

  • 私密联邦频率估计：适应实例的难度

    本文基于联邦学习和安全加密协议，提出了一种新的混合化草图算法，可用于对多轮次的频率估计问题进行更准确的处理，并探讨了如何根据实际情况设置草图大小，并验证了算法具有更好的性能。

    Jun, 2023

  • 具有差分隐私的联邦重要数据发现

    通过分布式算法，本文提出了一种隐私保护的方法来发现用户生成数据流中的高频数据，并探讨了隐私和效用之间的平衡，实验证明方法不仅具有良好的效用而且达到了强隐私保障。

    Feb, 2019

  • 基于格密码学的计算差分隐私

    本研究探讨大数据分析所带来的安全和隐私问题，研究了私有时间序列数据在分布式和半诚信环境下的统计分析问题，并提出了一种基于对称 Skellam 分布的扰动机制，可用于保护分布式数据的差分隐私性，并构建了一个计算有效的量子后学协议，该协议的安全性基于一种新型决策学习问题。

    Oct, 2017

  • 滑动窗口上的次模优化

    本文在数据流的上下文中，提供了一种基于滑动窗口模型的次模优化的近似算法，该算法维护了一个解决方案，考虑的仅是最后 $W$ 个元素，使用空间多项式对元素值的传播速度的对数级别，线性大小的解决方案，并保持高品质的解，实际表现远超理论界限。

    Oct, 2016

  • 基于学习的重量级命中者和流量频率在流中的估计

    通过使用基于竞争计数的算法，我们提出了一种称为 LSS 的学习算法，用于识别重要对象、top k 以及流量频率的估计，该算法充分利用了众所周知的 Space Saving 算法，并提供了理论洞察以及基于综合和真实世界数据集的实验结果，验证了 LSS 在提高 Space Saving 的准确性和效率方面的能力。

    Jun, 2024

  • 使用理论最优滑动窗口方法追踪动态高斯密度

    通过理论上的特征分类，我们提供了一个原则性指南，以选择最优的权重序列，从而改善卡尔曼滤波器在动态密度估计中的追踪效果。

    Mar, 2024