  Differential privacy is a strong notion for protecting individual privacy in
privacy preserving data analysis or publishing. In this paper, we study the
problem of differentially private histogram release for random workloads. We
study two multidimensional partitioning strategies including: 1) a baseline
cell-based partitioning strategy for releasing an equi-width cell histogram,
and 2) an innovative 2-phase kd-tree based partitioning strategy for releasing
a v-optimal histogram. We formally analyze the utility of the released
histograms and quantify the errors for answering linear queries such as
counting queries. We formally characterize the property of the input data that
will guarantee the optimality of the algorithm. Finally, we implement and
experimentally evaluate several applications using the released histograms,
including counting queries, classification, and blocking for record linkage and
show the benefit of our approach.
