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 |
|---|---|---|---|---|
| 137 | Revealing Information while Preserving Privacy | 2003 | PODS | 0.00042381562 |
| 451 | Towards Practical Differential Privacy for SQL Queries | 2018 | VLDB | 0.00022807098 |
| 567 | Practical Privacy: The SuLQ Framework | 2005 | PODS | 0.00019940193 |
| 1,516 | PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions | 2016 | SIGMOD | 0.00011558246 |
| 2,688 | On Differentially Private Frequent Itemset Mining | 2013 | VLDB | 8.3012815e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,436 | Optimizing error of high-dimensional statistical queries under differential privacy | 2018 | VLDB | 8.8217855e-05 |
| 12,303 | Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes | 2009 | PODS | 4.1905499e-05 |
| 5,410 | Practical Authenticated Pattern Matching with Optimal Proof Size | 2015 | VLDB | 5.5214688e-05 |
| 742 | Optimizing Linear Counting Queries Under Differential Privacy | 2010 | PODS | 0.00017336928 |
| 137 | Revealing Information while Preserving Privacy | 2003 | PODS | 0.00042381562 |
| 7,584 | A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries | 2022 | PODS | 4.7015411e-05 |
| 5,773 | Mining Frequent Patterns with Differential Privacy | 2013 | VLDB | 5.3300095e-05 |
| 3,103 | Publishing Set-Valued Data via Differential Privacy | 2011 | VLDB | 7.5578714e-05 |
| 1,928 | A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy | 2014 | VLDB | 0.00010062105 |
| 5,825 | Space-efficient Substring Occurrence Estimation | 2011 | PODS | 5.3119504e-05 |