RIPOST: Two-Phase Private Decomposition for Multidimensional Data

• DOI: 10.48550/arxiv.2502.10207
• Publication Date: 2025-02-14
• Authors: Ala Eddine Laouir; Abdessamad Imine
• Keywords: FOS: Computer and information sciences; Computer Science - Databases; H.2.8; Databases (cs.DB)

Differential privacy (DP) is considered as the gold standard for data privacy. While problem of answering simple queries and functions under DP guarantees has been thoroughly addressed in recent years, releasing multidimensional remains challenging. In this paper, we focus on problem, particular how to construct privacy-preserving views using a domain decomposition approach. The main idea recursively split into sub-domains until convergence condition met. resulting are perturbed then published order be used answer arbitrary queries. Existing methods that have face two challenges: (i) efficient budget management over variable undefined depth $h$; (ii) defining an optimal data-dependent splitting strategy minimizes error while ensuring smallest possible decomposition. To address these challenges, present RIPOST, algorithm bypasses constraint predefined $h$ applies data-aware optimize quality results.The core RIPOST two-phase separates non-empty at early stage from empty by exploiting properties datasets, decomposes with minimal inaccuracies mean function. Moreover, introduces distribution allows without requiring prior computation $h$. Through extensive experiments, demonstrated \texttt{RIPOST} outperforms state-of-the-art terms utility accuracy variety datasets test cases