# Neighborhood Stability as a Measure of Nearest Neighbor Searchability

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 46 references that are in the map.
- First posted on arXiv 18 Feb 2026.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ReSSL: Relational Self-Supervised Learning with Weak Augmentation](https://mlsanity.com/paper/2107.09282/) (2021)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [To Cluster, or Not to Cluster: An Analysis of Clusterability Methods](https://mlsanity.com/paper/1808.08317/) (2018)
- [Deep Clustering with Features from Self-Supervised Pretraining](https://mlsanity.com/paper/2207.13364/) (2022)
- [Bridging Dense and Sparse Maximum Inner Product Search](https://mlsanity.com/paper/2309.09013/) (2023)
- [Axioms for graph clustering quality functions](https://mlsanity.com/paper/1308.3383/) (2013)
- [A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2404.11731/) (2024)
- [Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search](https://mlsanity.com/paper/2403.01797/) (2024)
- [Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search](https://mlsanity.com/paper/2405.12207/) (2024)
- [An Axiomatic Definition of Hierarchical Clustering](https://mlsanity.com/paper/2407.03574/) (2024)
- [Learning Cluster Representatives for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2412.05921/) (2024)

## Abstract (arXiv)

Clustering-based Approximate Nearest Neighbor Search (ANNS) organizes a set of points into partitions, and searches only a few of them to find the nearest neighbors of a query. Despite its popularity, there are virtually no analytical tools to determine the suitability of clustering-based ANNS for a given dataset -- what we call "searchability." To address that gap, we present two measures for flat clusterings of high-dimensional points in Euclidean space. First is Clustering-Neighborhood Stability Measure (clustering-NSM), an internal measure of clustering quality -- a function of a clustering of a dataset -- that we show to be predictive of ANNS accuracy. The second, Point-Neighborhood Stability Measure (point-NSM), is a measure of clusterability -- a function of the dataset itself -- that is predictive of clustering-NSM. The two together allow us to determine whether a dataset is searchable by clustering-based ANNS given only the data points. Importantly, both are functions of nearest neighbor relationships between points, not distances, making them applicable to various distance functions including inner product.