Neighborhood Stability as a Measure of Nearest Neighbor Searchability

Thomas Vecchiato; Sebastian Bruch

cs.LGFeb 18, 2026

Neighborhood Stability as a Measure of Nearest Neighbor Searchability

Authors: Thomas Vecchiato, Sebastian Bruch

Organizations: University of Copenhagen, Copenhagen, Denmark · Northeastern University, Boston, MA, USA

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Spearman’s correlation coefficient between clustering quality and top- $k$ Anns accuracy. For Db , we present the negated coefficient because smaller values indicate better clustering quality.

Panel of Figure 2 — Figure 2: Spearman’s correlation coefficient between clustering quality and external evaluation metrics. For Db , the coefficient is negated because a smaller index indicates better clustering quality.

Panel of Figure 3 — Figure 3: Point- Nsm distributions for various datasets.

	Standard KMeans		Spherical KMeans
point- Nsm radius	Mean	$0.1$ -quantile	Mean	$0.1$ -quantile
$r=1024$	0.81	0.86	0.79	0.85
$r=2048$	0.82	0.85	0.82	0.85
$r=4096$	0.74	0.81	0.74	0.81
$r=8192$	0.76	0.78	0.76	0.78
Combined	0.79	0.83	0.82	0.85

Table 1: Spearman’s correlation coefficient between statistics from point- Nsm distributions and the clustering- Nsm for clusterings obtained from standard and spherical KMeans . All correlations are significant (

p

-value

<0.001

). Last row aggregates statistics and clustering- Nsm for all values of

r

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Spearman’s correlation coefficient between clustering quality and top- $k$ Ann accuracy where the number of clusters is $\frac{1}{4}\sqrt{\lvert\mathcal{X}\rvert}$ . For Db , we present the negated coefficient because smaller values indicate better clustering quality.

Panel of Figure 5 — Figure 5: Spearman’s correlation coefficient between clustering quality and top- $k$ Ann accuracy where the number of clusters is $\frac{1}{2}\sqrt{\lvert\mathcal{X}\rvert}$ . For Db , we present the negated coefficient because smaller values indicate better clustering quality.

Panel of Figure 6 — Figure 6: Spearman’s correlation coefficient between clustering quality and top- $5$ Anns accuracy, as a function of $\ell$ with values between $1$ and $5\%$ of the total number of clusters. The figures also include, for each of the eight clustering algorithms, recall (green curves) versus $\ell$ for reference. For Db , we present the negated coefficient because smaller values indicate better clustering quality.

Panel of Figure 7 — Figure 7: Figure 6 continued.

Panel of Figure 8 — Figure 8: Spearman’s correlation coefficient between clustering quality and top- $k$ Ann accuracy. For Db , we present the negated coefficient because smaller values indicate better clustering quality. For clustering- Nsm , we use approximate nearest neighbors to compute each set’s stability.

Panel of Figure 9 — Figure 9: Spearman’s correlation coefficient between clustering quality and external evaluation metrics for the task of image clustering. For Db , the coefficient is negated because a smaller index indicates better clustering quality. For clustering- Nsm , we use approximate nearest neighbors to compute each set’s stability.

Panel of Figure 10 — Figure 10: Point- Nsm distributions computed from all points within the various datasets.

	Standard KMeans		Spherical KMeans
point- Nsm radius	Mean	$0.1$ -quantile	Mean	$0.1$ -quantile
$r=1024$	0.81	0.86	0.79	0.85
$r=2048$	0.82	0.85	0.82	0.85
$r=4096$	0.74	0.81	0.74	0.81
$r=8192$	0.76	0.78	0.76	0.78
Combined	0.79	0.83	0.82	0.85

Appendix

Table 2: Spearman’s correlation coefficient between statistics from point- Nsm distributions (computed from full datasets) and the clustering- Nsm for clusterings obtained from standard and spherical KMeans . All correlations are significant (

p

-value

<0.001

). Last row aggregates statistics and clustering- Nsm for all values of

r

. These coefficients are exactly the same as those reported in Table 1 .

$r=256$	$r=512$	$r=1024$	Combined
$0.83$	$0.84$	$0.84$	$0.83$

Appendix

Table 3: Spearman’s correlation coefficient between the

0.1

-quantile of point- Nsm distributions and Hnsw ’s accuracy at

k=1

for each

r

separately. The last column shows the correlation between point- Nsm and Anns accuracy for all values of

r

Approximate Nearest Neighbor Search

Approximate nearest neighbor search finds close vectors without exhaustive comparisons, enabling scalable retrieval in high-dimensional datasets.

See all 42 papers

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search
Jul 20, 2026Zheqi Shen, Jingbo Su, Zijin Wan +2Exact Nearest Neighbor Search Graph-Based Retrieval
UC Riverside Riverside CA, USA · W&M Williamsburg VA, USA
ANN Search: Recall What Matters
Jun 3, 2026Dimitris Dimitropoulos, Nikos MamoulisIR Evaluation Approximate Nearest Neighbor Search
University of Ioannina & Archimedes, Athena RC · Ioannina, Greece
Panorama: Fast-Track Nearest Neighbors
Oct 1, 2025Vansh Ramani, Alexis Schlomer, Akash Nayar +3Product Quantization Approximate Nearest Neighbor Search
IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1

Jul 20, 2026J/K move · Enter open · S save

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search

Zheqi Shen, Jingbo Su, Zijin Wan, Yan Gu+1

UC Riverside Riverside CA, USA · W&M Williamsburg VA, USA

Exact Nearest Neighbor Search Graph-Based Retrieval Approximate Nearest Neighbor Search

Open paper AskPDF arXiv

Approximate Nearest Neighbor Search (ANNS) plays a pivotal role in modern deep learning pipelines. Recently, many ANNS systems have been proposed to either provide broad functionality or reach high performance. However, it is yet difficult to achieve both with minimal programming efforts. We propose ANNLib to address the gap. ANNLib is a library that provides a programming framework for achieving high performance and flexible functionality in ANNS systems, based on popular graph-based ANNS algorithms. We carefully decouple and independently optimize both the algorithm and the data structure components of an ANNS system. In addition, we integrate state-of-the-art algorithms and data structures into ANNLib as modules, along with our new designs. Users can choose combinations of components to implement sophisticated settings with high performance, such as filter search, fully dynamic updates, and historical queries on snapshots. Our experiments show that our new solution provides a simple interface for various applications and achieves comparable or even better performance than previous work, specifically for each application.

Abstract

Approximate Nearest Neighbor Search

Explore similar work

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search

ANN Search: Recall What Matters

Panorama: Fast-Track Nearest Neighbors