Differentially Private Substring and Document Counting

Summary: DP for substring and document counting in document collections; epsilon-DP data structure yields additive error O(l polylog(n l |Sigma|)) for all patterns, optimal up to polylog. For epsilon-delta DP, bound improves to O(sqrt(l) polylog(n l |Sigma|)); space O(n l^2), preprocessing O(n^2 l^4), query O(|P|); introduces a tree-counting technique enabling private mining of frequent substrings and q-grams. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha6d8c85cf913d138
Venue: PODS
Year: 2025
Pagerank: 4.9793485e-05
Overall Rank: 11,085 | 25.48%
DOI: 10.1145/3725232

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Giulia Bernardini (University of Milan)
2. Philip Bille (Technical University of Denmark)
3. Inge Li Gørtz (Technical University of Denmark)
4. Teresa Anna Steiner (University of Southern Denmark)

BibTeX Citation

@inproceedings{bernardini_pods25,
        address = {New York, NY, USA},
        series = {{PODS} '25},
        title = {{Differentially Private Substring and Document Counting}},
        url = {https://dl.acm.org/doi/10.1145/3725232},
        doi = {10.1145/3725232},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bernardini, Giulia and Bille, Philip and Gørtz, Inge Li and Steiner, Teresa Anna},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
122	Revealing Information while Preserving Privacy	2003	PODS	0.00030770793
276	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.0002234348
520	Practical Privacy: The SuLQ Framework	2005	PODS	0.00016939312
1,324	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011023355
2,416	On Differentially Private Frequent Itemset Mining	2013	VLDB	8.4962257e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,090	Optimizing error of high-dimensional statistical queries under differential privacy	2018	VLDB
2	12,780	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
3	5,485	Practical Authenticated Pattern Matching with Optimal Proof Size	2015	VLDB
4	625	Optimizing Linear Counting Queries Under Differential Privacy	2010	PODS
5	122	Revealing Information while Preserving Privacy	2003	PODS
6	7,439	A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries	2022	PODS
7	5,673	Mining Frequent Patterns with Differential Privacy	2013	VLDB
8	2,912	Publishing Set-Valued Data via Differential Privacy	2011	VLDB
9	1,528	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
10	6,952	Space-efficient Substring Occurrence Estimation	2011	PODS