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: 1998
Venue: PODS
Year: 2025
Pagerank: 5.0723324e-05
Overall Rank: 10,725 | 26.67%
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
123	Revealing Information while Preserving Privacy	2003	PODS	0.00030957525
283	Towards Practical Differential Privacy for SQL Queries	2018	VLDB	0.0002238608
514	Practical Privacy: The SuLQ Framework	2005	PODS	0.00017151811
1,314	PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions	2016	SIGMOD	0.00011177323
2,373	On Differentially Private Frequent Itemset Mining	2013	VLDB	8.6507669e-05

Semantically Similar Papers

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