- 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 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 . Following existing work (Bernardini et al. 2025), the error is quantified by an additive : strings occurring more than times must be reported, while those occurring less than 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 , is there a difference?
Q3. Is it an abuse of notation for and ?
Post-rebuttal: Please include discussions w.r.t. the PODS paper.
3 comments
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.
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ℓ+∣Σ∣). For ∣Σ∣=O(nℓ), this matches the worst-case asymptotic cost of one input scan. It also removes GHW’s log∣Σ∣ factor from the input-dependent runtime term, complementing our existing polylogarithmic improvement in additive error.
The current logℓ 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)−ℓ)+ and enumerate all substrings with positive shifted counts directly from the compact suffix tree. At any fixed length, at most n substrings have frequency greater than ℓ, giving O(nℓ) such substrings across all lengths. This reduces the overall runtime to O(nℓ+∣Σ∣). 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:
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