Abstract
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 ε-differentially private algorithm achieving near-optimal error, but at the prohibitive cost of O(n²ℓ⁴) space and processing time. In this work, we present a new ε-differentially private algorithm that retains the same near-optimal error guarantees while reducing space complexity to O(n ℓ+ |Σ| ) and time complexity to O(n ℓlog |Σ| + |Σ| ), for input alphabet Σ. 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.