A New Privacy-Preserving Distributed k-Clustering Algorithm
Geetha Jagannathan, Krishnan Pillaipakkamnatt, Rebecca N. Wright · 2006
We present a simple I/O-efficient k-clustering algorithm that was designed with the goal of enabling a privacy-preserving version of the algorithm. Our experiments show that this algorithm produces cluster centers that are, on average, more accurate than the ones produced by the well known iterative A;-means algorithm. We use our new algorithm as the basis for a communication-efficient privacy-preserving k-clustering protocol for databases that are horizontally partitioned between two parties. Unlike existing privacy-preserving protocols based on the A;-means algorithm, this protocol does not reveal intermediate candidate cluster centers.