A Differentially Private Data Structure for Substring and Document Counting
ACM SIGMOD Record · 23.04.2026 · 55 (1) · 41-49
DOI: 10.1145/3810900.3810908 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGMOD Record, online erschienen am 23.04.2026. Verfasst von Giulia Bernardini und 3 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben.
Abstract (Originalsprache)
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 (substring counting) and (ii) how many documents in the collection contain the pattern as a substring (document counting). If such a database contains sensitive data, it is crucial to protect the privacy of individuals in the database. Differential privacy is the gold standard for privacy in data analysis. It gives rigorous privacy guarantees, but comes at the cost of yielding less accurate results. In this paper, we study the problem of substring and document counting under differential privacy. We give the first differentially private data structures for these problems and provide bounds on their additive error. For ε-differential privacy, we show that the error of our data structure is optimal up to a poly-logarithmic factor in the number of documents and length of the longest document. Our data structures immediately lead to improved algorithms for related problems, such as privately mining frequent substrings and q-grams.
Zitieren
APA
Bernardini, G., Bille, P., Gørtz, I. L., & Steiner, T. A. (2026). A Differentially Private Data Structure for Substring and Document Counting. ACM SIGMOD Record, 55(1), 41-49. https://doi.org/10.1145/3810900.3810908
Vancouver
Bernardini G, Bille P, Gørtz IL, Steiner TA. A Differentially Private Data Structure for Substring and Document Counting. ACM SIGMOD Record. 2026;55(1):41-49. doi:10.1145/3810900.3810908
BibTeX
@article{Bernardini2026,
author = {Bernardini, Giulia and Bille, Philip and Gørtz, Inge Li and Steiner, Teresa Anna},
title = {A Differentially Private Data Structure for Substring and Document Counting},
journal = {ACM SIGMOD Record},
year = {2026},
volume = {55},
number = {1},
pages = {41--49},
doi = {10.1145/3810900.3810908}
}
EUVIMED