Techniques for ensuring differential privacy in top-K selection are provided. In one technique, multiple items and multiple counts are identified in response to a query. For each count, which corresponds to a different item, a noise value is generated and added to the count to generate a noisy value, and the noisy value is added to a set of noisy values that is initially empty. A particular noise value is generated for a particular count and added to the particular count to generate a noisy threshold. The particular noise value is generated using a different technique than the technique used to generate each noise value in the set. Based on the noisy threshold, a subset of the noisy values is identified, where each noisy value in the subset is less than the noisy threshold. A response to the query is generated that excludes items that correspond to the subset.