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.
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.
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