An Improved Error Bound for Differentially Private Frequent-Substring Mining

Given a dataset of $n$ user-contributed strings, each of length at most $\ell$, we study the problem of identifying frequent substrings under user-level $\epsilon$-differential privacy. Bernardini et al. (PODS '25) gave an $\epsilon$-differentially private algorithm with near-optimal error guarantees, but its $O(n^2{\ell }^4)$ time and space complexity makes it impractical at scale. More recent work by Guo et al. (ICDT '27) achieves near-linear efficiency, but at the cost of additional polylogarithmic factors in the error. We obtain the best of both works, providing a new $\epsilon$-differentially private algorithm that improves the near-optimal error guarantees of Bernardini et al. while achieving near-linear time and space. Our main technical contribution is a differentially private virtual search tree that succinctly represents all sufficiently frequent substrings contained in the dataset. We search this tree with a private top-down search framework for monotone trees, which combines heavy-light tree decomposition with the sparse vector technique. The framework is implemented through constant-time frequency and subtree-size oracles, enabling private path searches and heavy-path decisions without fully materializing the underlying tree. This yields a scalable private frequent-substring mining algorithm with near-optimal privacy-utility tradeoffs and near-linear resource bounds. Specifically, with failure probability at most $\beta$, our algorithm achieves additive error $O\left(\frac{\ell \log (n\ell )}{\epsilon }\log \frac{n\ell }{\beta }\right)$.