Tight Data Access Bounds for Private Top-k Selection

We study the top-k selection problem under the differential privacy model: m items are rated according to votes of a set of clients. We consider a setting in which algorithms can retrieve data via a sequence of accesses, each either a random access or a sorted access; the goal is to minimize the total number of data accesses. Our algorithm requires only O( √ mk) expected accesses: to our knowledge, this is the first sublinear data-access upper bound for this problem. Our analysis also shows that the well-known exponential mechanism requires only O( √ m) expected accesses. Accompanying this, we develop the first lower bounds for the problem, in three settings: only random accesses; only sorted accesses; a sequence of accesses of either kind. We show that, to avoid Ω(m) access cost, supporting both kinds of access is necessary, and that in this case our algorithm's access cost is optimal. Example 1.1. Consider the example of a movie ranking database. It can present the movies in sorted order, according to their ratings by the clients, or it can return directly the rating of a specific movie.