acceptodds
Under review as a conference paper at ICLR 2027

An Improved Error Bound for Differentially Private Frequent-Substring Mining

Abstract

Given a dataset of user-contributed strings, each of length at most , we study the problem of identifying frequent substrings under user-level -differential privacy. Bernardini et al. (PODS '25) gave an -differentially private algorithm with near-optimal error guarantees, but its 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 -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 , our algorithm achieves additive error .

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Differential Privacy, Natural Language Processing, Private LLM

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 2 reviews, above 68% of the others.
Reviewer_5zKiOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the problem of frequent substring discovery under DP. A dataset contains nn files (strings), and neighboring datasets differ by one file. The frequency of a query string is its total number of occurrence in all files. The target is to identify heavy-hitter strings whose frequency is above threshold τ\tau. Following existing work (Bernardini et al. 2025), the error is quantified by an additive α\alpha: strings occurring more than τ+α\tau+\alpha times must be reported, while those occurring less than τ−α\tau-\alpha times should not be reported.

There are two major components of the algorithm. In Section 3, the authors proposed a heavy-hitter search algorithm on trees that are monotone along any root-to-leaf path, by employing SVT. However, due to missing reference to a closely related work by Biswas et al. (PODS 2025), it is hard to recognize the novelty and technical contribution beyond prior work. Section 4 reduced the frequent substring discovery problem to the searching problem above, but the technique appears similar to that in Guo et al. (ICDT 2027), with inadequate discussion on the differences/improvements even after checking the appendix. Given that this is a pure-theory paper with no experiments justifying its practical improvements, my overall evaluation is weak reject. The paper would benefit from a more detailed comparison, with proper reference to prior work.

Critical strengths

S1. The paper addresses a meaningful problem and improves over recent STOA results.

S2. The proposed private HH search on monotone trees is a general framework not limited to the substring search scope.

Critical weaknesses

W1. The main design in Section 3, i.e. using SVT to search for heavy hitters along monotone trees, largely overlaps with the following reference from PODS 2025 (the same conference as the work cited in the 3rd line of the abstract):

Ari Biswas, Graham Cormode, Yaron Kanza, Divesh Srivastava, and Zhengyi Zhou. 2024. Differentially Private Hierarchical Heavy Hitters. Proc. ACM Manag. Data 2, 5 (PODS), Article 208 (November 2024), 25 pages. https://doi.org/10.1145/3695826

In particular, the missing reference studies the hierarchical heavy hitters (HHH) problem: given a tree with data-independent topology (similar to what Definition 3.2 in this paper assumes), counts for internal nodes of the tree is the sum over its children excluding those already identified as HHH. The observation in the PODS 25 paper is that each user only affects one leaf-to-root path, and once it is identified a HHH, subsequent counts are unaffected. It then proposed an SVT-based technique to run leaf-to-root discovery of HHH's.

The observation in this paper is not identical but similar. Definition 3.2 requires the counts to differ only on one root-to-node path, and the paper executes SVT iteratively on root-to-leaf paths, pruning subtree if its root is already light due to monotonicity. Therefore, instead of proposing SVT on trees as a novel idea, the paper should properly cite the PODS 25 work and provide detailed comparisons. One difference I observe is that the PODS 25 paper performs bottom-up search, whereas this paper does top-down DFS in specific order. However, the performance difference, e.g. through worst-case analyses, is unclear.

W2. The heavy-light decomposition appears in both BBGS (named heavy path decomposition) and GHW (same name). Yet Section 3.2 seem to claim novelty for its application in the proposed problem without reference to these closely related work. This can be confusing for readers. The authors should clearly distinguish between the design in this paper (if any) and those in existing works.

W3. Lemma 4.2 in the main text only specified the properties of the tree, with more important details on how the tree is constructed deferred to Appendix E and F. After reading, it appears similar to the construction in GHW, and there is no direct comparison provided for this design.

Questions for authors

Other than the weaknesses above, there are some minor issues:

Q1. Line 227, is there a typo for S vs P?

Q2. Line 323, V(T) is undefined. In particular, line 311 also used u∈Tu\in T, is there a difference?

Q3. Is it an abuse of notation for fT(u)f_T(u) and fD(S)f_{D}(S)?


Post-rebuttal: Please include discussions w.r.t. the PODS paper.

3 comments

We thank the reviewer for the careful review and constructive feedback. We will add the relevant references and clarify the distinctions from prior work.

New Improvement Since Submission

Before addressing the reviewers’ questions, we present a new post-submission improvement. An algorithmic modification reduces runtime from
O(nℓlog⁡ℓ+∣Σ∣)toO(nℓ+∣Σ∣).O(n\ell\log\ell+|\Sigma|) \quad \text{to} \quad O(n\ell+|\Sigma|). For ∣Σ∣=O(nℓ)|\Sigma|=O(n\ell), this matches the worst-case asymptotic cost of one input scan. It also removes GHW’s log⁡∣Σ∣\log|\Sigma| factor from the input-dependent runtime term, complementing our existing polylogarithmic improvement in additive error.

The current log⁡ℓ\log\ell factor comes from the full dataset scan used in Lemma B.7 at each dyadic scale to enumerate positive-frequency candidate concatenations for the sparse-histogram construction. To avoid these repeated scans, we apply the private sparse-histogram mechanism to shifted counts gD(P)=(fD(P)−ℓ)+g_D(P)=(f_D(P)-\ell)_+ and enumerate all substrings with positive shifted counts directly from the compact suffix tree. At any fixed length, at most nn substrings have frequency greater than ℓ\ell, giving O(nℓ)O(n\ell) such substrings across all lengths. This reduces the overall runtime to O(nℓ+∣Σ∣)O(n\ell+|\Sigma|). The shift does not increase sensitivity, so the existing privacy argument continues to apply, while the asymptotic error bound remains unchanged. We will include the full construction and analysis in the revised manuscript.

This refinement shows that our framework can achieve both linear runtime and the improved error guarantee.

W1. Distinction from Biswas et al. (PODS 2025). We refer to the updated version of their paper (arXiv:2606.13563), which revises the privacy and utility analysis.

Their algorithm achieves approximate DP and provides different utility guarantees for residual-count hierarchical heavy hitters. More importantly, directly adapting their bottom-up strategy to our pure-DP setting faces a fundamental efficiency challenge:

  1. Approximate DP. Their algorithm skips nodes with zero residual counts. In their setting, there are at most O(n)O(n) nonzero leaves. However, this strategy relies on approximate DP, as explicitly discussed in their paper.
  2. Pure DP. Skipping zero-count nodes in this manner does not preserve pure DP: a node with frequency zero in one dataset may have frequency 1 in a neighboring dataset, changing its probability of being reported from zero to positive. On the other hand, naively testing all leaves of a binary tree of height ℓ\ell requires Ω(2ℓ)\Omega(2^\ell) time.

Our top-down approach avoids this exponential search space while achieving pure DP and linear time and space.

W2. Heavy-light decomposition. We thank the reviewer for this suggestion. While we discuss the use of heavy-light decomposition in BBGS and GHW in Section 1.3 and Appendix A, we agree that the distinction could be clearer in Section 3.2. Our improvement is to combine heavy-light decomposition with SVT for private threshold search, achieving a better error bound. We will add explicit references and clarify this distinction.

W3. Global virtual tree. GHW searches each dyadic scale separately, incurring an additional logarithmic factor in the error due to composition. Our single global tree eliminates this factor. However, naively constructing such a tree incurs quadratic time and space, which we avoid through our new candidate construction and subtree-size oracle. We will clarify this distinction in the revision (see also our response to Reviewer NWtc for quantitative comparisons).

Questions

  • Q1: yes, it should be S.
  • Q2: V(T)V(T) denotes the node set of TT, and u∈Tu \in T is shorthand for u∈V(T)u \in V(T). In the revision, we will define V(T)V(T) and use u∈Tu \in T consistently.
  • Q3: ff is deliberately overloaded. The subscript names the object over which the frequency is taken. The two agree in the context of Lemma 4.2(3). We will state this more explicitly.

Thank you for the feedback. My biggest concern, comparison w.r.t. Biswas et al., has been addressed, and the distinction is valid. The comparisons are important for such similar designs, and should be included into the final paper in my opinion. Conditioned on it, the paper makes a nice theoretical contribution, and I will raise my rating to weak accept.

Thank you for raising your rating and for the constructive feedback. We will make sure to include the detailed comparison with Biswas et al. in the final revision.

Reviewer_NWtcOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper offers a new private algorithm for a natural problem on strings: The dataset consists of nn user-contributed strings, each of length at most ℓ\ell, and given a threshold parameter τ\tau and error parameter α\alpha, the goal is to output a set CC of highly frequent substrings, where substrings with frequency at least τ+α\tau + \alpha are in, and substrings with frequency less than τ−α\tau - \alpha are out. Here, a substring's frequency is the total number of its occurrences in the dataset. This paper studies this problem under the guarantee of ε\varepsilon-differential privacy, where the output is almost the same even if we change a single user-contributed string in the input. To evaluate the quality of a given solution, they use two criteria: (1) What is the error α\alpha (as a function of ℓ,ε,n\ell, \varepsilon, n and perhaps other parameters such as the alphabet size ∣Σ∣|\Sigma|, which is assumed to be ≤(nℓ)O(1)\leq (n \ell)^{O(1)}), and (2) What is the running time of the algorithm (as a function of n,ℓ,∣Σ∣n, \ell, |\Sigma|). Two relevant works are BBGS and GHW. BBGS presented an algorithm with near-optimal additive error, but its running time is O(n2ℓ4+∣Σ∣)O(n^2 \ell^4 + |\Sigma|), which is computationally expensive. GHW improves the running time to O(nℓlog⁡∣Σ∣+∣Σ∣)O(n\ell \log |\Sigma|+ |\Sigma|), but induces additional logarithmic factors in the error. The main contribution of this paper is to achieve GHW's running time without paying additional logarithmic factors in accuracy.

The algorithm builds on the idea that if a substring is frequent, then all its prefixes must also be frequent. This lets us view the problem as a tree search, where each node represents a substring and frequencies can only decrease as we move down the tree. The algorithm has two main steps:

  1. Like BBGS and GHW, it privately identifies a relatively small set of potentially frequent substrings of lengths 1,2,4,8,... The main difference is how it does this efficiently. BBGS considers all pairs of candidates when constructing longer substrings, which leads to high computational complexity. GHW avoids this expensive step and achieves near-linear running time. The current paper builds on these ideas but uses a private sparse histogram to efficiently construct the candidate sets, considering only pairs that actually occur in the dataset. The algorithm then uses these candidates to build a single virtual tree containing all potentially frequent substrings. This differs from GHW, which uses separate trees for different substring lengths, while BBGS already uses a single global tree but with much more expensive construction.

  2. Second, the algorithm privately searches this tree to identify frequent substrings. It uses heavy-light decomposition to divide the tree into paths and applies the sparse vector technique (SVT) to determine where frequencies fall below the desired threshold along each path. Unlike previous approaches that privately estimate many nodes' frequencies using the binary tree mechanism, SVT only needs to identify when a frequency drops below the threshold. Moreover, searching a single virtual tree avoids an additional privacy cost of searching separately at different substring lengths, as done in GHW.

Together, these ideas allow the authors to improve the error bound by logarithmic factors while maintaining near-linear running time and space complexity.

Critical strengths
  1. The studied problem is basic and easy to understand.
  2. The algorithm, while it has some parts similar to prior work, also has new parts that, overall, achieve strict quantitative improvements.
  3. The first step of the algorithm (see my summary) consists of new techniques, which seem non-trivial.
Critical weaknesses
  1. The quantitative improvements compared to GHW seem minor and not very exciting.
  2. The improvement comes from two steps (see my summary). The second step (replacing the binary tree mechanism with SVT) seems standard and straightforward, so the first step (identifying small sets of potentially frequent substrings) is likely the more interesting technical part. But after reading the first 9 pages, I still struggled to get a basic, intuitive understanding of this part and the actual improvement compared to GHW.
Questions for authors

It seems that the two steps of the algorithm (as I wrote in my summary) achieve independent improvements. Can you quantify the improvement from each step? For example, if we consider GHW but replace the binary-tree mechanism with SVT, what do we get?

3 comments

We thank the reviewer for the careful review and constructive feedback, and for the opportunity to clarify our key technical improvements.

New Improvement Since Submission

Before addressing the reviewers’ questions, we present a new post-submission improvement. An algorithmic modification reduces runtime from
O(nℓlog⁡ℓ+∣Σ∣)toO(nℓ+∣Σ∣).O(n\ell\log\ell+|\Sigma|) \quad \text{to} \quad O(n\ell+|\Sigma|). For ∣Σ∣=O(nℓ)|\Sigma|=O(n\ell), this matches the worst-case asymptotic cost of one input scan. It also removes GHW’s log⁡∣Σ∣\log|\Sigma| factor from the input-dependent runtime term, complementing our existing polylogarithmic improvement in additive error.

The current log⁡ℓ\log\ell factor comes from the full dataset scan used in Lemma B.7 at each dyadic scale to enumerate positive-frequency candidate concatenations for the sparse-histogram construction. To avoid these repeated scans, we apply the private sparse-histogram mechanism to shifted counts gD(P)=(fD(P)−ℓ)+g_D(P)=(f_D(P)-\ell)_+ and enumerate all substrings with positive shifted counts directly from the compact suffix tree. At any fixed length, at most nn substrings have frequency greater than ℓ\ell, giving O(nℓ)O(n\ell) such substrings across all lengths. This reduces the overall runtime to O(nℓ+∣Σ∣)O(n\ell+|\Sigma|). The shift does not increase sensitivity, so the existing privacy argument continues to apply, while the asymptotic error bound remains unchanged. We will include the full construction and analysis in the revised manuscript.

This refinement shows that our framework can achieve both linear runtime and the improved error guarantee.

Quantifying the error improvement. We consider two hypothetical modifications of GHW to isolate the contributions of our techniques. Recall that GHW achieves an additive error of

O(ℓln⁡2ℓˉεln⁡2nℓˉβ).O\left(\frac{\ell\ln^2\bar\ell}{\varepsilon}\ln^2\frac{n\bar\ell}{\beta}\right).

1. Replacing the binary-tree mechanism with SVT. Replacing GHW's binary-tree mechanism with SVT removes a factor of ln⁡ℓˉ\ln\bar{\ell} from the error bound while preserving its near-linear time and space complexity. This substitution alone, however, leaves the privacy cost of composition across dyadic scales unchanged.

2. Using a single global search tree. Replacing GHW's separate search trees with our single global tree and candidate construction also removes a factor of ln⁡ℓˉ\ln\bar{\ell} (due to composition) from the error bound.

More importantly, without the following two key techniques introduced in our paper, replacing GHW's separate search trees with a single global tree would increase its running time to O(n2ℓˉ2)O(n^2\bar{\ell}^2) under a straightforward implementation.

  1. Efficient candidate construction. The single global search tree requires identifying the candidates at all dyadic levels. Each level may contain O(n)O(n) candidates, so a brute-force approach that tests all pairs at the next level would already incur Ω(n2)\Omega(n^2) time. Our sparse-histogram-based construction avoids this quadratic bottleneck. And our new trick reduces runtime even further.

  2. Efficient subtree-size oracle. Searching the single global tree requires knowing the subtree sizes to perform heavy-light decomposition on the fly. Explicitly constructing the tree would incur quadratic time and space. Our key contribution is a succinct subtree-size oracle that exploits the combinatorial structure of the global tree to support O(1)O(1) expected-time queries with near-linear preprocessing time and space, enabling on-the-fly heavy-light decomposition without materializing the tree.

We will make these quantitative comparisons and the underlying technical challenges more explicit in the revision.

Thank you for the detailed response. I now understand the technical contribution better. Nevertheless, my main concern remains that the improvements over GHW are relatively modest (mainly removing logarithmic factors). While I acknowledge the non-trivial technical contributions, the overall approach largely builds on the framework developed in BBGS and GHW.

The post-submission running-time improvement looks promising, but since it was not part of the original submission, I give it limited weight in my evaluation (also, it does not substantially change my main concern).

Overall, I appreciate the clarifications provided, but I will keep my score unchanged at this point.

AuthorsOpenReview ↗

technical contribution

Thank you very much for your prompt follow-up and for recognizing our technical contributions. We truly appreciate the opportunity to provide a bit more context regarding the significance of the logarithmic improvements, and we have also uploaded a revised version of our paper incorporating your feedback.

Significance of logarithmic-factor improvements. The known lower bound for our problem is Ω(min⁡{n,ℓlog⁡∣Σ∣/ε})\Omega(\min\{n,\ell\log|\Sigma|/\varepsilon\}) (Table 1), so the remaining gap between upper and lower bounds in the nontrivial parameter regime is already polylogarithmic. Closing this gap is therefore the main remaining theoretical challenge.

Our original submission builds on BBGS and GHW and narrows this gap while retaining near-linear time and space. Crucially, this improvement is not achieved merely by tightening the analysis: without the new methods proposed in this paper (efficient dyadic candidate-set construction, sparse suffix tree construction, and virtual tree construction along with its size-oracle algorithm), this would not be possible in (near-)linear time, requiring O(n2ℓˉ2)O(n^2 \bar{\ell}^2) time instead, as discussed.

Indeed, improving logarithmic dependencies is an important and active research direction in differential privacy. This focus is also reflected in closely related work on approximate DP heavy-node classification. For example, Section 5.3 and Table 1 of BetweenCut [4] compare its error bounds against those of Lumberjack [3], as well as those obtained by adapting the methods of Ghazi et al. [1] and Biswas et al. [2] to the same setting. This comparison highlights successive improvements in the logarithmic dependence of the error on tree height. Although these works differ in their precise accuracy guarantees, they share a common research objective: reducing logarithmic factors through new algorithmic techniques. Appendix A of the revised manuscript discusses these four works in more detail.

Revised manuscript. We have uploaded the revised manuscript. The new Section 5 explains how our single virtual tree avoids the additional error that GHW incurs from composing private searches across scales. Appendix E gives the improved candidate construction and its running-time analysis. Appendix D proves that the full algorithm runs in linear time O(nℓ+∣Σ∣)O(n\ell + |\Sigma|). Thank you again for the careful discussion.

References

[1] Ghazi et al. On Differentially Private Counting on Trees. ICALP 2023.

[2] Biswas et al. Differentially Private Hierarchical Heavy Hitters. PODS 2025. Updated version.

[3] Lebeda et al. Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees. NeurIPS 2026.

[4] Bao et al. BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height. arXiv 2026.

Comments on the paper

2 comments

We thank the reviewer for the careful and constructive review, and for recognizing the key technical contributions of our work.

New Improvement Since Submission

Before addressing the reviewers’ questions, we present a new post-submission improvement. An algorithmic modification reduces runtime from
O(nℓlog⁡ℓ+∣Σ∣)toO(nℓ+∣Σ∣).O(n\ell\log\ell+|\Sigma|) \quad \text{to} \quad O(n\ell+|\Sigma|). For ∣Σ∣=O(nℓ)|\Sigma|=O(n\ell), this matches the worst-case asymptotic cost of one input scan. It also removes GHW’s log⁡∣Σ∣\log|\Sigma| factor from the input-dependent runtime term, complementing our existing polylogarithmic improvement in additive error.

The current log⁡ℓ\log\ell factor comes from the full dataset scan used in Lemma B.7 at each dyadic scale to enumerate positive-frequency candidate concatenations for the sparse-histogram construction. To avoid these repeated scans, we apply the private sparse-histogram mechanism to shifted counts gD(P)=(fD(P)−ℓ)+g_D(P)=(f_D(P)-\ell)_+ and enumerate all substrings with positive shifted counts directly from the compact suffix tree. At any fixed length, at most nn substrings have frequency greater than ℓ\ell, giving O(nℓ)O(n\ell) such substrings across all lengths. This reduces the overall runtime to O(nℓ+∣Σ∣)O(n\ell+|\Sigma|). The shift does not increase sensitivity, so the existing privacy argument continues to apply, while the asymptotic error bound remains unchanged. We will include the full construction and analysis in the revised manuscript.

This refinement shows that our framework can achieve both linear runtime and the improved error guarantee.

Presentation and scope. We agree that adding a compact proof overview and a short table outlining the proof dependencies would substantially improve the readability of our manuscript. We will also make the parameter assumptions more explicit in the introduction.

Q2 (Privacy of the output trie) Yes. The complete mechanism remains pure DP even when it outputs the discovered trie rather than just the set of decoded substrings.

Q3 (Time and space complexity). The reviewer is correct that our current analysis establishes expected-time guarantees. We will clarify the following points.

  • Sparse dyadic candidate construction. We use the sparse histogram algorithm of Cormode et al. (2012) for simplicity, which gives expected-time and space guarantees. Alternatively, we can use the algorithm of Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time (PODS 2026) to obtain deterministic time and space bounds for this component.

  • Number of explored nodes. As in BBGS and GHW, we can impose a deterministic cap on the number of nodes explored, aborting the search if this cap is exceeded, which happens only with low probability. Since the stopping rule depends only on the private search transcript, it preserves the pure DP guarantee and affects only utility.

We will qualify the runtime types explicitly in the revision.

AuthorsOpenReview ↗

revised manuscript

Dear Area Chair and Reviewers,

We have uploaded the revised manuscript. The main change is the post-submission improvement in expected running time from O(nℓlog⁡ℓ+∣Σ∣)O(n\ell\log\ell + |\Sigma|) to O(nℓ+∣Σ∣)O(n\ell + |\Sigma|), with the same pure-DP and additive-error guarantees as in the original submission.

  1. Linear-time algorithm and proof. Section 5.1 explains how a single suffix tree identifies substrings occurring more than ℓ\ell times across all dyadic lengths, eliminating repeated scans of the input during candidate construction. Appendix E gives the construction and its running-time analysis. Appendix D proves the bound for the full algorithm.

  2. Proof roadmap and privacy budget. Figure 2 maps the steps in the proof of Lemma 4.2 to the corresponding lemmas. It shows that tree construction and search each receive a user-level privacy budget of ε/2\varepsilon/2 and a failure probability budget of β/2\beta/2. Section 5.4 explains the privacy accounting, and Appendix D shows how candidate coverage and search accuracy together yield the final additive-error guarantee.

  3. Comparison with GHW. The new Section 5 explains how a single search on our virtual tree avoids the additional error that GHW incurs by composing private searches across dyadic scales.

  4. Private heavy hitters on trees. Appendix A now details the comparison with Biswas et al.'s bottom-up search algorithm. It also covers Ghazi et al., Lumberjack, and BetweenCut in the discussion of heavy-node classification under approximate DP.

We thank the reviewers for their thoughtful questions and suggestions, and we welcome further feedback on the revised manuscript.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.