liveBook · Manning

K-means clustering

As explained in Retrieval Augmented Generation, The Foundational Ideas

K-means is a clustering algorithm that partitions data points into a fixed number of clusters by assigning each point to one cluster.

K-means partitions vectors into a fixed number of similarity-based clusters, turning exhaustive nearest-neighbor search into a smaller staged search. section 2.2.1

The clustering procedure repeats four steps:

FAISS search

FAISS compares a query with cluster centroids first, then searches the selected cluster rather than every vector. This turns million-vector searches into thousand-vector searches. section 2.2.1

Figure 2.3 FAISS's Two-Stage Search Strategy.

Shows FAISS’s two-stage strategy: route a query through centroids before searching vectors within the selected cluster. section 2.2.1

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains initialization, assignment, averaging, convergence, and query routing, but defers implementation details and compression.
Examples
Uses FAISS to illustrate centroid routing and restricted vector search for million-vector collections.
What it assumes
Assumes vector representations and nearest-neighbor search while teaching centroid assignment and iterative averaging explicitly.
What you can do after
Apply it via FAISS to build clustered approximate nearest-neighbor indexes and reduce query-time comparisons.
How it connects
Connects k-means with approximate nearest neighbors, vector compression, GPU acceleration, and centroids.

Also explained in

Compare how 12 books explain K-means clustering →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Retrieval Augmented Generation, The Foundational Ideas. The section links point to the parts of the book it draws on.