## 5 Sanitization Algorithm
### Grouping Rules
\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}^{(H_{j}-\overline{C}_{i})|C_{i}|}-(\overline{C} _{i}-H_{j}+\frac{x}{|\overline{C}_{i}|})\frac{1}{2\lambda}e^{\frac{x}{\lambda} }dx\\ &+\int_{(H_{j}-\overline{C}_{i})|C_{i}|}^{0}(\overline{C}_{i}-H_ {j}+\frac{x}{|C_{i}|})\frac{1}{2\lambda}e^{\frac{x}{\lambda}}dx\\ &+\int_{0}^{+\infty}(\overline{C}_{i}-H_{j}+\frac{x}{|\overline{ C}_{i}|})\frac{1}{2\lambda}e^{-\frac{x}{\lambda}}dx\\ &=\overline{C}_{i}-H_{j}+\frac{\lambda}{|\overline{C}_{i}|}e^{ \frac{H_{j}-\overline{C}_{i}}{|\overline{C}_{i}|}}\.\end{split}  \tag{14}\]  
Based on (13) and (14), it can be seen that  
\[E[|\widehat{H}_{j}-H_{j}|]=|\overline{C}_{i}-H_{j}|+\frac{\lambda}{|\overline{ C}_{i}|}e^{-\frac{|H_{j}-\overline{C}_{i}|}{|\overline{C}_{i}|}}. \tag{15}\]  
Therefore, \(E[|\widehat{H}_{j}-H_{j}|]\) is mainly composed of two parts, where the part \(|\overline{C}_{i}-H_{j}|\) is caused by grouping and the other part \(\frac{\lambda}{|\overline{C}_{i}|}e^{-\frac{|H_{j}-\overline{C}_{i}|}{| \overline{C}_{i}|}}\) is caused by both grouping and Laplace noise injected. It is easy to obtain \(\frac{\lambda}{|\overline{C}_{i}|}e^{-\frac{|H_{j}-\overline{C}_{i}|}{| \overline{C}_{i}|}}\ \leq\frac{\lambda}{|\overline{C}_{i}|}\). Approximately, we use \(|H_{j}-\overline{C}_{i}|+\frac{\lambda}{|\overline{C}_{i}|}\) to represent the relative error between \(\widetilde{H}_{j}\) and \(H_{j}\). Therefore, \(E[err(H_{j})]\approx\frac{1}{H_{j}}(|H_{j}-\overline{C}_{i}|+\frac{\lambda}{| \overline{C}_{i}|})\) approximately, 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\)). From the above discussion, the result follows. Hence, the expectation of the mean relative error of \(C_{i}\) is  
\[E[err(C_{i})]=\sum_{H_{j}\in C_{i}}\frac{1}{H_{j}}\frac{|H_{j}-\overline{C}_{i}|+ \frac{\lambda}{|C_{i}|}}{|C_{i}|}. \tag{16}\]  
Theorem 2: _Assuming that \(H_{j}\in C_{i}\) and \(H_{j}\leq\overline{C}_{i}\), suppose there two bins \(H_{l}\) and \(H_{l^{\prime}}\) exist such that \(H_{j}\leq H_{l}\leq H_{l^{\prime}}\). Then, the relative error incurred by grouping \(H_{l}\) into \(C_{i}\) is less than that resulting from grouping \(H_{l^{\prime}}\) into \(C_{i}\)._  
Proof: From \(H_{j}\in C_{i}\), it has \(E[err(H_{j})]=\frac{1}{H_{j}}(|H_{j}-\overline{C}_{i}|+\frac{\lambda}{|C_{i}|})\), where \(RRE=\frac{|H_{j}-\overline{C}_{i}|}{H_{j}}\) and \(RNE=\frac{\lambda}{|C_{i}|H_{j}}\). If we add \(H_{l}\) to \(C_{i}\), it has  
\[E[err(H_{j})]=\frac{1}{H_{j}}(|H_{j}-\frac{\overline{C}_{i}|C_{i}|+H_{l}}{|C_ {i}|+1}|+\frac{\lambda}{|C_{i}|+1}), \tag{17}\]  
where \(RRE_{1}=\frac{1}{H_{j}}|H_{j}-\frac{\overline{C}_{i}|C_{i}|+H_{l}}{|C_{i}|+1}|\) and \(RNE_{1}=\frac{1}{H_{j}}\frac{\lambda}{|C_{i}|+1}\). If we add \(H_{l^{\prime}}\) to \(C_{i}\), it has  
\[E[err(H_{j})]=\frac{1}{H_{j}}|H_{j}-\frac{\overline{C}_{i}|C_{i}|+H_{l^{\prime }}}{|C_{i}|+1}|+\frac{1}{H_{j}}\frac{\lambda}{|C_{i}|+1}, \tag{18}\]  
where \(RRE_{2}=\frac{1}{H_{j}}|H_{j}-\frac{\overline{C}_{i}|C_{i}|+H_{l^{\prime}}}{| C_{i}|+1}|\) and \(RNE_{2}=\frac{1}{H_{j}}\frac{\lambda}{|C_{i}|+1}\). Since \(H_{j}\leq\overline{C}_{i}\) and \(H_{j}\leq H_{l}\leq H_{l^{\prime}}\), it has  
\[RRE_{1}=\frac{1}{H_{j}}|H_{j}-\frac{\overline{C}_{i}|C_{i}|+H_{l}}{|C_{i}|+1}| =\frac{1}{H_{j}}(\frac{\overline{C}_{i}|C_{i}|+H_{l}}{|C_{i}|+1}-H_{j}) \tag{19}\]  
and  
\[RRE_{2} =\frac{1}{H_{j}}|H_{j}-\frac{\overline{C}_{i}|C_{i}|+H_{l^{\prime }}}{|C_{i}|+1}| \tag{20}\] \[=\frac{1}{H_{j}}(\frac{\overline{C}_{i}|C_{i}|+H_{l}}{|C_{i}|+1}- H_{j}+\frac{H_{l^{\prime}}-H_{l}}{|C_{i}|+1})\] \[\geq\frac{1}{H_{j}}|H_{j}-\frac{\overline{C}_{i}|C_{i}|+H_{l}}{|C_ {i}|+1}|\] \[=RRE_{1}.\]  
Therefore, the result follows.