Answering differentially private multi-dimensional queries

Abstract

Providing privacy-preserving answers to multi-dimensional range queries is a critical problem that has attracted significant attention in recent years, given that range queries constitute a fundamental operation in data analysis. However, four principal technical challenges remain: (i) effectively capturing correlations among attributes, (ii) mitigating the curse of dimensionality, (iii) handling large attribute domains, and (iv) accommodating heterogeneous user privacy requirements. Existing methods fail to comprehensively address all these challenges. We build our approach on the idea of using multi-dimensional grids. Specifically, users’ data are mapped onto grid structures, which are then perturbed to ensure privacy before being transmitted to an aggregator. The aggregator utilizes the perturbed grid information to estimate the underlying data distribution and subsequently answer range queries. There exists a trade-off in grid granularity: finer grids amplify noise-induced error, whereas coarser grids introduce bias-induced error. To overcome these limitations, we propose a grid construction optimization that considers multiple factors to enhance accuracy. In addition, we build a correlation model to determine how attributes are correlated, enabling the use of fewer, strategically constructed grids, which improves the signal-to-noise ratio. Also, we incorporate a novel optimization procedure that accounts for workload-specific characteristics. This step finds the user-to-grid assignment that minimizes the total expected error. Finally, we combine different differentially private estimators to improve the accuracy when answering multi-dimensional range queries. We validate our approach through extensive experiments on both real-world and synthetic datasets, demonstrating that our method significantly outperforms existing state-of-the-art techniques.