Abstract
Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur additive error margins of $Ω_{\varepsilon,δ}(\log h)$ or $Ω_{\varepsilon,δ}(\sqrt{\log h})$ for tree height $h$. We introduce \textsc{BetweenCut}, an $(\varepsilon,δ)$-DP algorithm with an additive error margin of $O_{\varepsilon,δ}(\log\log h)$, improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Bao, E., Cormode, G., Xiao, X., & Yu, T. (2026). BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height. https://omanscience.com/en/articles/betweencut-private-heavy-node-classification-with-doubly-logarithmic-error-in-tree-height
MLA 9
Bao, Ergute, et al. "BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height." https://omanscience.com/en/articles/betweencut-private-heavy-node-classification-with-doubly-logarithmic-error-in-tree-height.
Chicago (author–date)
Bao, Ergute, Graham Cormode, Xiaokui Xiao, and Ting Yu. 2026. "BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height." https://omanscience.com/en/articles/betweencut-private-heavy-node-classification-with-doubly-logarithmic-error-in-tree-height.
Harvard
Bao, E., Cormode, G., Xiao, X. and Yu, T. (2026) 'BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height', Available at: https://omanscience.com/en/articles/betweencut-private-heavy-node-classification-with-doubly-logarithmic-error-in-tree-height.
Vancouver
Bao E, Cormode G, Xiao X, Yu T. BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height. https://omanscience.com/en/articles/betweencut-private-heavy-node-classification-with-doubly-logarithmic-error-in-tree-height
IEEE
E. Bao, G. Cormode, X. Xiao, and T. Yu, "BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height," https://omanscience.com/en/articles/betweencut-private-heavy-node-classification-with-doubly-logarithmic-error-in-tree-height.