Differential Privacy.pdf

The proposed method satisfies approximate differential privacy for top-k selection with unordered output in the unknown data domain setting. It only requires looking at the top-¯k elements for any given ¯k ≥k, enforcing the principle of minimal privilege. The algorithm combines the sparse vector technique and stability, giving improved applicability for scenarios with very large k. The privacy parameter ε does not scale with k, and the construction can be applied as a general framework to any type of query. The method is compared to previous work, including the Limited Domain (LD) procedure, and shows improved results in various settings. The code and experimental trials are made publicly available. Key contributions include:

A new differentially private top-k selection algorithm for the unknown domain setting
Improved combination of SVT and Stability techniques
Privacy budget ε independent of k
Better parameters than previous work
Empirical evaluation on real-world datasets
Publicly available code and experimental trials

The method has strong applicability to scenarios with large domains and top-k selections with very large k, and is of independent interest as it can be used for general queries, not just top-k selection.