Preprint Open access
BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height
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, allo …