## 5 Sanitization Algorithm
### Grouping Rules
Theorem 2 shows that if a bin smaller than the average of the current group is added, the relative error of the current group adding another bin closer to the bin is smaller than that of adding another bin farther away from the bin. Theorem 3: _When \(|C_{i}|\) gets bigger, \(RNE\) gets smaller._  
Proof: Assuming that \(H_{j}\in C_{i}\), it has \(E[err(H_{j})]=\frac{1}{H_{j}}(|H_{j}-\overline{C}_{i}|+\frac{\lambda}{|C_{i}|})\) with \(RNE=\frac{\lambda}{H_{j}|C_{i}|}\). Therefore, the result follows. Theorem 3 demonstrates that the more bins a group contains, the smaller the Relative Noise Error (\(RNE\)) for each individual bin within that group. Theorems 2 and 3 collectively facilitate enhancing the accuracy of smaller bins during the grouping process of a new bin. Proceeding further in this section, we delve into analyzing the relative error associated with a solitary bin situated within a fixed group, leading us to the derivation of Theorem 4. **Theorem 4**. : _Given \(C_{i}\), \(\overline{C}_{i}\), \(|C_{i}|\), \(H_{j}\in C_{i}\), and \(\lambda\), then it has the following cases._  
1. _When_ \(|C_{i}|\overline{C}_{i}<\lambda\)_,_ \(E[err(H_{j})]\) _decreases as_ \(H_{j}\) _increases;_
2. _When_ \(|C_{i}|\overline{C}_{i}\geq\lambda\)_, two cases exist as follows._
3. _If_ \(H_{j}\leq\overline{C}_{i}\)_, then_ \(E[err(H_{j})]\) _decreases as_ \(H_{j}\) _increases;_
4. _If_ \(H_{j}>\overline{C}_{i}\)_, then_ \(E[err(H_{j})]\) _increases as_ \(H_{j}\) _increases._  
Proof. : Let \(f(x)=\frac{1}{x}(|x-\overline{C}_{i}|+\frac{\lambda}{|C_{i}|})\), where \(x>0\) is the variable for \(H_{j}\), and the derivative \(f(x)\) can be obtained as follows:  
\[\frac{df(x)}{dx}= \begin{cases}-\dfrac{\overline{C}_{i}}{x^{2}}-\dfrac{\lambda }{x^{2}|C_{i}|},&0<x\leq\overline{C}_{i}\\ \dfrac{\overline{C}_{i}}{x^{2}}-\dfrac{\lambda}{x^{2}|C_{i}|},&x>\overline{C}_ {i}\end{cases} . \tag{21}\]  
i.e.,  
\[\frac{df(x)}{dx}= \begin{cases}<0,&0<x\leq\overline{C}_{i}\\ \geq 0,&x>\overline{C}_{i},|C_{i}|\overline{C}_{i}\geq\lambda\\ <0,&x>\overline{C}_{i},|C_{i}|\overline{C}_{i}<\lambda\end{cases}  \tag{22}\]  
Thus, the result follows. **Example 1**. : _When \(\epsilon=0.0005\), \(\lambda=\frac{1}{\epsilon}=2000\), \(\overline{C}_{i}=100\), and \(|C_{i}|=10\), it has \(|C_{i}|\overline{C}_{i}<\lambda\). Assuming that \(H_{j}\in C_{i}\), the change of \(ln(E[err(H_{j})])\) with respect to \(H_{j}\) is illustrated in Figure 1. When \(\epsilon=0.01\), \(\lambda=\frac{1}{\epsilon}=100\), \(\overline{C}_{i}=100\), and \(|C_{i}|=10\), it has \(|C_{i}|\overline{C}_{i}\geq\lambda\). Assume that \(H_{j}\in C_{i}\); the behavior of \(ln(E[err(H_{j})])\) as \(H_{j}\) varies is shown in Figure 2. Finally, the conclusions of Theorem 4 are intuitively demonstrated directly through Figures 1 and 2._  
Given \(H=\{H_{1},H_{2},\cdots,H_{n}\}\) in order from small to large, Theorem 4 shows that the maximum relative error of the histogram in each group depends on the bins at both ends. **Theorem 5**. : _Given \(C_{i}\), \(\overline{C}_{i}\), \(|C_{i}|\), \(H_{j}\in C_{i}\), and \(\lambda\) with \(\lambda=\frac{1}{\epsilon}\), then \(E[err(H_{j})]\) increases with the increase in \(\lambda\) (or the decrease in \(\epsilon\)) and decreases otherwise._  
Proof. : From \(E[err(H_{j})]=\frac{1}{H_{j}}(|H_{j}-\bar{C}_{i}|+\frac{\lambda}{|C_{i}|})\), \(E[err(H_{j})]\) increases with the increase in \(\lambda\); otherwise, it decreases. When \(\lambda=\frac{1}{\epsilon}\), \(E[err(H_{j})]\) increases with the decrease in \(\epsilon\); otherwise, it decreases. **Theorem 6**. : _Given \(C_{i}\), \(\overline{C}_{i}\), \(|C_{i}|\), \(H_{j}\in C_{i}\), and \(\lambda\), the monotonicity of \(E[err(C_{i})]\) on \(H_{j}\) is the same as the monotonicity of \(E[err(H_{j})]\) on \(H_{j}\)._  
Proof.