## 1 Introduction
Hence, even in the presence of noisy statistical information, it is imperative to direct attention towards data analysis conducted under a comparably uniform level of noise. In the context of hospital patient data analysis using histograms, health information is sensitive, especially regarding serious illnesses, which typically involve fewer cases and are vital for the in-depth analysis of such diseases. Consider a hypothetical histogram of patient data resulting in counts of 2, 3, 10, 9, 8, 1, and 1, wherein 1, 1, 2, and 3 denote the respective counts for severe disease categories. Following the guidance of study [5], if noise from a Laplace mechanism with a scale parameter \(\lambda\) were introduced to each datum to enforce \(\frac{1}{\lambda}\)-differential privacy, the expected absolute magnitude of the noise added to each count would be \(\lambda\). This addition, particularly in relation to the counts of 1, 1, 2, and 3 for severe diseases, introduces a significant relative error. study [13; 15; 19; 22] introduces grouping methodologies that can moderately enhance the overall accuracy of the data; however, this approach necessitates balancing the noise error induced by random distribution against the reconstruction error due to grouping. Current methodologies, while attempting to weigh absolute accuracy against both types of errors, still encounter the challenge of excessive noise introduced by low counts. Specifically, in Section 4 of this paper, a formulaic analysis is carried out for the \(\epsilon\)-DP histogram publishing, and it is concluded that under the uneven data distribution, small bins tend to bear much more relative noise than large bins. Indeed, small bins are sometimes just as important as large bins or much more crucial than large bins. Therefore, this paper considers how to prioritize balancing the accuracy of small bins and minimize the mean relative error of the histogram under \(\epsilon\)-DP. The main contributions of this paper are summarized as follows. * A sanitization algorithm, SReB_GCA, is introduced, which adopts relative error as its metric for accuracy. This approach diverges from numerous methodologies documented in the study [15; 19], wherein the mean squared error or absolute error is typically employed, with the histogram being assessed collectively to ascertain a cumulative mean squared or absolute error for the purpose of optimization. Consequently, the significance of smaller bins may be inadvertently disregarded. * The grouping rules under relative error are theoretically deduced and analyzed. There are two types of errors in DP histogram publishing, including the reconstruction error due to grouping and the noise error due to Laplace noise being injected. From the analysis of their relative error forms, it is concluded that sorting from small to large is favorable for improving the utility of small bins first, a perspective not thoroughly explored in the previous literature. Additionally, a lower bound in the greedy grouping process of SReB_GCA is theoretically deduced, which facilitates maximizing the number of bins grouped and approximately optimizing the mean relative error of the histogram. Moreover, we conduct extensive experiments on four real-life and synthetic datasets to evaluate the performance of our approach in comparison with a benchmark method (DP_BASE) across single-value queries, range queries, and analyses of data distribution. Additionally, we compare this performance with several other existing methods that leverage data distribution characteristics. The remainder of this paper is organized as follows: Section 2 introduces the related work on DP histogram publishing. Section 3 presents the relevant definitions of DP. Section 4 details the problem and presents initial approaches. Section 5 formally defines the problem and proposes a sanitization algorithm, SReB_GCA, encompassing the grouping rules and an approximately greedy optimal grouping strategy, theoretically derived and analyzed. Section 6 presents the experimental evaluation of SReB_GCA.