## 5 Sanitization Algorithm
### Grouping Rules  
According to studies [13; 15; 19; 22], grouping constitutes a prevalent technique in differential privacy histogram publication for enhancing accuracy. The formal definition of histogram grouping is outlined as follows. **Definition 4** (Histogram grouping). : _Given an original bin sequence \(H=\{H_{1},H_{2},\cdots,H_{n}\}\) of the histogram, and assuming that \(k\) groups of \(C=\{C_{1},C_{2},\cdots,C_{k}\}\) are formed after grouping and each group \(C_{i}\) covers \(|C_{i}|\) bins, the average count \(\overline{C}_{i}\) of group \(C_{i}\) is expressed in Formula (7)._  
\[\overline{C}_{i}=\frac{\sum_{H_{j}\in C_{i}}H_{j}}{|C_{i}|} \tag{7}\]  
Assume that a sanitized histogram \(\widetilde{H}=\{\widetilde{H}_{1},\widetilde{H}_{2},\cdots,\widetilde{H}_{n}\}\) satisfies \(\epsilon\)-DP, where each \(\widetilde{H}_{j}\) represents a sanitized version of \(H_{j}\in H\). For \(H_{j}\in C_{i}\), it can be seen that  
\[\widetilde{H}_{j}=\overline{C}_{i}+\frac{x}{|C_{i}|}, \tag{8}\]  
where \(x\sim Lap(\lambda)\) and \(\lambda=\frac{1}{\epsilon}\). Then, the relative error between \(\widetilde{H}_{j}\) and \(H_{j}\) can be expressed as  
\[err(H_{j})=\frac{|\widetilde{H}_{j}-H_{j}|}{max(H_{j},\delta)}, \tag{9}\]  
where \(\delta\geq 0\) serves as a small positive constant to avoid division by zero when \(H_{j}=0\). When \(H_{j}\geq 1\) and \(\delta=1\), the mean relative error between \(\widetilde{C}_{i}\) and \(C_{i}\) is given by  
\[err(C_{i})=\frac{\sum_{H_{j}\in C_{i}}err(H_{j})}{|C_{i}|}=\sum_{H_{j}\in C_{ i}}\frac{\frac{|\widetilde{H}_{j}-H_{j}|}{H_{j}}}{|C_{i}|}. \tag{10}\]  
For any \(H_{j}\in C_{i}\), the expected relative error between \(\widetilde{H}_{j}\) and \(H_{j}\) can be expressed as  
\[E[err(H_{j})]=E[\frac{|\widetilde{H}_{j}-H_{j}|}{H_{j}}]=\frac{1}{H_{j}}E[| \widetilde{H}_{j}-H_{j}|], \tag{11}\]  
where  
\[E[|\widetilde{H}_{j}-H_{j}|]=\int_{-\infty}^{+\infty}|\overline{C}_{i}+\frac{ x}{|C_{i}|}-H_{j}|\frac{1}{2\lambda}e^{-\frac{|x|}{\lambda}}dx\]  
and \(x\sim Lap(\lambda)\). Consequently, the expected mean relative error between \(\widetilde{C}_{i}\) and \(C_{i}\) is given by Formula (12). \[ \begin{split} E[err(C_{i})]&=E\bigg{[}\frac{\sum_{H_ {j}\in C_{i}}|\widetilde{H}_{j}-H_{j}|}{|C_{i}|}\bigg{]}\\ &=\sum_{H_{j}\in C_{i}}\frac{1}{H_{j}}\frac{E[|\widetilde{H}_{j}- H_{j}|]}{|C_{i}|}.\end{split}  \tag{12}\]  
Regarding our problem, we initially present Theorem 1, which offers an approximate characterization of the relative error between sanitized and original bins. **Theorem 1**. : _Given \(C_{i}\), \(\overline{C}_{i}\), \(|C_{i}|\), \(H_{j}\in C_{i}\), \(\widetilde{H}_{j}\), and \(\lambda\), then \(E[err(H_{j})]\approx\frac{1}{H_{j}}(|H_{j}-\overline{C}_{i}|+\frac{\lambda}{| C_{i}|})\), where \(\frac{|H_{j}-\overline{C}_{i}|}{H_{j}}\) is the Relative Reconstruction Error (RRE) and \(\frac{\lambda}{|\overline{C}_{i}|H_{j}}\) is the Relative Noise Error (RNE)._  
Proof. : In order to obtain \(E[err(H_{j})]\), we need to calculate \(E[|\widehat{H}_{j}-H_{j}|]\). According to the relationship between \(H_{j}\) and \(\widetilde{C}_{i}\), the discussion can be divided into the following two cases. (1) When \(H_{j}\geq\widetilde{C}_{i}\), it has  
\[ \begin{split} E[|\widehat{H}_{j}-H_{j}|]&=\int_{- \infty}^{+\infty}|\overline{C}_{i}-H_{j}+\frac{x}{|\overline{C}_{i}|}\big{|} \frac{1}{2\lambda}e^{-\frac{|x|}{\lambda}}dx\\ &=\int_{-\infty}^{0}-(\overline{C}_{i}-H_{j}+\frac{x}{|C_{i}|}) \frac{1}{2\lambda}e^{\frac{x}{\lambda}}dx\\ &-\int_{0}^{(H_{j}-\overline{C}_{i})|C_{i}|}(\overline{C}_{i}-H_ {j}+\frac{x}{|C_{i}|})\frac{1}{2\lambda}e^{-\frac{x}{\lambda}}dx\\ &+\int_{(H_{j}-\overline{C}_{i})|C_{i}|}^{+\infty}(\overline{C}_ {i}-H_{j}+\frac{x}{|C_{i}|})\frac{1}{2\lambda}e^{-\frac{x}{\lambda}}dx\\ &=H_{j}-\overline{C}_{i}+\frac{\lambda}{|C_{i}|}e^{-\frac{H_{j} -\overline{C}_{i}}{|\overline{C}_{i}|}}\.\end{split} \] (13) (2) When \(H_{j}<\widetilde{C}_{i}\), it has  
\[