论文标题
差异私人线性草图：有效的实现和应用程序
Differentially Private Linear Sketches: Efficient Implementations and Applications
论文作者
论文摘要
线性草图已被广泛采用来处理快速数据流，可以用来准确回答频率估计，近似k项并汇总数据分布。当数据敏感时，希望为线性草图提供隐私保证，以保留私人信息，同时以理论界限提供有用的结果。我们表明，线性草图可以在初始化时添加少量噪声来确保隐私并维护其独特的属性。从差异的私有线性草图中，我们展示了旋转门模型中最先进的分位数草图也可以是私有的并保持高性能。实验进一步表明，我们提出的差异私人草图在定量上与无噪声草图在合成和真实数据集上具有高利用率。
Linear sketches have been widely adopted to process fast data streams, and they can be used to accurately answer frequency estimation, approximate top K items, and summarize data distributions. When data are sensitive, it is desirable to provide privacy guarantees for linear sketches to preserve private information while delivering useful results with theoretical bounds. We show that linear sketches can ensure privacy and maintain their unique properties with a small amount of noise added at initialization. From the differentially private linear sketches, we showcase that the state-of-the-art quantile sketch in the turnstile model can also be private and maintain high performance. Experiments further demonstrate that our proposed differentially private sketches are quantitatively and qualitatively similar to noise-free sketches with high utilization on synthetic and real datasets.
