BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height

arXiv:2610.10075 · cs.CR, cs.DS · Submitted 2026-10-07 · Read on arXiv

cs.CR, cs.DS

Submitted: 2026-10-07

Updated: 2026-10-07

License: http://creativecommons.org/licenses/by/4.0/

The gist: Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data.

Terminology

Differential Privacy — 17× in this paper · explained in 4 episodes
Differentially Private — 16× in this paper · explained in 3 episodes
Accuracy — 8× in this paper · explained in 1 episode
Sparse Vector Technique — 5× in this paper
Calibration — 4× in this paper · explained in 7 episodes
Consistency — 4× in this paper · explained in 3 episodes
Generative AI — 3× in this paper · explained in 2 episodes
Adam — 1× in this paper · explained in 2 episodes
Clustering — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
Pruning — 1× in this paper · explained in 4 episodes
Sparsity — 1× in this paper · explained in 4 episodes

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 Ω epsilon,δ(h) or Ω epsilon,δ(sqrt h) for tree height h. We introduce BetweenCut, an (epsilon,δ) -DP algorithm with an additive error margin of O epsilon,δ(h), improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size.

Terminology

Abstract

Related papers