一种快速、可合并且兼容LDP的算法，用于统计完全动态表中不同值的数量

《Proceedings of the ACM on Management of Data》：A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables

支持动态插入和删除的轻量级LDP兼容NDV估计方法

　　

摘要

计算不同值的数量（NDV）是Web应用程序和数据库中的一个基本问题，尤其是在内存受限的情况下。基于草图的方法（如Flajolet-Martin草图）可以构建紧凑的数据摘要来估计NDV，但主要关注仅插入操作的场景。然而，在许多实际应用中（如数据库），支持删除操作对于保持准确和最新的基数估计至关重要。现有的完全动态场景方法（同时涉及插入和删除操作）通常会带来相当大的计算和内存开销。此外，协作计算通常需要与外部或不受信任的方共享草图，这会引入重大的隐私风险。为了解决这些挑战，我们提出了一种新颖的草图方法GMod，该方法专为完全动态场景设计，并且与局部差分隐私（LDP）兼容，可用于NDV估计和隐私保护。我们的方法通过使用一个单一的离散均匀分布随机变量来支持高效的删除操作，同时将额外开销降至最低。此外，我们引入了一个轻量级的概率估计模型来计算NDV，其性能比现有最先进方法快3倍。通过结合精心设计的草图扰动机制，我们的模型减轻了LDP噪声的影响。实验结果表明，我们的方法在本地环境中使用1/3的内存即可实现与现有方法相当的估计精度，并且在LDP场景下提供了8倍更高的精度。