# AHEAD: Adaptive Hierarchical Decomposition for Range Query under Local Differential Privacy

arXiv: https://arxiv.org/abs/2110.07505 · HTML: https://mlsanity.com/paper/2110.07505/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2021.

## Built on by (most cited first, 10 of 10)

- [FACE-AUDITOR: Data Auditing in Facial Recognition Systems](https://mlsanity.com/paper/2304.02782/) (2023)
- [SoK: Dataset Copyright Auditing in Machine Learning Systems](https://mlsanity.com/paper/2410.16618/) (2024)
- [DPMLBench: Holistic Evaluation of Differentially Private Machine Learning](https://mlsanity.com/paper/2305.05900/) (2023)
- [OpBoost: A Vertical Federated Tree Boosting Framework Based on Order-Preserving Desensitization](https://mlsanity.com/paper/2210.01318/) (2022)
- [ORL-AUDITOR: Dataset Auditing in Offline Deep Reinforcement Learning](https://mlsanity.com/paper/2309.03081/) (2023)
- [DPAdapter: Improving Differentially Private Deep Learning through Noise Tolerance Pre-training](https://mlsanity.com/paper/2403.02571/) (2024)
- [On the Privacy Risks of Cell-Based NAS Architectures](https://mlsanity.com/paper/2209.01688/) (2022)
- [Data Poisoning Attacks to Locally Differentially Private Range Query Protocols](https://mlsanity.com/paper/2503.03454/) (2025)
- [SLDP: Semi-Local Differential Privacy for Density-Adaptive Analytics](https://mlsanity.com/paper/2602.18910/) (2026)
- [DP-SelFT: Differentially Private Selective Fine-Tuning for Large Language Models](https://mlsanity.com/paper/2605.17432/) (2026)

## Abstract (arXiv)

For protecting users' private data, local differential privacy (LDP) has been leveraged to provide the privacy-preserving range query, thus supporting further statistical analysis. However, existing LDP-based range query approaches are limited by their properties, i.e., collecting user data according to a pre-defined structure. These static frameworks would incur excessive noise added to the aggregated data especially in the low privacy budget setting. In this work, we propose an Adaptive Hierarchical Decomposition (AHEAD) protocol, which adaptively and dynamically controls the built tree structure, so that the injected noise is well controlled for maintaining high utility. Furthermore, we derive a guideline for properly choosing parameters for AHEAD so that the overall utility can be consistently competitive while rigorously satisfying LDP. Leveraging multiple real and synthetic datasets, we extensively show the effectiveness of AHEAD in both low and high dimensional range query scenarios, as well as its advantages over the state-of-the-art methods. In addition, we provide a series of useful observations for deploying AHEAD in practice.