Differentially Private Substring and Document Counting with Near-Optimal Error

Giulia Bernardini, Philip Bille, Inge Li Gørtz +1

For databases consisting of many text documents, one of the most fundamental data analysis tasks is counting (i) how often a pattern appears as a substring in the database (substri…