## 2 Related Work  
Researchers have derived numerous valuable solutions concerning DP histogram publishing [13; 14; 15; 17; 18; 19; 22; 23; 24; 25; 26; 27]. [PERSON] et al. [5] introduced a method applicable to equal-width histograms for the first time. They augmented each bin in the equal-width histogram with Laplace noise and utilized the resulting noisy bins for range queries. When executing large-range queries, this approach results in a substantial accumulation of noise within the query outcomes, ultimately compromising the data availability of query results. In [14], a methodology known as Boost1 is presented, which relies on the optimal linear unbiased estimator. In practice, however, this method fails to efficiently mitigate the noise associated with each bin in the histogram. To address the challenge posed by a wide range of queries, [PERSON] et al. [19] put forward two techniques: NoiseFirst and StructureFirst. With NoiseFirst, dynamic programming technology is employed to reconstitute the output of an equal-width histogram by consolidating adjacent, similar bins. Conversely, StructureFirst utilizes the exponential mechanism [5] to determine the boundaries of output bins, thereby forming a non-equivwidth histogram, and subsequently incorporates appropriate noise into the adjusted results prior to publication. While StructureFirst effectively mitigates the error induced by perturbation (i.e., noise error), it inadvertently introduces a novel error (i.e., reconstruction error). Furthermore, during the reconstruction process, the number of bins(\(k\)) is manually specified, rendering it incapable of effectively balancing noise error against reconstruction error. In order to enhance the accuracy of sanitized data (i.e., data with added noise conforming to a specific distribution) and strike a superior balance between noise and reconstruction errors, the study [13] introduces PHPartition. This method employs a dynamic search via hierarchical clustering techniques to determine the optimal value \(k\), rendering it an improvement over StructureFirst. Additionally, the study [17] puts forth an adaptive sampling methodology for achieving differential privacy in the histogram publishing of dynamically evolving datasets. Furthermore, the work presented in [24] proposes DPDR, a grouping technique grounded in the ranking methodology of the exponential mechanism. Nonetheless, these methodologies primarily focus on devising reconstruction strategies that enhance the overall accuracy of histograms or the precision of larger bins, inadvertently overlooking the accuracy of smaller bins. In some instances, they even compromise the precision of small bins to augment the absolute accuracy for broader bins or the histogram as a whole [19]. While large bins typically garner significant attention, the significance of small bins, as exemplified by phenomena like the \"Black Swan Event\", cannot be discounted. As far as we know, there is almost no research focusing specifically on prioritizing the accuracy of small bins, despite some studies employing a metric of relative error. In [28], through analyzing the correlation between the cumulative probability of noise and the privacy level in Laplace mechanism, and integrating the relative error metric, an algorithm was proposed to inject varying levels of noise proportional to query preferences. However, the algorithm's implementation necessitates prior knowledge of these query preferences, which may contain sensitive information to some extent, thereby posing a risk of privacy leakage. In addition, the metric of relative error is also considered in study [29]. Therein, a DP publishing algorithm for batch queries based on gradual iterations is proposed to mitigate noise error; specifically, the privacy budget is allocated according to intermediate noisy results, with the overarching goal of minimizing the overall relative error while efficiently managing the consumption of the privacy budget. Through iterations, queries are adaptively adjusted to achieve the best cost-performance ratio.