A Joint Exponential Mechanism For Differentially Private Top-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(dk) length-k sequences. Our main contribution is a method to sample this exponential mechanism in time O(dklog(k) + dlog(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.