mlsanityData to 7 Oct 2026

Neighborhood Stability as a Measure of Nearest Neighbor Searchability

arXiv 2602.16673 ↗First posted 18 Feb 2026cs.LG cs.IRcited by 0

Not on the map. Why?

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.

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

Builds on

17 of 46 references.

References · 17

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,456
  3. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  4. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  5. 2016MS MARCO: A Human Generated MAchine Reading COmprehension Datasetcited by 1,591
  6. 2016Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphscited by 853
  7. 2021ReSSL: Relational Self-Supervised Learning with Weak Augmentationcited by 83
  8. 2022Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Searchcited by 45
  9. 2018To Cluster, or Not to Cluster: An Analysis of Clusterability Methodscited by 17
  10. 2022Deep Clustering with Features from Self-Supervised Pretrainingcited by 14
  11. 2023Bridging Dense and Sparse Maximum Inner Product Searchcited by 8
  12. 2013Axioms for graph clustering quality functionscited by 6
5 more
  1. 2024A Learning-to-Rank Formulation of Clustering-Based Approximate Nearest Neighbor Searchcited by 6
  2. 2024Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Searchcited by 4
  3. 2024Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Searchcited by 3
  4. 2024An Axiomatic Definition of Hierarchical Clusteringcited by 3
  5. 2024Learning Cluster Representatives for Approximate Nearest Neighbor Searchcited by 1

Built on by

Not cited yet.