A search that compares only with centroids can enter the wrong cluster while the closest point lies in another one.
A cluster can be any shape, and its boundary is a demarcation in the ND space.
The mistake happens in this order:
- An input is compared with the centroids of C1 and C2 only. Comparing with the entire cluster is an order N operation.
- C1's centroid is close and C2's is far, so the search goes to C1.
- The nearest point in C1 is 100 meters away. A point in C2 is just 50 meters away, because many points elsewhere in C2 affect its centroid.
Vectors that come in later are assigned the same way.
The clustered index is fast, and its only problem is accuracy. The vector database builds it in the background and uses it at search time.
A relational database searches by sorting in log n. With K clusters there are K decisions at each level, K log n in all. One layer of many clusters avoids the hops at a small scale.