Locating a Small Cluster Privately
This addresses privacy concerns in data exploration, clustering, and outlier removal for data analysts, but appears incremental as it builds on existing differential privacy frameworks.
The paper tackles the problem of locating a small cluster of points with differential privacy, resulting in an algorithm that relaxes the requirements of the sample and aggregate technique for compiling non-private analyses into private ones.
We present a new algorithm for locating a small cluster of points with differential privacy [Dwork, McSherry, Nissim, and Smith, 2006]. Our algorithm has implications to private data exploration, clustering, and removal of outliers. Furthermore, we use it to significantly relax the requirements of the sample and aggregate technique [Nissim, Raskhodnikova, and Smith, 2007], which allows compiling of "off the shelf" (non-private) analyses into analyses that preserve differential privacy.