Date Added: Aug 2010
Differential privacy is a strong notion for protecting individual privacy in privacy preserving data analysis or publishing. In this paper, the authors study the problem of differentially private histogram release based on an interactive differential privacy interface. They propose two multidimensional partitioning strategies including a baseline cell-based partitioning and an innovative kd-tree based partitioning. In addition to providing formal proofs for differential privacy and usefulness guarantees for linear distributive queries, they also present a set of experimental results and demonstrate the feasibility and performance of their method.