Blog
-
The recall-latency curve
Every index parameter moves you along one curve with diminishing returns. How to measure recall honestly, and why distance concentration sets its ceiling.
-
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.
-
Quantization: trading memory for recall
Scalar, product and binary quantization compress vectors by discarding precision. What each one throws away, and why reranking recovers most of it.
-
How graph indexes search
Greedy traversal over a proximity graph, why it gets stuck in local minima, and how layers and connectivity fix it — the mechanism behind HNSW.
-
Distance metrics and when each is right
Cosine, dot product and Euclidean measure different things — except when they don't. What each compares, and why normalization collapses all three.
-
Maximum inner product is not nearest neighbour
Inner product isn't a metric, so the pruning every index relies on stops working. What breaks, the reduction that fixes it, and why normalising is easier.
-
What "approximate" is allowed to mean
ANN has three quite different notions of approximation: a proven ratio, a probability, and no guarantee at all. Which one your index gives you, and why.
-
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.
-
How a filter fights the index
A metadata predicate isn't a cheap extra condition — it breaks the assumption each index family is built on. Why graphs strand and cluster scans shrug.
-
Why product quantization wants a rotation first
Splitting a vector into slices assumes information is spread evenly across them. It isn't. What a learned rotation fixes, and why it's free per query.
-
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.
-
Hubness: the vectors that turn up in everyone's results
In high dimensions a few points become the nearest neighbour of implausibly many queries. Why the k-NN relation is asymmetric, and what it does to a graph.
-
What the layers in a hierarchical graph buy
A flat proximity graph already navigates. Why stacking sparse layers on top changes the hop count, and where the skip-list analogy breaks down.
-
The neighbour list you want isn't the nearest one
Connecting each vector to its k closest neighbours builds a graph that traps every search. Why diversified pruning is the fix, and what it approximates.
-
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.
-
The curse of dimensionality, precisely
High dimensions don't break similarity search by magic. Distance concentration, boundary volume and intrinsic dimension, stated carefully enough to use.
-
What similarity means as geometry
Similarity search works by turning meaning into position. What a vector space provides, which properties indexes depend on, and what the map loses.