approximate nearest neighbour search
Vector search that skips most comparisons using an index, trading a little recall for much faster queries.
In more detail
HNSW graphs and inverted-file indexes are the common kinds. Their settings, such as nprobe or ef search, move the trade-off, so measure recall against exact search on your own queries before trusting the defaults.
Related terms
- HNSW — An approximate vector index built as a layered graph of links between nearby vectors, searched by walking from a coarse top layer down to a dense bottom one.
- IVF index — An approximate vector index that clusters vectors into cells and searches only the cells whose centres are closest to the query.
- recall at k — The share of the relevant passages for a query that appear in the top k results.
Taught in
- Vector Indexes And Databases — AI Engineering: LLM Apps, RAG & Agents
References
- FAISS wiki: Faiss indexes (IndexIVFFlat, nprobe, IndexHNSWFlat)
- Malkov and Yashunin: Hierarchical Navigable Small World graphs (arXiv 1603.09320)