Tagged “cluster-index”
-
How cluster indexes search
Partition the space in advance, then only search the partitions near your query. Why boundary effects cost recall and what probing more of them buys.
-
Composite indexes: coarse filter, exact rescore
Nearly every large-scale index is the same two-stage pattern with different parts. What each stage must guarantee, and how the pattern nests inside itself.
-
Residual quantization: compressing what the centroid missed
Quantizing a vector's offset from its cluster centroid, rather than the vector, shrinks the error for free. Why it works, and what it couples together.
-
Voronoi cells and the cost of a query near a boundary
A cluster index cuts space into Voronoi cells. Why almost every query lands near an edge, what probing more cells recovers, and why overlap beats probing.
-
How k-means places the centroids you probe
A cluster index is trained by k-means, and its objective isn't your recall. What the algorithm optimises, and why initialisation decides the partition.
-
Locality-sensitive hashing and the amplification trick
A hash that collides for nearby points turns search into a lookup. How AND/OR amplification sharpens a weak signal, and why graphs displaced it anyway.
-
Why space-partitioning trees fail on embeddings
k-d trees give exact nearest neighbours in logarithmic time in low dimensions. What backtracking does to that guarantee, and why the field went elsewhere.