# Differentially Private Set Union

arXiv: https://arxiv.org/abs/2002.09745 · HTML: https://mlsanity.com/paper/2002.09745/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2020.

## Built on by (most cited first, 14 of 14)

- [Differentially Private Synthetic Data via Foundation Model APIs 1: Images](https://mlsanity.com/paper/2305.15560/) (2023)
- [Submix: Practical Private Prediction for Large-Scale Language Models](https://mlsanity.com/paper/2201.00971/) (2022)
- [Secure Federated Clustering](https://mlsanity.com/paper/2205.15564/) (2022)
- [Differentially Private n-gram Extraction](https://mlsanity.com/paper/2108.02831/) (2021)
- [Sparsity-Preserving Differentially Private Training of Large Embedding Models](https://mlsanity.com/paper/2311.08357/) (2023)
- [Language Scaling for Universal Suggested Replies Model](https://mlsanity.com/paper/2106.02232/) (2021)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [Membership Inference Attacks and Privacy in Topic Modeling](https://mlsanity.com/paper/2403.04451/) (2024)
- [N-grams Bayesian Differential Privacy](https://mlsanity.com/paper/2101.12736/) (2021)
- [On Privacy and Confidentiality of Communications in Organizational Graphs](https://mlsanity.com/paper/2105.13418/) (2021)
- [Training with Differential Privacy: A Gradient-Preserving Noise Reduction Approach with Provable Security](https://mlsanity.com/paper/2409.11663/) (2024)
- [Synonymix: Unified Group Personas for Generative Simulations](https://mlsanity.com/paper/2603.28066/) (2026)
- [Sherpa.ai Privacy-Preserving Multi-Party Entity Alignment without Intersection Disclosure for Noisy Identifiers](https://mlsanity.com/paper/2604.19219/) (2026)
- [Tight End-to-End Accounting for Differentially Private Synthetic Data](https://mlsanity.com/paper/2610.17249/) (2026)

## Abstract (arXiv)

We study the basic operation of set union in the global model of differential privacy. In this problem, we are given a universe U of items, possibly of infinite size, and a database D of users. Each user i contributes a subset Wi subseteq U of items. We want an (ε,δ)-differentially private algorithm which outputs a subset S subset cupi Wi such that the size of S is as large as possible. The problem arises in countless real world applications; it is particularly ubiquitous in natural language processing (NLP) applications as vocabulary extraction. For example, discovering words, sentences, n-grams etc., from private text data belonging to users is an instance of the set union problem. Known algorithms for this problem proceed by collecting a subset of items from each user, taking the union of such subsets, and disclosing the items whose noisy counts fall above a certain threshold. Crucially, in the above process, the contribution of each individual user is always independent of the items held by other users, resulting in a wasteful aggregation process, where some item counts happen to be way above the threshold. We deviate from the above paradigm by allowing users to contribute their items in a textitdependent fashion, guided by a textitpolicy. In this new setting ensuring privacy is significantly delicate. We prove that any policy which has certain textitcontractive properties would result in a differentially private algorithm. We design two new algorithms, one using Laplace noise and other Gaussian noise, as specific instances of policies satisfying the contractive properties. Our experiments show that the new algorithms significantly outperform previously known mechanisms for the problem.