  We study the problem of top-$k$ selection over a large domain universe
subject to user-level differential privacy. Typically, the exponential
mechanism or report noisy max are the algorithms used to solve this problem.
However, these algorithms require querying the database for the count of each
domain element. We focus on the setting where the data domain is unknown, which
is different than the setting of frequent itemsets where an apriori type
algorithm can help prune the space of domain elements to query. We design
algorithms that ensures (approximate) $(\epsilon,\delta>0)$-differential
privacy and only needs access to the true top-$\bar{k}$ elements from the data
for any chosen $\bar{k} \geq k$. This is a highly desirable feature for making
differential privacy practical, since the algorithms require no knowledge of
the domain. We consider both the setting where a user's data can modify an
arbitrary number of counts by at most 1, i.e. unrestricted sensitivity, and the
setting where a user's data can modify at most some small, fixed number of
counts by at most 1, i.e. restricted sensitivity. Additionally, we provide a
pay-what-you-get privacy composition bound for our algorithms. That is, our
algorithms might return fewer than $k$ elements when the top-$k$ elements are
queried, but the overall privacy budget only decreases by the size of the
outcome set.
