A Joint Exponential Mechanism For Differentially Private Top-$k$
This work addresses privacy-preserving data analysis for applications like frequent itemset mining, offering a more efficient solution for releasing top-k counts, though it is incremental in improving upon existing differential privacy techniques.
The paper tackles the problem of releasing the top-k elements with high counts under differential privacy, presenting a joint exponential mechanism algorithm that achieves improved performance over existing methods, with experiments showing it outperforms pure and even approximate differential privacy approaches for moderate 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$.