# Achieving differential privacy for k-nearest neighbors based outlier detection by data partitioning

arXiv: https://arxiv.org/abs/2104.07938 · HTML: https://mlsanity.com/paper/2104.07938/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 23 references that are in the map.
- First posted on arXiv 16 Apr 2021.

## Builds on (most cited first, 2 of 2)

- [Differentially Private k-Means Clustering](https://mlsanity.com/paper/1504.05998/) (2015)
- [Differentially Private Analysis of Outliers](https://mlsanity.com/paper/1507.06763/) (2015)

## Built on by (most cited first, 1 of 1)

- [Evaluating Inference-Time Defenses Against Package Hallucination in LLM-Generated Code](https://mlsanity.com/paper/2608.22652/) (2026)

## Abstract (arXiv)

When applying outlier detection in settings where data is sensitive, mechanisms which guarantee the privacy of the underlying data are needed. The k-nearest neighbors (k-NN) algorithm is a simple and one of the most effective methods for outlier detection. So far, there have been no attempts made to develop a differentially private (ε-DP) approach for k-NN based outlier detection. Existing approaches often relax the notion of ε-DP and employ other methods than k-NN. We propose a method for k-NN based outlier detection by separating the procedure into a fitting step on reference inlier data and then apply the outlier classifier to new data. We achieve ε-DP for both the fitting algorithm and the outlier classifier with respect to the reference data by partitioning the dataset into a uniform grid, which yields low global sensitivity. Our approach yields nearly optimal performance on real-world data with varying dimensions when compared to the non-private versions of k-NN.