Answering multi-dimensional range queries under local differential privacy
Authors:
Open Access
- 1 November 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 14 (3) , 378-390
Abstract
In this paper, we tackle the problem of answering multi-dimensional range queries under local differential privacy. There are three key technical challenges: capturing the correlations among attributes, avoiding the curse of dimensionality, and dealing with the large domains of attributes. None of the existing approaches satisfactorily deals with all three challenges. Overcoming these three challenges, we first propose an approach called Two-Dimensional Grids (TDG). Its main idea is to carefully use binning to partition the two-dimensional (2-D) domains of all attribute pairs into 2-D grids that can answer all 2-D range queries and then estimate the answer of a higher dimensional range query from the answers of the associated 2-D range queries. However, in order to reduce errors due to noises, coarse granularities are needed for each attribute in 2-D grids, losing fine-grained distribution information for individual attributes. To correct this deficiency, we further propose Hybrid-Dimensional Grids (HDG), which also introduces 1-D grids to capture finer-grained information on distribution of each individual attribute and combines information from 1-D and 2-D grids to answer range queries. To make HDG consistently effective, we provide a guideline for properly choosing granularities of grids based on an analysis of how different sources of errors are impacted by these choices. Extensive experiments conducted on real and synthetic datasets show that HDG can give a significant improvement over the existing approaches.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Local, Private, Efficient Protocols for Succinct Histograms2015
- A data- and workload-aware algorithm for range queries under differential privacyProceedings of the VLDB Endowment, 2014
- Local Privacy and Statistical Minimax Rates2013
- Understanding hierarchical methods for differentially private histogramsProceedings of the VLDB Endowment, 2013
- Differentially private grids for geospatial data2013
- Differentially Private Spatial Decompositions2012
- Distributed Private Heavy Hitters2012
- Boosting the accuracy of differentially private histograms through consistencyProceedings of the VLDB Endowment, 2010
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Randomized Response: A Survey Technique for Eliminating Evasive Answer BiasJournal of the American Statistical Association, 1965