# Fast and Optimal Differentially Private Frequent-Substring Mining

arXiv: https://arxiv.org/abs/2603.09166 · HTML: https://mlsanity.com/paper/2603.09166/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Mar 2026.

## Built on by (most cited first, 1 of 1)

- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)

## Abstract (arXiv)

Given a dataset of n user-contributed strings, each of length at most ℓ, a key problem is how to identify all frequent substrings while preserving each user's privacy. Recent work by Bernardini et al. (PODS'25) introduced a varepsilon-differentially private algorithm achieving near-optimal error, but at the prohibitive cost of O(n2ℓ4) space and processing time. In this work, we present a new varepsilon-differentially private algorithm that retains the same near-optimal error guarantees while reducing space complexity to O(n ℓ+ |Sigma| ) and time complexity to O(n ℓlog |Sigma| + |Sigma| ), for input alphabet Sigma. Our approach builds on a top-down exploration of candidate substrings but introduces two new innovations: (i) a refined candidate-generation strategy that leverages the structural properties of frequent prefixes and suffixes, and (ii) pruning of the search space guided by frequency relations. These techniques eliminate the quadratic blow-ups inherent in prior work, enabling scalable frequent substring mining under differential privacy.