  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.
