论文标题
差异私人上$ K $的联合指数机制
A Joint Exponential Mechanism For Differentially Private Top-$k$
论文作者
论文摘要
我们提出了一种差异私有算法，用于释放从$ d $元素的数据域中最高计数的$ k $元素的顺序。该算法是指数机制的“关节”实例，其输出空间由所有$ o（d^k）$ length- $ k $序列组成。我们的主要贡献是一种在时间$ O（dk \ log（k） + d \ log（d））$和space $ o（dk）$的时间$ o（dk \ log（k） + d \ log（d \ log（dk）$）中采样的方法。实验表明，这种方法的表现优于现有的纯差分隐私方法，并且甚至在中等$ k $的近似差异隐私方法中改进。
We present a differentially private algorithm for releasing the sequence of $k$ elements with the highest counts from a data domain of $d$ elements. The algorithm is a "joint" instance of the exponential mechanism, and its output space consists of all $O(d^k)$ length-$k$ sequences. Our main contribution is a method to sample this exponential mechanism in time $O(dk\log(k) + d\log(d))$ and space $O(dk)$. Experiments show that this approach outperforms existing pure differential privacy methods and improves upon even approximate differential privacy methods for moderate $k$.
