  We advance the approach initiated by Chawla et al. for sanitizing (census)
data so as to preserve the privacy of respondents while simultaneously
extracting "useful" statistical information. First, we extend the scope of
their techniques to a broad and rich class of distributions, specifically,
mixtures of highdimensional balls, spheres, Gaussians, and other "nice"
distributions. Second, we randomize the histogram constructions to preserve
spatial characteristics of the data, allowing us to approximate various
quantities of interest, e.g., cost of the minimum spanning tree on the data, in
a privacy-preserving fashion.
