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)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 136 | Revealing Information while Preserving Privacy | 2003 | PODS | 0.0004241101 |
| 453 | Towards Practical Differential Privacy for SQL Queries | 2018 | VLDB | 0.00022741848 |
| 568 | Practical Privacy: The SuLQ Framework | 2005 | PODS | 0.00019949368 |
| 1,520 | PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions | 2016 | SIGMOD | 0.00011535148 |
| 2,685 | On Differentially Private Frequent Itemset Mining | 2013 | VLDB | 8.3070708e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,434 | Optimizing error of high-dimensional statistical queries under differential privacy | 2018 | VLDB | 8.8278955e-05 |
| 12,295 | Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes | 2009 | PODS | 4.1945683e-05 |
| 5,404 | Practical Authenticated Pattern Matching with Optimal Proof Size | 2015 | VLDB | 5.5267144e-05 |
| 742 | Optimizing Linear Counting Queries Under Differential Privacy | 2010 | PODS | 0.00017360873 |
| 136 | Revealing Information while Preserving Privacy | 2003 | PODS | 0.0004241101 |
| 7,579 | A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries | 2022 | PODS | 4.706055e-05 |
| 5,772 | Mining Frequent Patterns with Differential Privacy | 2013 | VLDB | 5.3322378e-05 |
| 3,097 | Publishing Set-Valued Data via Differential Privacy | 2011 | VLDB | 7.5647028e-05 |
| 1,935 | A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy | 2014 | VLDB | 0.00010032967 |
| 5,813 | Space-efficient Substring Occurrence Estimation | 2011 | PODS | 5.3170565e-05 |