Timezone: »

Differentially Private Set Union
Sivakanth Gopi · Pankaj Gulhane · Janardhan Kulkarni · Judy Hanwen Shen · Milad Shokouhi · Sergey Yekhanin

Tue Jul 14 08:00 AM -- 08:45 AM & Tue Jul 14 07:00 PM -- 07:45 PM (PDT) @
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 $W_i \subseteq U$ of items. We want an ($\epsilon$,$\delta$)-differentially private Algorithm which outputs a subset $S \subset \cup_i W_i$ such that the size of $S$ is as large as possible. The problem arises in countless real world applications, and is particularly ubiquitous in natural language processing (NLP) applications. For example, discovering words, sentences, $n$-grams etc., from private text data belonging to users is an instance of the set union problem. In this paper we design new algorithms for this problem that significantly outperform the best known algorithms.

Author Information

Sivakanth Gopi (Microsoft)
Pankaj Gulhane (Microsoft)
Janardhan Kulkarni (Microsoft Research)
Judy Hanwen Shen (Microsoft Research)
Milad Shokouhi (Microsoft)
Sergey Yekhanin (Microsoft)

More from the Same Authors