Before revision:  In this paper, we introduce theoneshot mechanism , a fast, low-distortion, and differentially private primitive for the top-k problem. Compared with existing approaches in the literature, our algorithm adds Laplace noise to the counts and releases the top-k noisy counts and their estimates in a oneshot fashion, thereby substantially reducing the computational cost while maintaining satisfying utility. Our /}\eps proof of privacy for this mechanism relies on a novel coupling technique that is of independent theoretical interest .
After revision:  In this paper, we introduce theoneshot mechanism , a fast, low-distortion, and differentially private primitive for the top-k elements. We show that the oneshot Laplace mechanism with a noise level of /}\eps proof of privacy for this mechanism relies on a novel coupling technique that is of independent theoretical interest .