Private heavy node finding in trees with very low error
BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height
Cryptography and SecurityData Structures and Algorithms
Summary
Finding important nodes in tree-structured data is useful but tricky when keeping user data private. Existing methods add significant error that grows with the tree’s depth. The authors created an algorithm called BetweenCut that keeps privacy while adding much less error, growing only very slowly with tree height. This approach works for all nodes at once and does not depend on how much data there is.
What this means in practice
- •For data privacy engineers: Improve privacy-preserving analytics on hierarchical datasets by reducing error in detecting frequent nodes in deep trees without increasing privacy loss.
- •For database administrators: Enable more accurate identification of heavily accessed or important nodes in tree-indexed databases while maintaining strong user privacy guarantees.
Authors
Ergute Bao, Graham Cormode, Xiaokui Xiao, Ting Yu
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.