A clustered index groups the vectors into clusters beforehand, so that a search is compared with one representative of each cluster and not with every vector.
The clusters are created before any search arrives, as an offline process, because the embedding space does not change.
The example has 14 vectors, and a scan of all of them takes 14 comparisons. With clusters the search runs like this:
- One vector is picked at random from each cluster as the representative of the whole group.
- The search vector is compared with all the representatives, and the closest one is chosen.
- Inside that cluster the search vector is compared with the remaining three vectors.
The search takes 5 plus 3, 8 comparisons against the original 14. The savings grow as the clusters grow, and K-means clustering makes the clusters.
A cluster of 50 thousand points is split into 50 clusters of a thousand points each, and those into clusters of a hundred. This is similar to an address: country, state, pin code, landmark, and in the end the coordinates.