Differentially Private Range Queries with Correlated Input Perturbation
This work addresses privacy-preserving data analysis for databases, offering a solution for range queries with improved utility, but it appears incremental as it builds on existing differential privacy methods.
The paper tackles the problem of performing differentially private range queries by introducing a mechanism that uses correlated input perturbation to achieve unbiasedness, consistency, and statistical transparency while meeting accuracy targets. The result is the Cascade Sampling algorithm, which achieves near-optimal utility and competes effectively with other methods.
This work proposes a class of differentially private mechanisms for linear queries, in particular range queries, that leverages correlated input perturbation to simultaneously achieve unbiasedness, consistency, statistical transparency, and control over utility requirements in terms of accuracy targets expressed either in certain query margins or as implied by the hierarchical database structure. The proposed Cascade Sampling algorithm instantiates the mechanism exactly and efficiently. Our theoretical and empirical analysis demonstrates that we achieve near-optimal utility, effectively compete with other methods, and retain all the favorable statistical properties discussed earlier.