## 6 Experimental Evaluation
### Experimental Settings  
(1) Datasets  
Waitakere, Search Log, NetTrace, and Social Network are used for experiments in this paper, which are commonly employed in histogram publishing [13; 14; 19]. Among them, Waitakere is a semi-synthetic dataset derived from the 2006 Census Meshblock Dataset of New Zealand, comprising a total population of 186,471 spread across 1340 meshblocks. Search Log is a synthetic dataset of search query logs featuring the keyword \"[PERSON]\", covering the period from 1 January 2004 to 9 August 2009. This timeframe is divided into 32,768 intervals, each lasting 90 min. Each interval represents a bin of the histogram, used to tally the number of queries within those 90-min segments. NetTrace documents IP-level network traces garnered from a university's intranet, where every internal host aligns with a histogram bin to enumerate the connecting external hosts. The Social Network dataset archives the friendships of 11,000 social networking platform users, with each user profile detailing their friend count. We consolidate the attributes of these datasets in Table 1. Moreover, Figure 3 illustrates that the prevalence of smaller bins is significantly high across all these datasets. Throughout the graphical representations from Figures 3-6, the y-axis employs a logarithmic scale with a base of 10.  
(2) Utility metrics and parameter settings  
Combined popular data analysis tasks, which involve checking data distributions and answering single-value or range queries [13], utilize mean relative error (MRE) and Kullback-Leibler Divergence (KLD) as metrics to assess the utility of the released histograms.  
**(a) Single-value query.** The performance of these two methods on different single values of queries with different privacy parameters (\(\epsilon=1,0.1,0.01\)) is explored, and the mean relative error of the same value of the bins is used to verify the accuracy of their reports and is symbolized as \(MRE_{single}\).  
\[MRE_{single}=\frac{1}{|\mathbf{Q_{k}}|}\sum_{H_{j}\in\mathbf{Q_{k}}}\frac{|H _{j}-\widetilde{H}_{j}|}{max(H_{j},\delta)} \tag{34}\]  
where \(\mathbf{Q_{k}}\)= \(\{H_{j}|H_{j}=k,H_{j}\in H,k\in[min(H),max(H)]\}\), and \(\delta=1\) in this paper.  
**(b) Range query.** The performance of two methods on different ranges of queries with varying privacy parameters (\(\epsilon=1,0.1,0.01\)) is explored, with the mean relative error in the query range employed to validate the accuracy of their responses, symbolized as \(MRE_{range}\).  
\[MRE_{range}=\frac{1}{|\mathbf{Q_{i}}|}\sum_{q_{j}\in\mathbf{Q_{i}}}\frac{|q_{ j}-\widetilde{q}_{j}|}{max(q_{j},\delta)} \tag{35}\]  
where \(\mathbf{Q_{i}}\) denotes the set of all queries within scope \(i\), \(q_{j}\) represents one query within scope \(i\), \(\widetilde{q}_{j}\) is the sanitized version of \(q_{j}\), \(i\in\{1,50,100,150,200,250,300,350,400,450,500\}\), \(j\in[1,|H|-i+1]\), and \(\delta=1\) in this paper.  
**(c) Data distribution.** The KLD (Kullback-Leibler Divergence), which is used to quantify the difference between two probability distributions where a smaller KLD indicates higher similarity and a larger value denotes greater dissimilarity, is investigated for two methods employing distinct privacy parameters (\(\epsilon=1,0.1,0.01\)).  
\[KLD=\sum_{j=1}^{|H|}H_{j}log\frac{H_{j}}{\widetilde{H}_{j}}. \tag{36}\]  
Figure 3: The ratio of bins.  
Figure 4: Single-value query on four datasets. (**a**) Waitakere; (**b**) Search Log; (**c**) NetTrace; and (**d**) Social Network.  
Figure 5: Range query on four datasets. (**a**) Waitakere; (**b**) Search Log; (**c**) NetTrace; and (**d**) Social Network.