## 5 Sanitization Algorithm
### Grouping Rules
: Since  
\[E[err(C_{i})]=E[\frac{\sum_{H_{j}\in C_{i}}err(H_{i})}{|C_{i}|}]=\frac{\sum_{H _{j}\in C_{i}}err(H_{i})}{|C_{i}|}=\sum_{H_{j}\in C_{i}}\frac{\frac{|H_{j}- \overline{C}_{i}|+\frac{\lambda}{|C_{i}|}}{H_{j}}}{|C_{i}|}, \tag{23}\]  
Theorem 6 can be proved by using the method of Theorem 4 similarly, and the monotonicity of \(E[err(C_{i})]\) on \(H_{j}\) is consistent with that of \(E[err(H_{j})]\) on \(H_{j}\). From Theorems 1-3, in order to reasonably solve the problem considered in this paper, the following two grouping rules are needed at least. 1. A sorting from small to large is favorable to improve the availability of small bins first. 2. The closer bins should be divided into the same group as much as possible to reduce the relative error. Based on the two grouping rules above, we formulate the following optimization problem, referred to as OP. **OP**: Given a histogram \(H=\{H_{1},H_{2},\ldots,H_{n}\}\) sorted in ascending order and a privacy budget \(\epsilon\), the goal is to partition \(H\) into \(k\) non-overlapping groups \(C=\{C_{1},C_{2},\ldots,C_{k}\}\), such that \(\bigcup_{i}C_{i}=H\) and \(C_{i}\cap C_{j}=\emptyset\) for all \(i\
eq j\) and \(k\geq 2\). Define the average error as \(err_{Agg}=\frac{\sum_{C_{i}\in C}\sum_{H_{j}\in C_{i}}E[err(H_{j})]}{n}\), where the objective is to find an optimal grouping \(C^{*}=\{C_{1}^{*},C_{2}^{*},\ldots,C_{k}^{*}\}\) that minimizes \(err_{Agg}\), i.e., \(C^{*}=\arg\min_{C}err_{Agg}\). Here, the error for each bin \(H_{j}\) is given by \(err(H_{j})=\frac{|\widehat{H}_{j}-H_{j}|}{H_{j}}\), with \(\widehat{H}_{j}=\overline{C}_{i}+\frac{Lap(\lambda)}{|C_{i}|}\) and the noise scale \(\lambda=\frac{1}{\epsilon}\). The OP problem, which is founded on the dynamic programming technique introduced in [19], incurs a complexity of \(O(kn^{2})\) when \(k\) is predefined. Furthermore, in cases where \(k\) is not specified, determining the optimal grouping escalates to a complexity of \(O(n^{4})\). Consequently, this approach becomes impractical for large real-world datasets due to computational intensity. To address this, the paper introduces a greedy optimal grouping strategy, designated as the GP (Greedy Problem), without predetermining \(k\). Incorporating Theorems 4-6, the formal description of the GP is as follows. **The GP:** Given a histogram \(H=\{H_{1},H_{2},\ldots,H_{n}\}\) sorted in ascending order and a privacy parameter \(\epsilon\), the task is to divide \(H\) into \(k\) non-overlapping groups \(C=\{C_{1},C_{2},\ldots,C_{k}\}\), where the number of groups satisfies \(1\leq k\leq n\), such that \(\bigcup_{i=1}^{k}C_{i}=H\) and for any pair of distinct groups \(C_{i}\) and \(C_{q}\), \(C_{i}\cap C_{q}=\emptyset\) (with the condition applicable when \(k\geq 2\)). The objective is to identify a grouping configuration \(C^{*}=\{C_{1}^{*},C_{2}^{*},\ldots,C_{k}^{*}\}\) that adheres to Equation (24). \[max\{|C_{i}||E[err(C_{i}\cup H_{j})]<\frac{E[err(C_{i})]|C_{i}|+E[err(H_{j})]^{*}} {(|C_{i}|+1)}\}, \tag{24}\]  
where  
\[E[err(C_{i})]=\sum_{H_{i}\in C_{i}}\frac{1}{H_{i}}(|H_{i}-\overline{C}_{i}|+ \frac{\lambda}{|C_{i}|})/|C_{i}|, \tag{25}\]  
\[E[err(C_{i}\cup H_{j})]=\sum_{H_{i}\in(C_{i}\cup H_{j})}\frac{1}{H_{i}}(|H_{r}- \overline{C}_{i}|+\frac{\lambda}{|C_{i}|+1})/(|C_{i}|+1), \tag{26}\]  
\[\overline{C}_{i}^{\prime}=(\overline{C}_{i}|C_{i}|+H_{j})/(|C_{i}|+1), \tag{27}\]  
\[E[err(H_{j})]^{*}=min_{j+1\leq e\leq n}(E[err(H_{j})]|H_{j}\in C_{\{H_{j}, \cdots,H_{e}\}}) \tag{28}\]  
and  
\[\lambda=\frac{1}{\epsilon}. \tag{29}\]  
Therein, Formula (28) defines \(C_{\{H_{j},\ldots,H_{e}\}}\) as a group comprising bins \(H_{j},\ldots,H_{e}\). From Formula (24), it is evident that, apart from computing \(E[err(C_{i}\cup H_{j})]\) and \(E[err(C_{i})]\), it is also necessary to calculate  
\[E[err(H_{j})]^{*}=\min_{j+1\leq e\leq n}\Bigl{(}E[err(H_{j})]\mid H_{j}\in C_{ \{H_{j},\ldots,H_{e}\}}\Bigr{)}. \tag{30}\]  
Formula (30) varies each time the composition of groups changes and thus requires recalculation accordingly.