2021/08/05 by Kunho Kim, Kim, Kunho, Sivakanth Gopi +5
Computer Science · Decision Sciences · #Cryptography and Data Security #Cryptography and Security (cs.CR) #Data Quality and Management #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2108.02831
openalex publication_date 2021/08/05 · openalex created_date 2021/08/16 · openalex updated_date 2026/07/28
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).