Bounded Space Differentially Private Quantiles
Bounded Space Differentially Private Quantiles
复制标题
有界空间微分私有分位数
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Anamay Chaturvedi
中科院分区：
文献类型：
--
作者：
Daniel Alabi;Omri Ben;Anamay Chaturvedi
估计大型数据集的分位数是流算法文献和差分隐私文献中的一个基本问题。然而，所有现有的与分布无关的分位数计算的私有机制都需要空间至少与输入大小 $n$ 成线性。在这项工作中，我们为分位数估计问题设计了一种差分隐私算法，在一次性和连续观察设置中具有强次线性空间复杂度。我们的基本机制使用 $O\left( \frac{\log (|\mathcal{X}|/\beta) \log (\alpha \epsilon n)}{\alpha \epsilon} \right)$ 空间以概率 $1-\beta$ 估计数据宇宙 $\mathcal{X}$ 上长度 $n$ 流的任何 $\alpha$ 近似分位数，同时满足单个时间点的 $\epsilon$-差分隐私。我们的方法基于用于非私有分位数估计的确定性流算法，使用草图项目上定义的效用函数实例化指数机制，同时从草图定义的间隔（私有）采样。我们还提出了另一种基于直方图的算法，该算法特别适合多分位数情况。我们实现我们的算法，并在合成和真实数据集上对它们进行实验评估。
Estimating the quantiles of a large dataset is a fundamental problem in both the streaming algorithms literature and the differential privacy literature. However, all existing private mechanisms for distribution-independent quantile computation require space at least linear in the input size $n$. In this work, we devise a differentially private algorithm for the quantile estimation problem, with strongly sublinear space complexity, in the one-shot and continual observation settings. Our basic mechanism estimates any $\alpha$-approximate quantile of a length-$n$ stream over a data universe $\mathcal{X}$ with probability $1-\beta$ using $O\left( \frac{\log (|\mathcal{X}|/\beta) \log (\alpha \epsilon n)}{\alpha \epsilon} \right)$ space while satisfying $\epsilon$-differential privacy at a single time point. Our approach builds upon deterministic streaming algorithms for non-private quantile estimation instantiating the exponential mechanism using a utility function defined on sketch items, while (privately) sampling from intervals defined by the sketch. We also present another algorithm based on histograms that is especially suited to the multiple quantiles case. We implement our algorithms and experimentally evaluate them on synthetic and real-world datasets.
登录
查看更多内容
DOI：
10.1145/3471485.3471488
发表时间：
2020-03
期刊：
ACM SIGMOD Record
影响因子：
--
作者：
Omri Ben-Eliezer;Rajesh Jayaram;David P. Woodruff;E. Yogev
通讯作者：
Omri Ben-Eliezer;Rajesh Jayaram;David P. Woodruff;E. Yogev
影响因子：
--
作者：
Alabi, Daniel;McMillan, Audra;Sarathy, Jayshree;Smith, Adam;Vadhan, Salil
通讯作者：
Vadhan, Salil
DOI：
--
发表时间：
2020-11
期刊：
ArXiv
影响因子：
--
作者：
Christos Tzamos;Emmanouil-Vasileios Vlatakis-Gkaragkounis;Ilias Zadik
通讯作者：
Christos Tzamos;Emmanouil-Vasileios Vlatakis-Gkaragkounis;Ilias Zadik
有限计算机上的差异隐私
影响因子：
--
作者：
Balcer, Victor;Vadhan, Salil
通讯作者：
Vadhan, Salil
相对误差流分位数
影响因子：
2.5
作者：
Cormode, Graham;Karnin, Zohar;Liberty, Edo;Thaler, Justin;Veselý, Pavel
通讯作者：
Veselý, Pavel