Differential Private Histogram Publication with Background Knowledge
Ruixin Xue · 2024
Cluster-based differential privacy histogram release imposes a new challenge of balancing between the cluster reconstruction error and the Laplace noise error. To address this issue, we propose a differential privacy histogram publication method, namely DP-KCHP, which uses Must-Link and Cannot-Link constraints for addressing practical problems with high flexibility and adaptability. Moreover, we employ the exponential mechanism to select initial cluster centers and merge clusters to reduce noise, employing the global minimum error as the error evaluation function for histogram clustering. This approach achieves global clustering with a near-optimal error balance, effectively balancing the cluster reconstruction error and the Laplace noise error, and thereby obtaining better data utility. Experimental results demonstrate that our proposed method significantly reduces the cumulative error and enhances the availability of the published histogram data, while strictly and arguably satisfying$\epsilon-\mathbf{differential}$privacy requirements.