  Many data analysis operations can be expressed as a GROUP BY query on an
unbounded set of partitions, followed by a per-partition aggregation. To make
such a query differentially private, adding noise to each aggregation is not
enough: we also need to make sure that the set of partitions released is also
differentially private.
  This problem is not new, and it was recently formally introduced as
differentially private set union. In this work, we continue this area of study,
and focus on the common setting where each user is associated with a single
partition. In this setting, we propose a simple, optimal differentially private
mechanism that maximizes the number of released partitions. We discuss
implementation considerations, as well as the possible extension of this
approach to the setting where each user contributes to a fixed, small number of
partitions.
