# Statistical Analysis of Nearest Neighbor Methods for Anomaly Detection

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jul 2019.

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

- [Out-of-Distribution Detection with Deep Nearest Neighbors](https://mlsanity.com/paper/2204.06507/) (2022)
- [Revisiting Mahalanobis Distance for Transformer-Based Out-of-Domain Detection](https://mlsanity.com/paper/2101.03778/) (2021)
- [A Survey on Out-of-Distribution Detection in NLP](https://mlsanity.com/paper/2305.03236/) (2023)
- [GOLD: Improving Out-of-Scope Detection in Dialogues using Data Augmentation](https://mlsanity.com/paper/2109.03079/) (2021)
- [TPU-KNN: K Nearest Neighbor Search at Peak FLOP/s](https://mlsanity.com/paper/2206.14286/) (2022)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [Enhancing Unsupervised Anomaly Detection with Score-Guided Network](https://mlsanity.com/paper/2109.04684/) (2021)
- [On the Detection of Reviewer-Author Collusion Rings From Paper Bidding](https://mlsanity.com/paper/2402.07860/) (2024)
- [Data Distribution Valuation](https://mlsanity.com/paper/2410.04386/) (2024)
- [Semi-Supervised Object Detection with Uncurated Unlabeled Data for Remote Sensing Images](https://mlsanity.com/paper/2310.05498/) (2023)
- [Outlier Synthesis via Hamiltonian Monte Carlo for Out-of-Distribution Detection](https://mlsanity.com/paper/2501.16718/) (2025)
- [We Need to Rethink Benchmarking in Anomaly Detection](https://mlsanity.com/paper/2507.15584/) (2025)
- [k-NNN: Nearest Neighbors of Neighbors for Anomaly Detection](https://mlsanity.com/paper/2305.17695/) (2023)
- [Understanding the limitations of self-supervised learning for tabular anomaly detection](https://mlsanity.com/paper/2309.08374/) (2023)
- [Unsupervised Surrogate Anomaly Detection](https://mlsanity.com/paper/2504.20733/) (2025)
- [Debunking Free Fusion Myth: Online Multi-view Anomaly Detection with Disentangled Product-of-Experts Modeling](https://mlsanity.com/paper/2310.18728/) (2023)
- [On the True Distribution Approximation of Minimum Bayes-Risk Decoding](https://mlsanity.com/paper/2404.00752/) (2024)
- [CKNN: Cleansed k-Nearest Neighbor for Unsupervised Video Anomaly Detection](https://mlsanity.com/paper/2408.03014/) (2024)
- [Improving Novelty Detection using the Reconstructions of Nearest Neighbours](https://mlsanity.com/paper/2111.06150/) (2021)
- [Model-free feature selection to facilitate automatic discovery of divergent subgroups in tabular data](https://mlsanity.com/paper/2203.04386/) (2022)
- [CoLaDa: A Collaborative Label Denoising Framework for Cross-lingual Named Entity Recognition](https://mlsanity.com/paper/2305.14913/) (2023)
- [Detecting and Learning Out-of-Distribution Data in the Open world: Algorithm and Theory](https://mlsanity.com/paper/2310.06221/) (2023)
- [Exploring the Impact of Outlier Variability on Anomaly Detection Evaluation Metrics](https://mlsanity.com/paper/2409.15986/) (2024)
- [GPU-Accelerated ANNS: Quantized for Speed, Built for Change](https://mlsanity.com/paper/2601.07048/) (2026)
- [Sparsity-based Feature Selection for Anomalous Subgroup Discovery](https://mlsanity.com/paper/2201.02008/) (2022)
- [UniOD: A Universal Model for Outlier Detection across Diverse Domains](https://mlsanity.com/paper/2507.06624/) (2025)
- [Transformer Based Machine Fault Detection From Audio Input](https://mlsanity.com/paper/2604.12733/) (2026)
- [Guided Discovery of New Behaviors using Diffusion Policies](https://mlsanity.com/paper/2606.08743/) (2026)
- [Streaming algorithms for robust max-min diversification](https://mlsanity.com/paper/2610.01456/) (2026)

## Abstract (arXiv)

Nearest-neighbor (NN) procedures are well studied and widely used in both supervised and unsupervised learning problems. In this paper we are concerned with investigating the performance of NN-based methods for anomaly detection. We first show through extensive simulations that NN methods compare favorably to some of the other state-of-the-art algorithms for anomaly detection based on a set of benchmark synthetic datasets. We further consider the performance of NN methods on real datasets, and relate it to the dimensionality of the problem. Next, we analyze the theoretical properties of NN-methods for anomaly detection by studying a more general quantity called distance-to-measure (DTM), originally developed in the literature on robust geometric and topological inference. We provide finite-sample uniform guarantees for the empirical DTM and use them to derive misclassification rates for anomalous observations under various settings. In our analysis we rely on Huber's contamination model and formulate mild geometric regularity assumptions on the underlying distribution of the data.