.png){kind=icon}
.png){kind=icon}
Return
RIPOST: Two-Phase Private Decomposition for Multidimensional Data
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-07901-5_14.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Differential Privacy
Hierarchical Decompositions
Journal
C
IF:
0
Papers:
19
Citations:
0