A neural database for differentially private spatial range queries
Authors:
Open Access
- 1 January 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 15 (5) , 1066-1078
Abstract
Mobile apps and location-based services generate large amounts of location data. Location density information from such datasets benefits research on traffic optimization, context-aware notifications and public health (e.g., disease spread). To preserve individual privacy, one must sanitize location data, which is commonly done using differential privacy (DP). Existing methods partition the data domain into bins, add noise to each bin and publish a noisy histogram of the data. However, such simplistic modelling choices fall short of accurately capturing the useful density information in spatial datasets and yield poor accuracy. We propose a machine-learning based approach for answering range count queries on location data with DP guarantees. We focus on countering the sources of error that plague existing approaches (i.e., noise and uniformity error) through learning, and we design a neural database system that models spatial data such that density features are preserved, even when DP-compliant noise is added. We also devise a framework for effective system parameter tuning on top of public data, which helps set important system parameters without expending scarce privacy budget. Extensive experimental results on real datasets with heterogeneous characteristics show that our proposed approach significantly outperforms the state of the art.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- Principled Evaluation of Differentially Private Algorithms using DPBench2016
- PrivTree2016
- A data- and workload-aware algorithm for range queries under differential privacyProceedings of the VLDB Endowment, 2014
- Understanding hierarchical methods for differentially private histogramsProceedings of the VLDB Endowment, 2013
- Differentially private grids for geospatial data2013
- Differentially Private Histogram Publishing through Lossy Compression2012
- Differentially Private Spatial Decompositions2012
- Friendship and mobility2011
- Smooth sensitivity and sampling in private data analysis2007
- STHoles2001