Abstract
We study the differentially private top-k selection problem, aiming to identify a sequence of k items with approximately the highest scores from d items. Recent work by Gillenwater et al. (ICML '22) employs a direct sampling approach from the vast collection of d^Θ(k) possible length-k sequences, showing superior empirical accuracy compared to previous pure or approximate differentially private methods. Their algorithm has a time and space complexity of O(dk). In this paper, we present an improved algorithm with time and space complexity O(d + k² / ε · ln d), where ε denotes the privacy parameter. Experimental results show that our algorithm runs orders of magnitude faster than their approach, while achieving similar empirical accuracy.