Timezone: »

 
Poster
Differentially Private n-gram Extraction
Kunho Kim · Sivakanth Gopi · Janardhan Kulkarni · Sergey Yekhanin

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »
We revisit the problem of $n$-gram extraction in the differential privacy setting. In this problem, given a corpus of private text data, the goal is to release as many $n$-grams as possible while preserving user level privacy. Extracting $n$-grams is a fundamental subroutine in many NLP applications such as sentence completion, auto response generation for emails, etc. The problem also arises in other applications such as sequence mining, trajectory analysis, etc., and is a generalization of recently studied differentially private set union (DPSU) by Gopi et al. (2020). In this paper, we develop a new differentially private algorithm for this problem which, in our experiments, significantly outperforms the state-of-the-art. Our improvements stem from combining recent advances in DPSU, privacy accounting, and new heuristics for pruning in the tree-based approach initiated by Chen et al. (2012).
Keywords: Privacy

Author Information

Kunho Kim (Microsoft)
Sivakanth Gopi (Microsoft Research)

Sivakanth Gopi is a senior researcher in the Algorithms group at Microsoft Research Redmond. He is interested in Coding Theory and Differential Privacy.

Janardhan Kulkarni (Microsoft Research)
Sergey Yekhanin (Microsoft)

More from the Same Authors