RIPOST: Two-Phase Private Decomposition for Multidimensional Data
摘要
In this paper, we focus on the problem of publishing multidimensional data under differential privacy (DP), particularly on how to construct privacy-preserving views using a domain decomposition approach. The core idea is to recursively split the domain into sub-domains until convergence, then perturb and publish them. The result is a tree structure that enables efficient indexing and fast approximation processing of queries, while ensuring privacy. Existing decomposition-based methods face two main challenges: (i) efficiently managing the privacy budget over an indefinite decomposition depth h, and (ii) designing a data-dependent splitting strategy that minimizes the error while limiting the subdomain size. We propose RIPOST, a multidimensional decomposition algorithm with bounded and flexible budget allocation that eliminates the need for a predefined depth h and exploits a data-aware splitting strategy with a good trade-off between privacy and utility. RIPOST follows a two-phase process: it first isolates non-empty sub-domains from empty ones, and then refines the decomposition using the mean function to minimize inaccuracies. Through extensive experiments, RIPOST consistently outperforms state-of-the-art methods in terms of data utility and accuracy across various datasets and scenarios.