Vector clustering partitions a large vector collection into groups of similar vectors so nearest-neighbor search can avoid exhaustive comparison. section 2.2.1
A k-means index follows this offline procedure:
- Initialize k centroids randomly. section 2.2.1
- Assign every vector to its nearest centroid, recompute each centroid as the mean of its assigned vectors, and repeat until convergence. section 2.2.1
- At query time, compare the query with centroids first, then search only the selected cluster or clusters for nearest neighbors. section 2.2.1
Million-vector search
A query can narrow a million-vector search to roughly a thousand candidates by selecting a relevant cluster before exact neighbor search, trading exhaustive coverage for speed. section 2.2.1
Figure 2.3 FAISS's Two-Stage Search Strategy.

Shows FAISS's clustered, two-stage search strategy. section 2.2.1
