2024/12/18 by Bernardini, Giulia, Bille, Philip, Gørtz, Inge Li +1
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2412.13813
Differential privacy is the gold standard for privacy in data analysis. In many data analysis applications, the data is a database of documents. For databases consisting of many documents, one of the most fundamental problems is that of pattern matching and computing (i) how often a pattern appears as a substring in the database (substring counting) and (ii) how many documents in the collection contain the pattern as a substring (document counting). In this paper, we initiate the theoretical study of substring and document counting under differential privacy. We give an ε-differentially private data structure solving this problem for all patterns simultaneously with a maximum additive error of O(ℓ \cdotpolylog(nℓ|Σ|)), where ℓ is the maximum length of a document in the database, n is the number of documents, and |Σ| is the size of the alphabet. We show that this is optimal up to a O(polylog(nℓ)) factor. Further, we show that for (ε,δ)-differential privacy, the bound for document counting can be improved to O(√(ℓ) \cdotpolylog(nℓ|Σ|)). Additionally, our data structures are efficient. In particular, our data structures use O(nℓ2) space, O(n2ℓ4) preprocessing time, and O(|P|) query time where P is the query pattern. Along the way, we develop a new technique for differentially privately computing a general class of counting functions on trees of independent interest. Our data structures immediately lead to improved algorithms for related problems, such as privately mining frequent substrings and q-grams. For q-grams, we further improve the preprocessing time of the data structure.