Answering Range Queries Under Local Differential Privacy

Tejas Kulkarni, Graham Cormode, Divesh Srivastava

Abstract

Counting the fraction of a population having an input within a specified interval, known as a range query, is a fundamental data analysis primitive. While well-studied in trusted aggregator settings, range queries pose significant challenges under Local Differential Privacy (LDP), where users perturb their own data. We introduce and analyze two classes of approaches based on hierarchical histograms and the Haar wavelet transform. We demonstrate that these methods provide strong theoretical accuracy guarantees and significant practical improvements over naive baselines.

1. Introduction

In the Local Differential Privacy (LDP) model, individuals do not trust a central server. Instead, they apply a privacy-preserving mechanism to their data before transmission. While LDP is effective for point queries (e.g., frequency estimation of discrete items), it struggles with range queries—estimating the count of values within a continuous or large discrete interval. A naive approach of summing noisy point estimates leads to variance that grows linearly with the range length, rendering results for large domains unusable.

2. Proposed Methods

2.1 Hierarchical Histograms (HH)

The Hierarchical Histogram approach organizes the data domain into a $B$-ary tree where each node represents a sub-range. To minimize the impact of noise, the authors introduce Level Sampling. Instead of splitting a user's privacy budget $\epsilon$ across all levels of the tree, each user randomly selects exactly one level to report. This ensures that the noise added to each reported node is minimized.

Dyadic decomposition of the domain (top) and the level sampling strategy (bottom) used in Hierarchical Histograms.

Furthermore, a post-processing step using Weighted Least Squares is applied to ensure consistency—where the sum of child node estimates equals the parent's estimate—which significantly reduces overall variance.

2.2 Discrete Haar Transform (DHT)

The second approach utilizes the Discrete Haar Transform to decompose the data signal into averages and differences across various scales.

The Haar wavelet transform matrix used for the DHT approach.

Unlike the HH method, the wavelet coefficients in DHT are independent by construction. This provides "consistency by design," eliminating the need for the complex post-processing required by hierarchical trees while maintaining high accuracy for range estimations.

3. Key Insights and Results

The study reveals several critical findings for LDP range queries:

  • Sampling vs. Splitting: Reporting one level with the full budget $\epsilon$ is mathematically superior to reporting multiple levels with a split budget.
  • Optimal Branching: A branching factor of $B=4$ or $B=8$ is optimal in the LDP setting, contrasting with the $B=16$ typically used in centralized DP.
  • Privacy-Accuracy Trade-off: DHT generally outperforms HH in high-privacy regimes (low $\epsilon$), whereas HH becomes more accurate as the privacy requirement is relaxed (high $\epsilon$).

Experimental results on synthetic Cauchy distributions with up to 67 million users show that these methods reduce error by at least 16x compared to flat baselines for long ranges.

4. Conclusion

By adapting hierarchical and wavelet-based structures to the constraints of local privacy, this work enables accurate range and quantile queries on massive domains. These methods serve as robust primitives for more complex private data analysis tasks, such as building predictive models without compromising individual privacy.

Summary updated

Abstract

Counting the fraction of a population having an input within a specified interval i.e. a \emph{range query}, is a fundamental data analysis primitive. Range queries can also be used to compute other interesting statistics such as \emph{quantiles}, and to build prediction models. However, frequently the data is subject to privacy concerns when it is drawn from individuals, and relates for example to their financial, health, religious or political status. In this paper, we introduce and analyze methods to support range queries under the local variant of differential privacy, an emerging standard for privacy-preserving data analysis. The local model requires that each user releases a noisy view of her private data under a privacy guarantee. While many works address the problem of range queries in the trusted aggregator setting, this problem has not been addressed specifically under untrusted aggregation (local DP) model even though many primitives have been developed recently for estimating a discrete distribution. We describe and analyze two classes of approaches for range queries, based on hierarchical histograms and the Haar wavelet transform. We show that both have strong theoretical accuracy guarantees on variance. In practice, both methods are fast and require minimal computation and communication resources. Our experiments show that the wavelet approach is most accurate in high privacy settings, while the hierarchical approach dominates for weaker privacy requirements.
BibTeX
@article{kulkarni2019answering,
  author = {Tejas Kulkarni and Graham Cormode and Divesh Srivastava},
  title = {{Answering Range Queries Under Local Differential Privacy}},
  journal = {Proc. VLDB Endow.},
  year = {2019},
  url = {https://openreview.net/forum?id=26TqRpmy6m},
}
Figure