  WaveCluster is an important family of grid-based clustering algorithms that
are capable of finding clusters of arbitrary shapes. In this paper, we
investigate techniques to perform WaveCluster while ensuring differential
privacy. Our goal is to develop a general technique for achieving differential
privacy on WaveCluster that accommodates different wavelet transforms. We show
that straightforward techniques based on synthetic data generation and
introduction of random noise when quantizing the data, though generally
preserving the distribution of data, often introduce too much noise to preserve
useful clusters. We then propose two optimized techniques, PrivTHR and
PrivTHREM, which can significantly reduce data distortion during two key steps
of WaveCluster: the quantization step and the significant grid identification
step. We conduct extensive experiments based on four datasets that are
particularly interesting in the context of clustering, and show that PrivTHR
and PrivTHREM achieve high utility when privacy budgets are properly allocated.
