Senior interview question
Exact k-NN is too slow at your scale. What do you give up with an ANN index, and how do you choose one?
Model answer
Recall: approximate search looks at only some vectors, so a true neighbour can be missed.
Scroll sideways to see the whole diagram
Approximate nearest-neighbour (ANN) indexes organise vectors so a query only looks at some of them. IVF uses clusters.
Text version
- Approximate nearest-neighbour (ANN) indexes organise vectors so a query only looks at some of them. IVF uses clusters.
- Each vector is filed under its nearest cluster centre. AI Engineering notes clusters are typically sized to hold 100 to 10,000 vectors on average.
- A query compares itself with the centroids, then only with the vectors in the closest clusters.
- That's the trade every ANN index makes, whether clusters (IVF), graphs (HNSW), hashing (LSH), trees (Annoy) or compressed vectors (product quantization): speed for some recall.
Indexes differ in how they trade: IVF searches the nearest clusters; HNSW walks a graph, accurate and fast to query but slow and memory-hungry to build; LSH hashes, cheap to build but less accurate. Compare on recall, queries per second, build time and index size, and weigh build time heavily if the data changes often.
Practise the rest
6 Retrieval algorithms questions, 492 in all, each with a model answer. Free.