# Differentially Private n-gram Extraction

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 17 references that are in the map.
- First posted on arXiv 5 Aug 2021.

## Builds on (most cited first, 7 of 7)

- [The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks](https://mlsanity.com/paper/1802.08232/) (2018)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Gmail Smart Compose: Real-Time Assisted Writing](https://mlsanity.com/paper/1906.00080/) (2019)
- [Convolutional Neural Network Architectures for Matching Natural Language Sentences](https://mlsanity.com/paper/1503.03244/) (2015)
- [Smart Reply: Automated Response Suggestion for Email](https://mlsanity.com/paper/1606.04870/) (2016)
- [Diversifying Reply Suggestions using a Matching-Conditional Variational Autoencoder](https://mlsanity.com/paper/1903.10630/) (2019)
- [Differentially Private Set Union](https://mlsanity.com/paper/2002.09745/) (2020)

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

- [Submix: Practical Private Prediction for Large-Scale Language Models](https://mlsanity.com/paper/2201.00971/) (2022)
- [Differentially Private Natural Language Models: Recent Advances and Future Directions](https://mlsanity.com/paper/2301.09112/) (2023)
- [The Canary's Echo: Auditing Privacy Risks of LLM-Generated Synthetic Text](https://mlsanity.com/paper/2502.14921/) (2025)
- [Differential Privacy in Natural Language Processing: The Story So Far](https://mlsanity.com/paper/2208.08140/) (2022)
- [Privacy-Preserving Domain Adaptation of Semantic Parsers](https://mlsanity.com/paper/2212.10520/) (2022)
- [Differentially Private Heavy Hitter Detection using Federated Analytics](https://mlsanity.com/paper/2307.11749/) (2023)
- [A Systematic Exploration of Text Decomposition and Budget Distribution in Differentially Private Text Obfuscation](https://mlsanity.com/paper/2605.01065/) (2026)
- [Evaluating utility in synthetic banking microdata applications](https://mlsanity.com/paper/2410.22519/) (2024)

## Abstract (arXiv)

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, response generation for emails etc. The problem also arises in other applications such as sequence mining, and is a generalization of recently studied differentially private set union (DPSU). 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).