DP-SIPS: A simpler, more scalable mechanism for differentially private partition selection
Authors: Marika Swanberg (Boston University), Damien Desfontaines (Tumult Labs), Samuel Haney (Tumult Labs)
Volume: 2023
Issue: 4
Pages: 257–268
DOI: https://doi.org/10.56553/popets-2023-0109
Abstract: Partition selection, or set union, is an important primitive in differentially private mechanism design: in a database where each user contributes a list of items, the goal is to publish as many of these items as possible under differential privacy. In this work, we present a novel mechanism for differentially private partition selection. This mechanism, which we call {DP-SIPS}, is very simple: it consists of iterating the naive algorithm over the data set multiple times, removing the released partitions from the data set while increasing the privacy budget at each step. This approach preserves the scalability benefits of the naive mechanism, yet its utility compares favorably to more complex approaches developed in prior work.
Keywords: differential privacy, partition selection, scalable algorithms
Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution 4.0 license.
