# RIPOST: Two-Phase Private Decomposition for Multidimensional Data

Ala Eddine Laouir, Abdessamad Imine

► To cite this version:

Ala Eddine Laouir, Abdessamad Imine. RIPOST: Two-Phase Private Decomposition for Multidimensional Data. European Symposium on Research in Computer Security, Sep 2025, Toulouse, France. pp.274-293, 10.1007/978-3-032-07901-5_14. hal-05424660

HAL Id: hal-05424660

https://hal.science/hal-05424660v1

Submitted on 18 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# RIPOST: Two-Phase Private Decomposition for Multidimensional Data*

Ala Eddine Laouir

Université de Lorraine, CNRS, Inria, LORIA

F-54000 Nancy, France

ala-eddine.laouir@loria.fr

Abdessamad Imine

Université de Lorraine, CNRS, Inria, LORIA

F-54000 Nancy, France

abdessamad.imine@loria.fr

## ABSTRACT

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

## 1 INTRODUCTION

Releasing a privacy-preserving view of the data, which does not compromise the privacy of individuals whose information is stored in the dataset, has received significant attention from both the

research community and major corporations<fnref n="2" />. The differential privacy model has become the de facto standard for ensuring data privacy [1, 24, 25]. It guarantees that the presence or absence of any particular individual in the dataset does not substantially affect the outcome of the released view. This provides individuals with the plausible deniability needed to deny their inclusion in the data, thus ensuring their privacy. The resulting privacy-preserving view can be used to answer OLAP (Online Analytical Processing) queries, create multi-dimensional histograms, and perform data mining tasks such as clustering [29]. This versatility in the use of the released view has encouraged researchers to further explore this field.

A naive approach [5] would be to add noise to all data points, but this results in a significant loss of data utility. Therefore, more sophisticated mechanisms and techniques have been proposed in the literature. Some use generative models to produce synthetic differentially private data [2, 10, 12, 23, 26, 28, 31], focusing primarily on image data or regular tabular data. Others [17–19] propose workload-dependent algorithms that aim to release answers to a predefined batch of queries rather than the full data view. The generative-based solutions are generally designed as general-purpose algorithms (especially those utilizing deep learning models) without a specific focus on multidimensional data or tensors. On the other hand, workload-dependent approaches are constrained by their reliance on the query workload, which limits their usability. Moreover, these methods often have high computational complexity, making them less scalable for multidimensional data.

In this paper, we focus on decomposition-based algorithms, as they are well-suited for multidimensional data and provide useful views that can be leveraged for a variety of analytical tasks such as OLAP queries. In the literature, several differentially private domain decomposition methods have been proposed to release multidimensional data [3, 13, 15, 21, 29, 30]. These solutions face two main challenges when constructing the view: (i) **The reliance on the decomposition depth *h* to manage the privacy budget.** Several methods [3, 15, 21, 30] estimate *h* before starting the decomposition to limit its value. However, only [13, 29] successfully overcome this limitation either completely or partially. (ii) **The use of data-aware domain splitting strategies** to ensure minimal error in sub-domain approximations while preserving the utility of the generated view. Notably, [29] neglects this issue by applying a data-independent splitting strategy, while [13] applies data-aware splitting only partially, not during the entire decomposition process. All of these domain decomposition methods fail to address both challenges successfully. In comparison with many existing methods, our proposed domain decomposition method, (RIPOST — pRivate

<footnote>*This work is funded by DigiTrust (http://lue.univ-lorraine.fr/fr/article/digitrust/).</footnote>

<footnote n="1">¹https://github.com/AlaEddineLaouir/RIPOST.git</footnote>

<footnote>Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s).

*Conference’17, July 2017, Washington, DC, USA*

© 2025 Copyright held by the owner/author(s).

ACM ISBN 978-3-98318-097-4.</footnote>

<footnote n="2">²https://www.nist.gov/ctl/pscr/open-innovation-prize-challenges/past-prize-challenges/2018-differential-privacy-synthetic</footnote>
<table><caption>Table 1: Comparative results of RIPOST</caption><thead><tr><th>Algo</th><th>RIPOST</th><th>[13]</th><th>[29]</th><th>[23]</th><th>[28]</th></tr></thead><tbody><tr><td>Avg R-RMSE</td><td>1</td><td>x1.47</td><td>x13</td><td>x22</td><td>x62</td></tr></tbody></table>

vIew by two-Phase decompOition for multidimenSional daTa), is able to fully overcome these limitations, producing a high-accuracy view compared to the others.

**Our Contributions.** Our proposed solution RIPOST eliminates the constraint of a predefined depth *h*, allowing for a more refined private decomposition as needed. This flexibility is achieved through a novel privacy budget distribution strategy that relies on a convergent series with a bounded sum as the allocation factor. The tree structure resulting from the decomposition of RIPOST is adapted to speed up query processing. However, the actual evaluation is performed at the leaf nodes, which are the constituents of the published private view RIPOST (similarly to existing works such as [13, 29]).

Regarding the decomposition strategy, RIPOST uses a novel data-aware splitting strategy that takes into account both the data distribution in the domain and the corresponding approximation error. RIPOST is a two-phase decomposition method that separates empty sub-domains from populated sub-domains, thus avoiding unnecessary decompositions and focusing only on highly populated sub-domains with large approximation errors. Those sub-domains are then passed to the second phase of decomposition to further refine them to minimize the error.

Through extensive experiments, we compared our algorithm with various existing methods in the literature, evaluating their performance based on the error (measured as relative root mean squared error, R-RMSE) produced during query evaluation on the published view. Table 1 presents the average Relative-RMSE obtained when comparing RIPOST with [13, 23, 28, 29] using the Fire dataset<fnref n="3" />. Our approach achieved the smallest error on average, outperforming the closest competitor [13] by 47% and showing more than a 10x improvement compared to other methods.

**Roadmap.** The paper is structured as follows: Section 2 reviews related work. Section 3 introduces the key concepts and notation used throughout the paper. Section 4 describes the problem that RIPOST addresses. Section 5 presents the details of the RIPOST method. The extensive evaluation of the method is provided in Section 6. Section 7 discusses potential limitations and extensions, and we conclude in Section 8 by outlining key results and contributions.

## 2 RELATED WORKS

The problem of data publication has become a major research topic in recent years. The naive solution would be to inject noise into each cell of the [4, 5] tensor, but this would cause too much perturbation, making the published data inaccurate. To provide a better alternative, many methods have been developed to publish and query high-dimensional data under DP. We present here the state-of-the-art on this problem.

**Partitioning approaches.** Rather than perturbing data points, [17, 30] proposed algorithms that partition data into bins. In [17], they focused on data partitioning based on minimal aggregation error, and then applied the Laplace mechanism to add noise to the mean value of each bin. Their solution is only effective in low-dimensional/small-domain data, due to the complexity of finding the best partitioning. Other solutions have proposed a recursive domain decomposition algorithm that uses the quadtree strategy to divide the tensor into smaller blocks [22, 29]. Partitioning continues until a convergence condition is satisfied. After convergence, blocks will only keep a representative value of the cells, such as the mean (similar to [17]), and perturb this value to ensure DP. One of the main challenges with partitioning is defining a limit or depth, denoted as *h*, to manage the budget distribution. Some solutions [3, 15, 21] use heuristics to determine an appropriate value for *h*, while [29] bypasses this constraint altogether, as it can hinder performance and introduce inaccuracies. We will address this challenge more in details in Section 4.

HDPView [13] can be considered an improvement over [29]. Instead of using quadtree partitioning, HDPView introduces a data-dependent partitioning strategy, which enhances the quality of the resulting DP view by reducing both the *Aggregation Error (AE)* and DP noise. However, this data-dependent strategy is still constrained by the depth parameter *h* (after which it becomes totally random). While the convergence of [13] is independent of *h*, the partitioning strategy itself is limited by *h*, which reintroduces the issue in part of their solution.

**Workload-based approaches.** Some solutions aim to release only a part of the data delimited by a predefined set of queries, also called *Workload*. In [18], they introduced a matrix mechanism (MM) that creates queries and outputs optimized for a given workload. The work in [19] presents an extension to [18] by adapting and optimizing the matrix mechanism to high-dimensional data (HDMM). In addition, HDMM improves [17], which also falls into this category of solutions. The main issues with these techniques are: (1) workload dependency, and (2) matrix operations can be computationally costly. PrivateSQL [14] provides a framework that calculates the sensitivity of relational data based on its schema and relationships. It then creates a multidimensional view of these data using methods such as [17, 18]. Another solution in this class is [16], which uses random sampling to create a synopsis of the original data and complements it with a dedicated perturbation table to inject noise into each query. This approach is considered a data publishing solution because it perturbs the data upfront, and no further budget is required for individual queries. However, it differs from the previously introduced solutions in that the generated data remains on the server to handle query perturbation, making it a hybrid between data publishing and online query answering. As a result, [16] is relevant to our work but not directly comparable.

**Private generative models.** Another direction of research in this area is the use of generative models to create synthetic, private versions of the data that can then be published. In [28], the authors trained a Bayesian network under DP guarantees, while others [20, 26, 31] used marginal tables to learn the distribution of the original data. Given the impressive performance of deep generative models in many research areas, [2, 9, 10, 12, 23] proposed models

<footnote n="3">³https://data.sfgov.org/Public-Safety/Fire-Department-and-Emergency-Medical-Services-Dis/nuek-vuh3/data</footnote>
that preserve DP while synthesizing data. These models, such as [9] (which uses a Generative Adversarial Network, GAN), outperform [28] only on some classification tasks, but [28] outperforms GAN-based methods on private tabular data. The limitations of these approaches are, in general, as follows: (1) The models are not specifically tailored to tensor data structures and OLAP tasks, which is a major drawback compared to partitioning and workload-dependent approaches, and (2) Generative models are very complex and resource-intensive for large-scale data. In scenarios where data is frequently updated, this computational cost becomes very significant.

In our work, we focus on **workload-independent partitioning-based approaches**. More specifically, we address the limitations and inefficiencies of existing methods such as [3, 13, 29] which we will present in more detail in Section 4. We propose a new partitioning algorithm RIPOST, which creates a better quality view in terms of **accuracy** while ensuring **data privacy and utility**.

## 3 PRELIMINARIES

In this section, we introduce the concepts and notation used throughout the paper.

**Database.** Let $\mathcal{B}$ be a database with a set of tuples defined over $|D|$ dimensions (or attributes) $D = \{d_1, \dots, d_{|D|}\}$, where $|D|$ is called the number of dimensions of $\mathcal{B}$. Each dimension $d \in D$ is associated with a domain (range) $\Omega_d = [d_s, d_e]$, containing $|\Omega_d| = d_e - d_s + 1$ discrete and totally ordered values. The overall domain size of $\mathcal{B}$ is $|\Omega_D| = \prod_{d \in D} |\Omega_d|$. In Figure 1, the database "Fact Table" is shown with $D = \{Age, Service, Patient\}$ and $\Omega_{Service} = [0, 10]$

**Tensor.** A tensor $\mathcal{T}$ is a multidimensional data structure created by aggregating $\mathcal{B}$ based on a subset of $m \le |D|$ dimensions in $D$. Such aggregation is done using a “group-by” query such as:
SELECT $(d_1, \dots, d_m, \text{aggregator}(\cdot))$ AS measure
FROM B GROUP BY $(d_1, \dots, d_m)$.

Here, $d_1, \dots, d_m \in D$ are dimensions and aggregator(·) is an aggregation function such as COUNT, SUM, AVG, etc., which takes an attribute (or dimension) as a parameter. Using COUNT to build a tensor $\mathcal{T}$, the measure attribute contains the number of rows that have the same values (or coordinates) on the dimensions $d_1, \dots, d_m$. In this case, $\mathcal{T}$ is called a count tensor. In this work, we will focus on counting tensors<fnref n="4" />. For simplicity, we will refer to “count tensor” simply as “tensor.”

In Fact Table of Figure 1, the dimensions Patient and Age have been aggregated to create a tensor, which can be represented either as a multidimensional array or as a tabular. The first representation visualizes (and stores) the entire domain (e.g. tensor on $\Omega_{Service}$ in Figure 1), while the second stores only the non-empty($\neq 0$) cells of the domain. Since our goal is to protect the entire data (empty and non-empty cells), we therefore consider the entire domain.

**Count Range Queries.** We consider a special class of queries, namely count range queries. A count range query $Q$ is defined on $k$ dimensions ($k \le |D|$) with subranges $Q = \{\tau_1^Q \subseteq \Omega_{d_1}, \dots, \tau_k^Q \subseteq \Omega_{d_k}\}$, and it computes the sum of the cells within those ranges.

<figure><img src="image_2.png" /><figcaption>Figure 1: Data Model</figcaption></figure>

Given the tensor in Figure 1, a query $Q$ defined by the following range: $Q = \{Service \in [7, 10]\}$ will return: 6.

**Differential Privacy (DP).** Differential Privacy is a privacy model that provides formal guarantees of indistinguishability, ensuring that query results do not reveal significant information about the presence or absence of any particular individual. Consequently, it hides information about which of the neighbouring tensors [6] was used to answer the query.

**DEFINITION 3.1 (NEIGHBOURING TENSORS).** Two tensors $T$ and $T'$ are neighbouring if we can obtain one of them by incrementing the value of a cell in the other by 1. We denote this distance as $Dist(T, T') = 1$.

Let $M$ be a randomized data publishing algorithm. $M$ is differentially private, when it is insensitive to the presence or absence of any individual in $T$.

**DEFINITION 3.2 (ε-DIFFERENTIAL PRIVACY [7]).** An algorithm $M$ satisfies $\epsilon$-differential privacy (or $\epsilon$-DP) if for any neighbouring tensors $T$ and $T'$, and all possible sets of outputs $S$:

$$ \frac{\Pr[M(T) \in S]}{\Pr[M(T') \in S]} \le e^{\epsilon} $$

The parameter $\epsilon$ is called the privacy budget.

It is well known that DP is used to answer specific queries on databases. Let $f$ be a query on a tensor $\mathcal{T}$ whose its answer $f(\mathcal{T})$ returns a number. The sensitivity of $f$ is the amount by which the output of $f$ changes for all neighbouring tensors.

**DEFINITION 3.3 (SENSITIVITY [7]).** The sensitivity of a query $f$ for any two neighboring tensors $\mathcal{T}, \mathcal{T}'$ is:

$$ \Delta_f = \max_{\mathcal{T}, \mathcal{T}'} \|f(\mathcal{T}) - f(\mathcal{T}')\|_1 $$

where $\|\cdot\|_1$ is the $L_1$ norm.

For instance, if $f$ is a count range query then $\Delta_f$ is 1.

To achieve DP for a query $f$, we need to add random noise to its answer $f(\mathcal{T})$. To inject adequate noise, some fundamental mechanisms have been developed for DP. One of them is the Laplace Mechanism.

<footnote n="4">⁴Note that our work can be generalized to any aggregation function</footnote>
**DEFINITION 3.4 (LAPLACE MECHANISM [7]).** The Laplace mechanism adds noise to $f(\mathcal{T})$ as:

$$f(\mathcal{T}) + \text{Lap}\left(\frac{\Delta f}{\epsilon}\right)$$

where $\Delta f$ is the sensitivity of $f$, and Lap($\alpha$) denotes sampling from the Laplace distribution with center 0 and scale $\alpha$.

For instance, if $f$ is a count range query then the noise is sampled from the distribution Lap($1/\epsilon$).

Unlike the Laplace Mechanism (based on noisy numerical answers), the Exponential mechanism allows for selecting the “best” element (according to a scoring function) in a set while preserving DP [7].

**DEFINITION 3.5 (EXPONENTIAL MECHANISM [7]).** Given a set of values $V$ extracted from a tensor $\mathcal{T}$ and a real scoring function $u$ to select values in $V$. The Exponential Mechanism randomly samples $v$ from $V$ with probability proportional to:

$$\exp\left(\frac{\epsilon \times u(\mathcal{T}, v)}{2 \times \Delta_u}\right)$$

where $\Delta_u$ is the sensitivity of $u$.

The Exponential Mechanism satisfies DP by approximately maximizing the score of the value it returns, while sometimes returning a value from the set that does not have the highest score.

Combining several DP mechanisms is possible, and the privacy accounting is managed using the sequential and the parallel composition properties of DP. Let $M_1, ..., M_n$ be mechanisms satisfying $\epsilon_1, ..., \epsilon_n$ -DP.

**THEOREM 3.1 (SEQUENTIAL COMPOSITION [7]).** An algorithm sequentially applying $M_1, ..., M_n$ satisfies $(\sum_{j=1}^n \epsilon_j)$ -DP.

**THEOREM 3.2 (PARALLEL COMPOSITION [7]).** An algorithm applying $M_1, ..., M_n$ to n disjoint datasets in parallel satisfies $(\max_{j=1}^n \epsilon_j)$ -DP.

# 4 PROBLEM STATEMENT

Given a multidimensional tensor $T$, the spatial decomposition problem involves dividing the domain and cells of $T$ into disjoint sub-blocks (sub-domains) such that the cells within each block $b$ can be approximated by their mean $\bar{x}$ with minimal error. This error, referred to as Aggregation Error (AE), measures how much the cells deviate from being perfectly uniform $AE = \sum_{c \in b} |\bar{x} - c|$, where $c$ is a cell in $b$. Range queries are estimated on these sub-blocks based on their intersections with the blocks. Consequently, minimizing AE is essential for maximizing utility.

In order to create such sub-domains (blocks), a decomposition algorithm consists of two main components:

* A convergence condition (CC), which determines whether further partitioning of a domain is necessary.

* A splitting strategy (SS), which defines how a given domain (sub-domain) is divided into smaller sub-domains.

As a result, the decomposition process produces a tree-like structure that serves as an index, enabling faster access to blocks within a given domain.

<figure><img src="image_3.png" /><figcaption>Figure 2: Example of a decomposition Tree</figcaption></figure>

In Figure 2, an example of the tree created by the decomposition algorithm of [13] (without DP) is shown, where:

* CC is defined based on the Aggregation Error of the current sub-domain: $AE \le \theta$, where in this example, $\theta = 10$.

* SS splits a domain into two sub-domains, {left, right}, and chooses the splitting point that minimizes $\{AE(\text{left}) + AE(\text{right})\}$.

The illustrative example in Figure 2, starts with one dimensional tensor with domaine $[0, 10]$. Using SS, the process continue to split the domain and cells until the CC is satisfied. Notice that the mean is added only for the leaf nodes in Figure 2. For approximating queries, only the leaves are considered. For example, for a query $Q = \{\text{Service} \in [7, 10]\}$, we need to compute its intersection with each leaf node $ln$ in the list of tree leaves TL ($ln \in TL$). The approximation is therefor performed as follows:

$$A(Q) = \sum_{ln \in TL} (ln_{\text{dom}} \cap Q_{\text{dom}}) \times ln_{\text{mean}}$$

For this example query, the resulting approximation is $A(Q) = 4.8$.

The problem becomes more complex when the decomposition is made differentially private (DP), as each block must be noised, introducing an additional error termed Perturbation Error (PE). These two errors are inversely related: increasing the number of blocks reduces AE but increases PE, and vice versa. Therefore, an optimal decomposition strikes a balance between AE and PE. The first challenge in creating a DP decomposition algorithm is determining how many times the convergence condition (CC) should be tested. Since CC is data-dependent, each test consumes a portion of the privacy budget. Moreover, because each branch operates on a disjoint portion of the domain, only the maximum depth of the tree must be predefined to limit and appropriately distribute the budget.

Defining this maximum depth $h$ independently of the underlying data [3, 11] can simplify budget management but does not necessarily guarantee an acceptable decomposition with respect to AE and PE. On the other hand, using a heuristic [15, 21] before decomposition to determine an appropriate $h$ based on the data is not practical for two reasons: (1) the result of the heuristic must be DP, as it relies on the data, and (2) the computational complexity of finding optimal $h$ may be comparable to performing the actual decomposition itself, thus they usually approximate $h$ vaguely.
The first approach to bypass the dependency on $h$ is PrivTree [29], which proposed a *Biased Convergence Condition (BCC)*. This condition allows repeated testing while ensuring that the total privacy budget consumption remains fixed and independent of $h$. To better clarify the *BCC*, consider a *CC* defined as $M(t) \le \theta$, where *M* is any arbitrary metric, *t* is a sub-block, and $\theta$ is a threshold. To ensure a DP-safe *CC*, *Laplace* noise with a budget $\epsilon$ is added to $M(t)$, resulting in $M'(t)$, which is used for testing. Their contribution relies on a key observation regarding budget consumption, particularly when:

* $M(t) \gg \theta$ for all intermediate nodes in a path except the leaf, and

* For any parent/child pair $t_p$ and $t_c$ in a path, $M(t_p) - M(t_c) \ge c$.

Under these conditions, the actual budget consumption along the path is less than $h/\epsilon$ (without releasing the actual value of $M'(t)$). They proved that if these two conditions are met, the total budget is constant and equal to $\epsilon$.

On real datasets, the issue arises with the second condition, as it cannot be guaranteed for all possible datasets. To address this, they introduced the *BCC*, defined as follows:

* $\hat{M}(t) = \max\{\theta - \delta, M(t) - \text{depth}(t) \times \delta\}$, where $\delta$ is the *bias* term, defined independently of the data. This guarantees that the second condition always holds: $M(\hat{t}_p) - M(\hat{t}_c) \ge \delta$. Alternatively, $\hat{M}(t) = \theta - \delta$, which is data-independent and does not require privacy budget.

* $M'(t) = \hat{M}(t) + \text{Lap}(\lambda)$, where $\lambda \ge \Phi \cdot \frac{1}{\epsilon}$, where of $\Phi$ is based on some parameters (see [29] for more details). This ensures that the total budget of *CC* is $\epsilon$, regardless of how many times it is repeated.

This proposition indeed eliminates the need to specify a fixed depth at the beginning, but it has a significant disadvantage. The *BCC* incorporates a deterministic, incrementing perturbation ($-\text{depth}(t) \times \delta$) to the metric *M* used in *CC*, in addition to the standard *Laplace noise*. This deterministic perturbation, referred to as the *bias term* in [29], is defined independently of the data. Consequently, it may lead to what we call *Early Convergence*, where the decomposition halts before achieving an acceptable balance between *AE* and *PE*.

To assert such a claim, we conducted an experiment where we passed a 2D-tensor created using the dataset Adult<fnref n="5" /> to both PrivTree [29] and HDPView [13], since they both implement the *BCC*. We set the total budget to $\epsilon = 0.1$. The results are shown in Figure 3, where plots 1 and 2 correspond to PrivTree and HDPView, respectively. The plots show how many sub-domains converged at each depth. Additionally, the red portion indicates the number of sub-domains with $AE > 0$, while the blue portion represents those with $AE = 0$.

We notice from the results that HDPView generated more blocks, resulting in more blocks with $AE = 0$. This highlights another issue with the *BCC*: the choice of the metric *M* is very important. Even though PrivTree uses the count as a metric, which has a *sensitivity* lower than that of *AE* (see Section 5.3.3), the deterministic and incrementing perturbation of the *BCC* affected it greatly.

<figure><img src="image_4.png" /><figcaption>Figure 3: Convergence Analysis</figcaption></figure>

To summarize the results in terms of *Early Convergence*, PrivTree has 92% of the sub-domains with $AE > 0$, while HDPView has 63%. In both cases, these proportions are very significant, indicating the limitations of the *BCC*.

The second challenge lies in the quality of the splitting strategy (**SS**) used in the decomposition algorithm. The **SS** can be defined as a data independent process; for example, splitting the domain into $2^{|D|}$ blocks at each level, as proposed in [29]. However, such a strategy often creates an excessive number of unnecessary blocks, significantly increasing the **PE** without meaningfully reducing the **AE**. Conversely, employing a data-dependent **SS** requires a DP mechanism, which consumes privacy budget at each level. This reintroduces the dependency on $h$ within the **SS**, like in [13]. Furthermore, an intuitive solution, such as designing an **SS** that uses **AE** as the primary metric for splitting, does not necessarily yield the best results. This approach neglects other important characteristics of tensors, such as sparsity, which could be leveraged to improve the quality of the splitting strategy.

With our proposed solution RIPOST, we aim to address both challenges while overcoming the limitations of previous approaches. Leveraging the fact that multidimensional tensors are typically sparse, RIPOST operates in two phases. In the first phase, it separates the empty regions from the nonempty regions of the tensor. In the second phase, the nonempty regions are further decomposed based on **AE**. Since **AE** cannot be null as long as there is a mixture of cells, this two-phase **SS** allows us to minimize the **AE** in significantly fewer steps. The tree example shown in Figure 2 reinforces this logic. As seen in the results in Figure 2, even though the **SS** is based on **AE**, it ends up separating the empty and non-empty cells.

Furthermore, RIPOST ensures that both **CC** and **SS** in each phase are independent of the depth $h$ and do not require a predefined or maximum $h$ as input. In Figure 3 plot 3, we see the performances of RIPOST compared to the others. It is able to reduce the *Early Convergence* by a big margin to only 29% while generating more refined blocks.

# 5 PROPOSED ALGORITHM

In this section, we present our method RIPOST, which constructs a DP view by privately decomposing a tensor into a set of blocks, and the user can query this view without any privacy risk while ensuring the utility of the query results.

## 5.1 Overview of RIPOST

Our proposed solution addresses all the key challenges and problems highlighted in Section 4. Thus, RIPOST iteratively splits the original tensor into two sub-blocks and stops when the cells in

<footnote n="5">⁵https://archive.ics.uci.edu/dataset/2/adult</footnote>
a block have minimal AE. To achieve such a decomposition, our algorithm operates in two phases: first, it tries to separate the empty cells from nonempty cells; then, it minimizes the AE in each block.

During the first phase, the algorithm uses the Sum of cells to determine whether it has successfully separated the empty cells (Sum ≤ 0). This condition will be satisfied for blocks with nonempty cells due to perturbation. In the second phase, all blocks that converged based on the first condition are tested again and split to minimize the AE. The overall algorithm of RIPOST is described in Algorithm 1. RIPOST works as follows:

* As input, it takes a tensor T, a total budget ϵ and hyperparameters α, γ, β which are used to divide the budget over the first and second phases (Lines 1-4).

* The first phase checks sum ≤ θ₁ in the current block (Line 9). In case Secure_cc is False, the current block is still in the first phase. Then, it is divided into two sub-blocks by choosing the optimal cutting point that separates the cells and creates sub-blocks with a minimal mix of non-empty and empty cells (Line 12).

* In case Secure_cc is True, the current block is added to the list of converged_blocks (Line 10).

* This process is repeated until there are no more non_converged_blocks (Line 7).

* In the second phase, all the converged blocks from the previous phase are now considered as non-converged (Lines 17-18).

* Each block with a minimal AE is added to the list of converged_blocks (Line 22). Otherwise, it is divided into two sub-blocks by choosing the optimal cutting point that minimizes AE in both sub-blocks (Line 24).

* This process is repeated as long as non_converged_blocks (Algorithm 1 Line 19) is not empty.

* At the end, the average (representative value) of the converged_blocks is perturbed and the secure_view is thus returned (Line 29).

Regarding the budget distribution (Lines 1-4): α splits the total privacy budget ϵ between the decomposition budget ϵ_d and the perturbation budget ϵ_p. The parameter γ then splits ϵ_d over both phases of RIPOST, namely ϵ_1 and ϵ_2. Lastly, β divides ϵ_1 and ϵ_2 between the convergence and splitting components.

Note that we pass as parameter the entire budget allocated to the Secure_cc (resp. Secure_ss) function in the current phase (Lines 9, 12, 21, 24). Since these operations are repeated many times, each iteration should only consume a part of the budget. In Section 5.2, we will explain how to distribute the privacy budget over an unlimited number of iterations without exceeding the allocation. Then, in Section 5.3, we will provide a detailed implementation of the Secure_cc and Secure_ss functions.

## 5.2 Privacy Budget Distribution

In order to ensure that our algorithm RIPOST satisfies ϵ-DP, we need to ensure not only that randomness is introduced, but also that the total budget remains below ϵ as required. As mentioned in Section 4, controlling the budget in a decomposition often results in a limitation on depth, which introduces significant challenges and tradeoffs. To avoid such a constraint, we need to define a function

**Algorithm 1 Our Partitioning algorithm RIPOST**

Require: T: Tensor; ϵ: budget; α, γ, β: hyperparameters

1: $\epsilon_p, \epsilon_d \leftarrow \epsilon \times (1 - \alpha), \epsilon \times \alpha$

2: $\epsilon_1, \epsilon_2 \leftarrow \epsilon_d \times \gamma, \epsilon_d \times (1 - \gamma)$

3: $\epsilon_{cc}^1, \epsilon_{ss}^1 \leftarrow \epsilon_1 \times \beta, \epsilon_1 \times (1 - \beta)$

4: $\epsilon_{cc}^2, \epsilon_{ss}^2 \leftarrow \epsilon_2 \times \beta, \epsilon_2 \times (1 - \beta)$

5: converged_blocks $\leftarrow$ []

6: non_converged_blocks $\leftarrow$ [T]

7: **while** non_converged_blocks $\neq \emptyset$ **do** ▸ First phase

8: &nbsp;&nbsp;&nbsp;&nbsp;block $\leftarrow$ non_converged_blocks.pop()

9: &nbsp;&nbsp;&nbsp;&nbsp;**if** Secure_cc(block, Sum, $\leq \theta_1, \epsilon_{cc}^2$) **then**

10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;converged_blocks.add(block)

11: &nbsp;&nbsp;&nbsp;&nbsp;**else**

12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;left_block, right_block $\leftarrow$ Secure_ss(Sum, block, $\epsilon_{ss}^1$)

13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;non_converged_blocks.push(left_block)

14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;non_converged_blocks.push(right_block)

15: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

16: &nbsp;&nbsp;&nbsp;&nbsp;**end while**

17: non_converged_blocks $\leftarrow$ converged_blocks

18: converged_blocks $\leftarrow$ []

19: **while** non_converged_blocks $\neq \emptyset$ **do** ▸ second phase

20: &nbsp;&nbsp;&nbsp;&nbsp;block $\leftarrow$ non_converged_blocks.pop()

21: &nbsp;&nbsp;&nbsp;&nbsp;**if** Secure_cc(block, AE, $\leq \theta_2, \epsilon_{cc}^2$) **then**

22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;converged_blocks.push(block)

23: &nbsp;&nbsp;&nbsp;&nbsp;**else**

24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;left_block, right_block $\leftarrow$ Secure_ss(AE, block, $\epsilon_{ss}^2$)

25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;non_converged_blocks.push(left_block)

26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;non_converged_blocks.push(right_block)

27: &nbsp;&nbsp;&nbsp;&nbsp;**end if**

28: &nbsp;&nbsp;&nbsp;&nbsp;**end while**

29: secure_view $\leftarrow$ perturb(converged_blocks)

30: **return** secure_view

that distributes a given budget ϵ for any arbitrary depth h, such that:

$$ \epsilon \geq \sum_{i=1}^{h} \epsilon_i, \text{ where } \epsilon_i > 0 \quad (1) $$

Since each $\epsilon_i < \epsilon$, we can define $\epsilon_i$ as: $\epsilon_i = \epsilon \times \omega_i$, where $\omega_i \in ]0, 1[$. Thus, we can redefine the constraint in Equation 1 as:

$$ \epsilon \geq \sum_{i=1}^{h} \epsilon \times \omega_i, \text{ where } \epsilon_i = \epsilon \times \omega_i \quad (2) $$

$$ 1 \geq \sum_{i=1}^{h} \omega_i $$

According to Equation 2, we need to define a weight for each level and ensure that the sum of weights does not exceed 1. To define such a distribution, we can opt for the following convergent series [27]:

$$ \omega_i = \frac{1}{i(i+1)} \text{ with positive integers } i \quad (3) $$

$$ \sum_{i=1}^{\infty} \omega_i = 1 $$

The issue in this case is that most of the allocation will be given to the very first few levels of the decomposition (i.e. bigger weights at the start) because such series decays quickly. Thus, it may lead to injecting too much noise early in the decomposition and cause
the Early Convergence discussed in Section 4 due to the budget being consumed quickly (big $\omega_i$ early on).

Simply considering a slower series may not be sufficient. So to slow down the weights distribution, we considered the sum of multiple instances of the series term by term. For instance, given $S = 1/i(i+1)$, then we define $S^2 = 1/i(i+1) + 1/i(i+1) = 2/i(i+1)$. Here, $S^2$ decays slower than $S$, but it no longer satisfies the condition in Equation 2 and the sum of weights is no longer equal to 1. However, we notice that the first term of $S^2$ is $S_1^2 = 2/(1+1) = 1$, so the remaining terms have the sum equal to 1: $\sum_{i=2}^n 2/i(i+1) = 1$. Therefore, we can offset the start of the series (in the case of $S^2$ the offset is 1, we refer to it as os) to obtain a new series that: (1) decays slower and (2) satisfies Equation 2.

So in the case of $S = 1/i(i+1)$, we can use a series $S^k = k/i(i+1)$ with a given offset os to define the weight $\omega_i$ as:

$$ \omega_i = S_{(i+os)}^k \quad (4) $$

Thus, we define a function get_weight(.) that will be used by Secure_cc and Secure_ss functions (used in Algorithm 1) to obtain the proper budget for an operation based on the block's depth at each phase of Algorithm 1.

Setting the appropriate offset os depends on the choice of S. In this work, we consider $S = \frac{1}{i(i+1)}$, though other series can also be used. To determine os for this definition of S, we need to ensure that the following condition holds:

Given S, we know that:

$$ \sum_{i=1}^{n} \frac{1}{i(i+1)} \le 1 - \frac{1}{n+1}, $$

which implies:

$$ \sum_{i=1}^{n} \frac{k}{i(i+1)} \le k \left( 1 - \frac{1}{n+1} \right) \le k $$

Thus, we define os such as:

$$ \sum_{i=1}^{os-1} \frac{k}{i(i+1)} + \sum_{i=0s}^{n} \frac{k}{i(i+1)} \le k $$

And in such a way:

$$ \sum_{i=1}^{os-1} \frac{k}{i(i+1)} \ge k-1 \text{ and } \sum_{i=0s}^{n} \frac{k}{i(i+1)} \le 1 $$

The first sum $\sum_{i=1}^{os-1} \frac{k}{i(i+1)}$ represents the sum of terms that we will ignore, and the second sum $\sum_{i=0s}^{n} \frac{k}{i(i+1)}$ represents the sum of terms that we want to use in Equation 4. Based on this, we get:

$$ \sum_{i=1}^{os-1} \frac{k}{i(i+1)} \ge k-1 \Rightarrow k \left( 1 - \frac{1}{(os-1)+1} \right) \ge k-1 $$

which leads to the condition, for any given $S^k$, the offset os must satisfy:

$$ os \ge k $$

to ensure that the sum of the weights remains within the bound $\le 1$.

To show the difference in decay between S and its variants $S^k$, Figure 4 illustrates the $\omega_i$ values obtained at each depth using different series.

<figure><img src="image_5.png" /><figcaption>Figure 4: $\omega_i$ for each level of depth h using $S^k$</figcaption></figure>

Other alternatives, such as uniform budget distribution, are not possible since h is not known in advance. Additionally, the use of a growing series might be more interesting than a decaying series [3] in some cases, but it also requires a predefined depth h. Without a predefined h, it would be very difficult to create such a series while ensuring that the constraint in Equation 2 holds.

## 5.3 Secure Convergence and Partitioning

In Algorithm 1, we showed that both phases use the same functions for convergence and splitting, differing only in the set of parameters, which hints that they follow the same logic.

### 5.3.1 Secure convergence condition Secure_cc: Algorithm 2 describes the function Secure_cc, which takes as input a block B, a metric based on which to determine convergence, a threshold $\theta$, and $\epsilon$, the privacy budget allocated to the convergence in the current phase ($\epsilon_{cc}^1$ or $\epsilon_{cc}^2$ in Algorithm 1).

Algorithm 2 starts with computing the budget $\epsilon_i$ corresponding to the current iteration based on Equations 2 and 4 and the depth of the block (Algorithm 2 Lines 1-2). The function depth(.) returns the depth of the block in parameter based on the current decomposition phase. When a block B moves from phase 1 to phase 2 of Algorithm 1, this function resets the depth of B to 1.

Then, Secure_cc computes and perturbs the desired metric (Algorithm 2 Line 3). Finally, it returns True or False on whether the perturbed metric is less than or equal to $\theta$. For this function the choice of $\theta$ does not have much affect on the output of the algorithm (as long as $\theta$ is small) as mentioned by [29], so in our algorithm this parameter is set to 0 by default.

### Algorithm 2 Secure_cc

Require: B: block, metric, $\epsilon$, $\theta$

1. $\omega_i \leftarrow get_weight(\text{depth}(B))$

2. $\epsilon_i \leftarrow \omega_i \times \epsilon$

3. value $\leftarrow$ metric(B) + Lap($\Delta_{\text{metric}}/\epsilon_i$)

4. return value $\le \theta$
The Secure\_cc uses the Laplace mechanism (Algorithm 2 Line 3) to ensure DP, and the scale of the noise depends on $\Delta_{metric}$, the sensitivity of the metric. The sensitivity of the metric will be discussed in details in Section 5.3.3.

### 5.3.2 Secure splitting strategy Secure\_ss
The Algorithm 3 illustrates all the steps of the function Secure\_ss. This function takes as parameters a block, metric, and the budget $\epsilon$ ($\epsilon_{ss}^1$ or $\epsilon_{ss}^2$) allocated for SS in the current phase of Algorithm 1. Secure\_ss starts by computing the budget for the current iteration (Algorithm 3 Lines 1-2), in a similar manner as the Secure\_cc. Then, it loops over all the possible cutting points of the block and calculates a sampling probability (Algorithm 3 Lines 3-5) based on the Definition 3.5 of the Exponential mechanism.

The function score takes as a parameter B, metric, and a cutting point i. The function score will treat B as if it were split at point i into two halves, $B_L$ and $B_R$. According to the metric (in other words, according to the phase of Algorithm 1), it will give the following score to the point i:

* Case metric is 'Min': $Score_i = -\min\{min_{B_L}, min_{B_R}\}$. Where $min_{B_L}$ (or $min_{B_R}$) is the minimum between the number (count) of empty and nonempty cells in the left block (respectively in the right block). Thus, the cutting point with $min \approx 0$ will get the highest score as it leads to a perfect split of cells.

* Case metric is 'AE': $score_i = -(AE_{B_L} + AE_{B_R})$. Thus, giving the highest score to the cutting point that provides a split with minimal AE.

**Algorithm 3 Secure\_ss**

**Require:** B: block, metric, $\epsilon$

1: $\omega_i \leftarrow get\_wiegth(\text{depth}(B))$

2: $\epsilon_i \leftarrow \omega_i \times \epsilon$

3: **for** i $\in \Omega_B$ **do**

4: &nbsp;&nbsp;&nbsp;&nbsp;prob[i] $\leftarrow \exp\left(\frac{\epsilon_i \times score(B,metric,i)}{4 \times \Delta_{metric}}\right)$

5: **end for**

6: point $\leftarrow$ random\_choice($\Omega_B$, prob)

7: $B_L, B_R \leftarrow split(B, point)$

8: **return** $B_L, B_R$

Since we are computing the measure twice (on $B_L$ and $B_R$), notice that we set the sensitivity of the score as $\Delta_{score} = 2 \times \Delta_{metric}$ (The sensitivity of the metric will be discussed in details in Section 5.3.3).

Afterwards, it applies **unequal probability sampling** (line 6) to select a random cutting point and splits B into $B_L$ and $B_R$, which are returned as results.

### 5.3.3 Sensitivity Min, Sum and AE
In order to apply the Laplace mechanism and Exponential mechanism used in Secure\_cc and Secure\_ss respectively, we need to compute the sensitivity of each metric used.

**THEOREM 5.1 (SENSITIVITY OF THE MIN, SUM AND AE.** For any neighbouring tensors T and T': $\Delta_{Min} = 1$, $\Delta_{Sum} = 1$ and $\Delta_{AE} = 2$.

**Proof:**

**In the case of the Sum (and the Min):** It is straightforward, $\Delta_{Sum} = 1$ ($\Delta_{Min} = 1$), since given two neighboring tensors T and T', the Sum (count of empty or nonempty cells) will change by 1 because of a cell having +1 or -1.

**In the case of AE:** Consider T and T'. In T', suppose the cell $c_l$ got +1, we compute the AE as follows:

$$AE(T) = \sum_{c \in \Omega_D} |\bar{x} - c| \text{ and,} \\ AE(T') = \sum_{c \in \Omega_D, c \neq c_l} |\bar{x}' - c| + |\bar{x}' - c_l| \text{ and,} \\ \bar{x} = \frac{\text{Sum}(T)}{|\Omega_D|} \\ \bar{x}' = \frac{\text{Sum}(T)+1}{|\Omega_D|} \quad (5)$$

Based on Equation 5, $AE(T') \le \sum_{c \in \Omega_D} |\bar{x} - c| + 2 \times \frac{n-1}{n}$ which implies that $\Delta_{AE} = |AE(T) - AE(T')| \le 2 \times \frac{n-1}{n} \le 2$.

## 5.4 Privacy budget

To compute the privacy budget consumption of our decomposition algorithm, and since each branch manipulates a distinct portion of tensor T (as mention in Section 4), we need only to track the consumption of only one path from the root T to a leaf node. Then based on the parallel composition, we can deduce the total consumption.

Each leaf node published by our algorithm must be produced by a branch that extends from the root and goes through two phases of decompositions as described in Algorithm 1. Based on this, let's assume that a branch went k iterations in our first decomposition phase and p iterations in the second phase. In the last step, the algorithm perturbs the leaves before publishing them. Given that all these iterations are applied consecutively to the same portion of the tensor, the total privacy budget is computed using the sequential composition property of DP, accumulating the budget consumed in each iteration.

So, to ensure that the budget consumption by the algorithm is in bound of the total budget $\epsilon$ given as input to Algorithm 1, means proving that for any given leaf block $B_l$ this equation holds:

$$\frac{\text{Pr}[B_l|T]}{\text{Pr}[B_l|T']} \le e^{\epsilon} \quad (6)$$

We note $B_l^i$ the i'th predecessor of $B_l$ starting from the root and belonging to the path from root to $B_l$. According to our Algorithm 1, for the Secure\_cc during the first phase we have the following budget consumption:

$$\left| \prod_{i=1}^{k-1} \frac{\text{Pr}[\text{Sum}(B_l^i) + \text{Lap}(\lambda_i) > \theta_1]}{\text{Pr}[\text{Sum}(B_l^{i'}) + \text{Lap}(\lambda_i) > \theta_1]} \right| \times \frac{\text{Pr}[\text{Sum}(B_l^k) + \text{Lap}(\lambda_i) \le \theta_1]}{\text{Pr}[\text{Sum}(B_l^{k'}) + \text{Lap}(\lambda_i) \le \theta_1]}$$

And for the Secure\_ss during the first phase:

$$\prod_{i=1}^{k} \frac{\text{Pr}[\text{point}_j | B_l^i, \text{Min}]}{\text{Pr}[\text{point}_j | B_l^{i'}, \text{Min}]}$$

Where $\text{Pr}[\text{point}_j | B_l^i, \text{metric}]$ is the probability point_j being selected as a cutting point given a block $B_l^i$ and a scoring function using metric. For the second phase we have a similar budget consumption. For the Secure\_cc in the second phase:

$$\left| \prod_{i=k}^{p-1} \frac{\text{Pr}[AE(B_l^i) + \text{Lap}(\lambda_i) > \theta_2]}{\text{Pr}[AE(B_l^{i'}) + \text{Lap}(\lambda_i) > \theta_2]} \right| \times \frac{\text{Pr}[AE(B_l^p) + \text{Lap}(\lambda_i) \le \theta_2]}{\text{Pr}[AE(B_l^{p'}) + \text{Lap}(\lambda_i) \le \theta_2]}$$
And for the Secure_ss:

$$ \prod_{i=k}^{p} \frac{\mathrm{Pr}[\mathrm{point}_i | B_l^i, \mathrm{AE}]}{\mathrm{Pr}[\mathrm{point}_i | B_l^i, \mathrm{AE}]} $$

Finally, Algorithm 1 perturbs the mean of the leaf:

$$ \frac{\mathrm{Pr}[\mathrm{mean}(B_l) + \mathrm{Lap}(\lambda) = S]}{\mathrm{Pr}[\mathrm{mean}(B'_l) + \mathrm{Lap}(\lambda) = S]} $$

Since each operation (Secure_cc and Secure_ss) is allocated a dedicated budget for each phase of Algorithm 1 lines 1-4, and according to the budget distribution we proposed in Section 5.2 and the definitions in 3.4.3.5: Secure_cc will not exceed $\epsilon_{cc}^1$ and $\epsilon_{cc}^2$ in both phases. Similarly, Secure_ss will not exceed $\epsilon_{ss}^1$ and $\epsilon_{ss}^2$ in both phases. So based on the sequential composition, we have:

$$ \frac{\mathrm{Pr}[B_l|T]}{\mathrm{Pr}[B_l|T']} \le \epsilon_{cc}^1 \times \epsilon_{ss}^1 \times \epsilon_{cc}^2 \times \epsilon_{ss}^2 \times \epsilon_{\rho} \le \epsilon^\epsilon $$

This result shows that our algorithm doesn't exceed the privacy budget given as an input, independently of the depth h of any branch during the decomposition. Based on the *Parallel Composition* property of DP, this conclusion can be generalized to all paths of the decomposition.

# 6 EXPERIMENTS

In order to assess the performance of our proposed algorithm RIPOST, we conducted an extensive comparative experiment with existing algorithms on several different datasets. In this section, we discuss the main results and observations we obtained.

## 6.1 Experiments Setup

**Datasets.** In our experiments, we used the following well-known datasets:

(i) **Census Adult**<fnref n="6" /> is a benchmark dataset containing demographic information about individuals and their income.

(ii) **Fire Department and Emergency Medical Services Dispatched Calls for Service (Fire)**<fnref n="7" /> contains records of emergency calls made to the fire department in San Francisco.

(iii) **Gowalla-2D**<fnref n="8" /> is a geo-location check-in dataset.

(iv) **Jm1**<fnref n="9" /> is a dataset containing static source code analysis data for defect detection.

For each dataset we generated several tensors and thousands of queries, the Table 2 shows the different stats on each dataset. In the remainder of this section, we will emphasize how we used each dataset/workload. **Evaluation metrics.** In our evaluation,

<table><caption>Table 2: Dataset and workload statistics</caption><thead><tr><th>Datasets</th><th>#Dimensions</th><th>#Workloads</th><th>#Queries</th><th>Domain</th></tr></thead><tbody><tr><td>Adult</td><td>15</td><td>119 + 8</td><td>(5 + 8) × 3000</td><td>8.9 × 10<sup>18</sup></td></tr><tr><td>Fire</td><td>35</td><td>119 + 8</td><td>(5 + 8) × 3000</td><td>2.291 × 10<sup>57</sup></td></tr><tr><td>Gowalla</td><td>2</td><td>1</td><td>3000</td><td>10<sup>6</sup></td></tr><tr><td>Jm1</td><td>21</td><td>456</td><td>5 × 3000</td><td>2 × 10<sup>21</sup></td></tr></tbody></table>

<table><caption>Table 3: Number of Tensors/Workloads per Number of Dimensions</caption><tr><td># Dimensions</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td></tr><tr><td># Tensors/Workloads</td><td>21</td><td>35</td><td>35</td><td>21</td><td>7</td></tr></table>

we used the RMSE (Root-Mean-Square Error) to measure the error between the query answer from the original dataset and those from the perturbed view. The RMSE is defined as: $RMSE = \sqrt{\frac{1}{n} \sum_{Q \in W} (Q(T) - Q(T'))^2}$

where W is the workload, and T, T' are the original and private views of the tensor, respectively (regardless of the method used to create T'). To compare the results across different algorithms, we calculated the relative RMSE, denoted as **R-RMSE**, by dividing the RMSE obtained by each approach on a workload W by the RMSE obtained using our approach on the same dataset.

Thus, if R-RMSE > 1, it means our approach outperformed the other, and **R-RMSE** indicates the magnitude of the difference. Conversely, if R-RMSE < 1, it means our approach underperformed compared to the other, and **R-RMSE** indicates the fraction that the RMSE of the other approach represents relative to ours.

**Competitors.** We compared RIPOST with several recent solutions (in addition to the naive solution Identity[5]) from the literature (see Section 2), namely: (i) HDPView [13] and PrivTree [29] for partitioning approaches; (ii) HDMM [19] and DAWA [17] for workload-dependent approaches; (iii) PrivBayes [28] and P3GM [23] for generative models creating DP datasets.

**Hyperparameters.** In all experiments, we set the total privacy budget to $\epsilon = 0.1$. For RIPOST, we set $\alpha = 0.3$, $\gamma = 0.9$, and $\beta = 0.4$. A complete analysis of the effect of each of these hyperparameters on the performance of RIPOST is provided in Section 6.3. For the other solutions, we used the same hyperparameter values as those reported in their original experiments. A disclaimer: The model presented in [23] computes the privacy budget based on both the data size and the training sample. As a result, it was quite complicated to tune the $\epsilon$ of this model for all the tensors generated in our tests, with minimal change on setup of the original paper. So to ensure fairness to all competitors, [23] was allocated a larger budget within the range of [0.1, 1], depending on the tensor.

**Source Code:** The code for all the experiments conducted in this paper is available on GitHub<fnref n="10" />. In addition to the experiments presented here, additional experiments can be found in the GitHub repository (due to space limitations).

## 6.2 RIPOST performances analysis

### Partitioning and generative approaches

In this first part of the experiments, we compared the performance of RIPOST with HDPView, PrivTree, PrivBayes, and P3GM. For these tests, we used the Adult and Fire datasets, and for each, we created a set of 2, 3, ..., 6-dimensional tensors, each with its own workload. Table 3 shows the number of distinct tensors/workloads generated and used for each number of dimensions.

<footnote n="10">¹⁰https://github.com/AlaEddineLaouir/RIPOST.git</footnote>

<footnote n="6">⁶http://archive.ics.uci.edu/ml/datasets/Adult</footnote>

<footnote n="7">⁷https://data.sfgov.org/Public-Safety/Fire-Department-and-Emergency-Medical-Services-Dis/nuek-vuh3/data</footnote>

<footnote n="8">⁸http://snap.stanford.edu/data/loc-Gowalla.html</footnote>

<footnote n="9">⁹https://www.openml.org/search?type=data&sort=runs&id=1053&status=active</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 5: R-RMSE results based on Adult dataset</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 6: R-RMSE results based on Fire dataset</figcaption></figure>

These different tensors/workloads are used to ensure a thorough and robust evaluation. In Figures 5 and 6, we show the average R-RMSE obtained by each approach on both the Adult and Fire datasets, respectively. First, we notice that our approach is able to maintain better performance than all the others in the different tests. In Figure 5, we see that our closest competitor is HDPView, but its performance pales as the number of dimensions grows. This is due to the large number of blocks generated at high-level tensors, but HDPView fails to calibrate the PE and AE compared to RIPOST. Also, in both Figures 5 and 6, we notice that PrivTree has worse performance than RIPOST and HDPView due to its limitations, as mentioned in Section 4, such as data-independent SS.

Regarding the generative approaches, PrivBayes and P3GM, we notice that their performance improves with higher dimensions due to the increase in training data. However, this does not make them outperform the partitioning approaches at any point in our tests, and this is due to the fact that they are not optimized for tensors and OLAP range queries as tasks. In particular, these models does not take into account the *measure* attribute created due to the aggregation (as explained in Section 3).

To further test the performance of these approaches, we scaled the tests to higher dimensions. We used the Adult dataset to create tensors with dimensions ranging from 7 to 14, each with a workload of 3000 queries to test the quality of the generated views.

Based on the results shown in Figure 7, we observe that our approach remains consistent and scales better than the other approaches. Also, HDPView remains a close competitor, but it is important to note that the generative approaches are also improving their results. Particularly, P3GM had two main advantages: (i) In the

<figure><img src="image_8.png" /><figcaption>Figure 7: R-RMSE on higher dimension tensors based on the Adult dataset.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 8: Gowalla</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 10: HDPView</figcaption></figure>

<caption>Figure 11: PrivTree</caption>

<caption>Figure 12: Gowalla-2D Partitioning</caption>

case of the *Adult* dataset, creating a tensor with 14 dimensions (out of the 15 available) does not introduce much aggregation, resulting in most values in the *measure* attribute being 1. This significantly reduces the effect of P3GM neglecting this attribute. (ii) The difficulty encountered when tuning its budget led to P3GM consuming more budget than the other methods in these tests, which consequently introduced less noise.

## Spatial Data

Another important use case is the publishing of spatial data, where partitioning algorithms are the most commonly used for this type of data. To highlight the performance of RIPOST, we compared its performance on the Gowalla dataset with HDPView and PrivTree. For this test, we generated 3000 queries to assess the quality of the view created. Figure 12 shows the spatial partitioning of the Gowalla
<figure><img src="image_11.png" /><figcaption>Figure 13: R-RMSE results based on small-adult dataset</figcaption></figure>

dataset by RIPOST, HDPView, and PrivTree, respectively. We can
easily notice that PrivTree generated the fewest blocks (converging
early), further supporting the observations and critiques made in
Section 4. As a result, it gave an RMSE ×25 larger than ours.

Comparing RIPOST to HDPView, from Figure 12, we can clearly
see that RIPOST generated/detected larger empty blocks in different
portions of the domain due to the first phase of partitioning. It then
focused deeper partitioning on the densely populated portions,
thanks to the second phase. Meanwhile, HDPView applied more
partitioning across a wider portion of the domain. Partitioning
empty regions wrongly and keeping the blocks mixed, did impact
the performances of HDPView. In terms of RMSE, and based on our
test queries, HDPView gave an RMSE ×1.27 larger than RIPOST.

Workload dependent approaches

In order to compare RIPOST with HDMM, DAWA, and the naive
solution Identity, we used tensors with smaller domains. This is
because both HDMM and DAWA have high computational com-
plexity, and Identity requires a large amount of memory storage
for big domains, making them impractical for high-dimensional
tensors. Therefore, we used the Adult dataset with a pre-selected
set of dimensions with a small domain (referred to as *Small-Adult*),
and also the Jm dataset. In these experiments, we increased the
number of dimensions as much as possible, creating a tensor and
3000 queries for testing at each step.

In Figures 13 and 14, we show the R-RMSE results for both the
Small-Adult and Jm datasets, respectively. We observe that both
DAWA and HDMM suffer as the number of dimensions/domain
size increases because their optimizations fail to find the optimal
strategy for answering the workload. In contrast, RIPOST maintains
better performance than all of them in most tests. Regarding Iden-
tity, the noise accumulated by each query grows as the domain size
increases, which is evident in both Figure 13 and 14.

6.3 Sensitivity analysis of hyperparameters

In this section, we analyze the behavior of RIPOST by evaluating
its performance across different values of the hyperparameters.
For this evaluation, we used a 2D tensor created from the *Adult*
dataset and a random workload. In each experiment, we vary one

<figure><img src="image_12.png" /><figcaption>Figure 14: R-RMSE results based on Jm dataset</figcaption></figure>

parameter while keeping the others fixed at their default values.
The performance of RIPOST is measured using the RMSE and the
number of generated blocks. The hyperparameters and their default
values are: $\epsilon = 0.1$, $\alpha = 0.3$, $\beta = 0.4$, $\gamma = 0.9$.

**Privacy budget** $\epsilon$: Here, we measured the performance of RIPOST obtained while changing the total privacy budget allocation $\epsilon$. A smaller value of $\epsilon$ indicates stronger privacy guarantees, which results in higher noise (randomness) in the output.

From Figure 15 first plot, we observe that RIPOST behaves con-
sistently with the characteristics of differential privacy. Specifically,
as the privacy budget increases, the error (RMSE) decreases, and
the number of generated blocks increases since *Secure cc* becomes
more accurate. The perturbation error (PE) did not have a significant
effect in this case (more blocks generated) because, as $\epsilon$ increases,
the noise added to the leaf blocks becomes smaller.

**Parameter α:** According to Algorithm 1, RIPOST uses this pa-
rameter to distribute the budget $\epsilon$ between leaf perturbation $\epsilon_p$ and
the decomposition ($\epsilon_d$). A smaller $\alpha$ means more budget is allocated
to leaf perturbation and less to the decomposition, and vice-versa.
From Figure 15 (second plot), we observe that as $\alpha$ increases, more
blocks are generated, which is expected. However, the RMSE also
increases due to the higher perturbation error (PE). This happens
because: (i) less budget is allocated to leaf perturbation, resulting
in more noise, and (ii) the number of blocks increases. Based on the
results in Figure 15 (second plot), the best performance of RIPOST is
found when $\alpha$ is between 0.2 and 0.4, achieving a balance between
decomposition accuracy and perturbation error.

**Parameter γ:** According to Algorithm 1, RIPOST uses this pa-
rameter to distribute the budget $\epsilon_d$ between the first phase of the
decomposition $\epsilon_1$ and the second phase $\epsilon_2$. A smaller $\gamma$ means less
budget is allocated to phase 1 and more to phase 2, and vice-versa.

From Figure 15 (third plot), we observe that as $\gamma$ increases, more
blocks are generated, and there is a decrease in RMSE. This high-
lights the importance of the first phase of the decomposition in
RIPOST, which aims to separate the non-empty cells from the empty
ones. This phase is one of the most distinctive features of RIPOST
compared to other existing decomposition algorithms, and these
results confirm the observations made in Section 4.
<figure><img src="image_13.png" /><figcaption>Figure 15: Analysis of hyperparameters</figcaption></figure>

**Parameter $\beta$**: According to Algorithm 1, RIPOST uses this pa- rameter to allocate the decomposition budget for each phase, $\epsilon_1$ (or $\epsilon_2$), between $Secure_{cc}$, $\epsilon_{cc}^1$ (or $\epsilon_{cc}^2$), and $Secure_{ss}$, $\epsilon_{ss}^1$ (or $\epsilon_{ss}^2$). A smaller $\beta$ means less budget is allocated to $Secure_{cc}$ and more to $Secure_{ss}$, and vice versa.

From Figure 15 (fourth plot), we observe that the performance of RIPOST in terms of RMSE and the number of blocks does not follow a clear trend, and fluctuates for each value of $\beta$. This suggests that both $Secure_{cc}$ and $Secure_{ss}$ play equally important roles in achieving optimal results.

# 7 DISCUSSION

In this section, we put forward some discussion points that can be considered as possible extensions and improvements that can be added to our proposed solution. First, according to the budget distribution strategy introduced in Section 5.2, both $Secure_{cc}$ and $Secure_{ss}$ will never consume the full budget allocated to them. This is due to the fact that the decomposition eventually converges; even if the depth $h$ varies from tensor to tensor, it can never be infinite. A simple optimization would be to take the unconsumed budget during the decomposition and add it to $\epsilon_p$ to reduce the noise added to the leaves, thus reducing the perturbation error (PE). On the same track of improving budget consumption, an improvement could be to apply $Secure_{cc}$ normally once and skip it (or give it budget 0) for a certain number of steps $k$, and afterwards apply it normally once again, and so on. This will allow us to chop the budget for $Secure_{cc}$ in both phases by $k$ and add the saved budget to $\epsilon_p$ to reduce the PE.

In Figure 16, we present the results of a small experiment con- ducted on a 2D tensor created using the Adult dataset. On the x-axis, we display the number of steps $k$ between consecutive applications of the $Secure_{cc}$. From the results, we observe the following: (i) as $k$ increases, the number of blocks generated also increases, which leads to a reduction in the aggregation error (AE), and (ii) the RMSE decreases, highlighting the advantage of reallocating the budget gained to reduce the perturbation error (PE). Another interesting direction for improving both decomposition computation cost and privacy consumption is to focus on enhancing the algorithm for $Secure_{ss}$. Specifically, in Algorithm 3, line 3, RIPOST iterates over all possible cutting points in the domain. A potential improvement could involve considering a smaller search space, such as a random sample of the domain. By selecting this sample randomly, we could

<figure><img src="image_14.png" /><figcaption>Figure 16: Results of extended RIPOST</figcaption></figure>

enforce privacy and reduce budget consumption [8]. However, such enhancements require careful consideration, as random sampling may lead to suboptimal partitioning. For this reason, we prefer to address this in a dedicated future project. The final point we would like to mention is the potential use of the generated tree to improve both query processing time and accuracy, as highlighted in [3, 29]. In the current version of RIPOST, the tree can be leveraged to enhance processing time. However, RIPOST does not yet incorporate the tree to improve accuracy. Given the results obtained in Section 6, it would be interesting to explore whether we can extend RIPOST to also address accuracy in future work.

# 8 CONCLUSION

In this work, we addressed the problem of releasing a privacy- preserving view of multidimensional data using a domain decomposition-based method. We introduced our solution, RIPOST, which overcomes the design and theoretical limitations of previ- ously proposed solutions in the literature, specifically regarding data-aware splitting and the independence from the depth $h$ of the decomposition. Through extensive experiments, we demonstrated that RIPOST outperforms existing methods in terms of the utility of the generated view. The positive results obtained in this work encourage us to explore various extensions and improvements in future work, particularly focusing on tighter budget management and reducing computational costs.
REFERENCES

[1] John M Abowd. 2018. The US Census Bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2867–2867.

[2] Gergely Acs, Luca Melis, Claude Castelluccia, and Emiliano De Cristofaro. 2018. Differentially private mixture of generative neural networks. IEEE Transactions on Knowledge and Data Engineering 31, 6 (2018), 1109–1121.

[3] Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, Entong Shen, and Ting Yu. 2012. Differentially private spatial decompositions. In 2012 IEEE 28th International Conference on Data Engineering. IEEE, 20–31.

[4] Bolin Ding, Marianne Winslett, Jiawei Han, and Zhenhui Li. 2011. Differentially private data cubes: optimizing noise sources and consistency. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. 217–228.

[5] Cynthia Dwork. 2006. Differential privacy. In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II 33. Springer, 1–12.

[6] Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science 9, 3–4 (2014), 211–407.

[7] Cynthia Dwork, Aaron Roth, et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science 9, 3–4 (2014), 211–407.

[8] Hamid Ebadi, Thibaud Antignac, and David Sands. 2016. Sampling and partitioning for differential privacy. In 2016 14th Annual Conference on Privacy, Security and Trust (PST). IEEE, 664–673.

[9] Ju Fan, Tongyu Liu, Guoliang Li, Junyou Chen, Yuwei Shen, and Xiaoyong Du. 2020. Relational data synthesis using generative adversarial networks: A design space exploration. arXiv preprint arXiv:2008.12763 (2020).

[10] Frederik Harder, Kamil Adamczewski, and Mijung Park. 2021. Dp-merf: Differentially private mean embeddings with randomfeatures for practical privacy-preserving data generation. In International conference on artificial intelligence and statistics. PMLR, 1819–1827.

[11] Ali Inan, Murat Kantarcioglu, Gabriel Ghinita, and Elisa Bertino. 2010. Private record matching using differential privacy. In Proceedings of the 13th International Conference on Extending Database Technology. 123–134.

[12] James Jordon, Jinsung Yoon, and Mihaela Van Der Schaar. 2019. PATE-GAN: Generating synthetic data with differential privacy guarantees. In International conference on learning representations.

[13] Fumiyuki Kato, Tsubasa Takahashi, Shun Takagi, Yang Cao, Seng Pei Liew, and Masatoshi Yoshikawa. 2022. HDPView: differentially private materialized view for exploring high dimensional relational data. arXiv preprint arXiv:2203.06791 (2022).

[14] Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajhala, Michael Hay, and Gerome Miklau. 2019. Privatesql: a differentially private sql query engine. Proceedings of the VLDB Endowment 12, 11 (2019), 1371–1384.

[15] Eleonora Kreaćić, Navid Nouri, Vamsi K Potluru, Tucker Balch, and Manuela Veloso. 2023. Differentially private synthetic data using KD-trees. In Uncertainty in Artificial Intelligence. PMLR, 1143–1153.

[16] Ala Eddine Laouir and Abdessamad Imine. 2024. SLIM-View: Sampling and Private Publishing of Multidimensional Databases. In Proceedings of the Fourteenth ACM Conference on Data and Application Security and Privacy. 391–402.

[17] Chao Li, Michael Hay, Gerome Miklau, and Yue Wang. 2014. A data-and workload-aware algorithm for range queries under differential privacy. arXiv preprint arXiv:1410.0265 (2014).

[18] Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. 2015. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB journal 24 (2015), 757–781.

[19] Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavajjhala. 2018. Optimizing error of high-dimensional statistical queries under differential privacy. arXiv preprint arXiv:1808.03537 (2018).

[20] Wahbeh Qardaji, Weining Yang, and Ninghui Li. 2014. Preview: practical differentially private release of marginal contingency tables. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 1435–1446.

[21] Sina Shaham, Gabriel Ghinita, Ritesh Ahuja, John Krumm, and Cyrus Shahabi. 2023. HTF: Homogeneous Tree Framework for Differentially Private Release of Large Geospatial Datasets with Self-tuning Structure Height. ACM transactions on spatial algorithms and systems 9, 4 (2023), 1–30.

[22] Graham Cormode Cecilia Procopiuc Divesh Srivastava, Entong Shen, and Ting Yu. [n.d.]. Differentially Private Spatial Decompositions. ([n. d.]).

[23] Shun Takagi, Tsubasa Takahashi, Yang Cao, and Masatoshi Yoshikawa. 2021. P3GM: Private high-dimensional data release via privacy preserving phased generative model. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 169–180.

[24] Apple Team. [n.d.]. learning-with-privacy-at-scale. ([n. d.]). https://docs-assets.developer.apple.com/ml-research/papers/learning-with-privacy-at-scale.pdf

[25] Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. 2020. Differentially private SQL with bounded user contribution. Proceedings on privacy enhancing technologies 2020, 2 (2020), 230–250.

[26] Chugui Xu, Ju Ren, Yaoxue Zhang, Zhan Qin, and Kui Ren. 2017. DPPro: Differentially private high-dimensional data release via random projection. IEEE Transactions on Information Forensics and Security 12, 12 (2017), 3081–3093.

[27] E. Zeidler, W. Hackbusch, H.R. Schwarz, and B. Hunt. 2004. Oxford Users' Guide to Mathematics. OUP Oxford.

[28] Jun Zhang, Graham Cormode, Cecilia M Procopiuc, Divesh Srivastava, and Xiaokui Xiao. 2017. Privbayes: Private data release via bayesian networks. ACM Transactions on Database Systems (TODS) 42, 4 (2017), 1–41.

[29] Jun Zhang, Xiaokui Xiao, and Xing Xie. 2016. Privtree: A differentially private algorithm for hierarchical decompositions. In Proceedings of the 2016 international conference on management of data. 155–170.

[30] Xiaojian Zhang, Rui Chen, Jianliang Xu, Xiaofeng Meng, and Yingtao Xie. 2014. Towards accurate histogram publication under differential privacy. In Proceedings of the 2014 SIAM international conference on data mining. SIAM, 587–595.

[31] Zhikun Zhang, Tianhao Wang, Jean Honorio, Ninghui Li, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. 2021. Privsyn: Differentially private data synthesis. (2021).