PrivMDC: leveraging multi-dimensional correlations to answer differentially private range queries

Abstract

Answering an unbounded number of multi-dimensional range queries while preserving privacy is a significant problem that has been the focus of recent studies since range queries serve as a core component of many data analysis tasks. Existing techniques that use local differential privacy (LDP), which adds noise to users’ data locally, make assumptions that significantly affect utility. In particular, they assume that all attributes in a dataset are correlated and materialize all pair-wise grids/trees. Moreover, they assume that each pair-wise correlation is equally relevant when answering queries. These assumptions result in a low signal/noise ratio, especially for datasets with a large number of attributes. To address the deficiency of existing techniques, we propose a new approach to answer multi-dimensional range queries that leverages multi-dimensional correlations and workload characteristics to selectively choose the data that is collected under the LDP model. Our approach first leverages the availability of a small number of DP users to build a correlation model to determine how attributes are correlated. Then, we use the notion of multi-dimensional grids to capture multi-dimensional correlations. That allows us to materialize fewer grids, boosting the signal/noise ratio. Finally, we propose a new optimization step that makes use of available workload characteristics to identify the user distribution that minimizes the total error when answering multi-dimensional queries among users during the grid assignment process. We conduct extensive experiments on real and synthetic datasets and demonstrate the superiority of our method over existing approaches.