arXiv:2409.01688v3 宣布类型: replace-cross 摘要: 我们介绍了一种细化的同态差分隐私(DP)数据结构，用于核密度估计(KDE)，不仅提供了更好的隐私-实用性权衡，还在效率上超越了先前的结果。具体来说，我们研究了以下数学问题：给定一个相似性函数 \(f\)（或DP KDE）和一个私人数据集 \(X \subset \mathbb{R}^d\)，我们的目标是预处理 \(X\)，以便对于任何查询点 \(y \in \mathbb{R}^d\)，我们可以以差分隐私的方式近似 \(\sum_{x \in X} f(x, y)\)。对于 \(f(x, y) = \| x - y \|_1\)，最佳的先前算法是 [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024] 的节点污染平衡二叉树。他们的算法在预处理时需要 \(O(nd)\) 的空间和时间，其中 \(n=|X|\)。对于任何查询点，查询时间是 \(d \log n\)，且有 \((1+\alpha)\)-近似和误差界 \(\epsilon^{-1} \alpha^{-0.5} d^{1.5} R \log^{1.5} n\)。 在这篇论文中，我们从三个方面改进了 [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024] 的最佳先前结果： - 我们将查询时间减少了一个因子 \(\alpha^{-1} \log n\)。 - 我们将近似比从 \(\alpha\) 改进为 1。 - 我们将误差依赖性减少了一个因子 \(\alpha^{-0.5}\)。 从技术角度看，我们构建搜索树的方法不同于先前的工作 [Backurs, Lin, Mahabadi, Silwal, and Tarnawski, ICLR 2024]。在以前的工作中，对于每个查询，答案被分割成 \(\alpha^{-1} \log n\) 个数字，每个数字都是从区间树计数的 \(\log n\) 个值中得出的。相比之下，我们以不同的方式构建树，将答案分割成 \(\log n\) 个数字，每个数字是两个距离值、两个计数值和 \(y\) 本身的巧妙结合。我们认为我们的树结构可能具有独立的兴趣。