Modern AI Engineering

Lesson 10.2 · 27 min · video lesson

ANN Search: Finding Similar Vectors Without Brute Force

How can a search engine find the 10 most similar items among a billion vectors in a few milliseconds, without looking at almost any of them?

In short: Nearest neighbour search finds the stored vectors closest to a query. Doing it exactly means comparing against every vector, which is too slow at scale, so Approximate Nearest Neighbor (ANN) search uses an index to look at only a small, promising part of the data. Four families do this: trees (KD-tree), hashing (LSH), clustering (IVF) and graphs (HNSW), each trading a little accuracy (recall) for a lot of speed.

What you will learn

  • What is Nearest Neighbor Search?
  • How do we turn things into numbers (vectors)?
  • How do we measure "closeness"?
  • The naive approach and why it fails
  • What is Approximate Nearest Neighbor (ANN) Search?
  • The trade-off: speed vs accuracy
  • Approach 1: Trees (KD-Tree)
  • Approach 2: Hashing (LSH)
  • Approach 3: Clustering (IVF)
  • Approach 4: Graphs (HNSW)
  • A simple code example
  • Where ANN Search is used
  • Picking the right method

In this lesson

  1. What is nearest neighbor search?
  2. Turning things into numbers and measuring closeness
  3. The naive approach and why it fails
  4. What is ANN search, and the speed vs accuracy trade-off
  5. Approach 1 and 2: trees (KD-tree) and hashing (LSH)
  6. Approach 3 and 4: clustering (IVF) and graphs (HNSW)
  7. A simple code example
  8. Where ANN search is used
  9. Picking the right method
  10. Worked example, step by step
  11. Practice: try it yourself

Key terms in this lesson

k-NN search
Finding the k stored points closest to a query point.
ANN search
Nearest neighbour search that is allowed to be slightly inexact in exchange for large speed-ups.
Recall@k
Fraction of the true top-k neighbours that a search returned.
Curse of dimensionality
In very high dimensions distances become similar and space-cutting tricks prune poorly.
LSH
Locality-sensitive hashing: hashes built so that nearby vectors tend to share a bucket.
IVF
Inverted file index: cluster vectors with k-means and search only the nprobe nearest clusters.
HNSW
Hierarchical Navigable Small World graph: greedy search on layered neighbour graphs.

This lesson is part of the Generative AI Engineering and Complete AI Engineer tracks. See plans and pricing to open the full lesson, its video, labs and quiz, or try the free lesson first (free account needed).

← 10.1 Vector Databases: Storing and Searching Embeddings at Scale · 10.3 Semantic Search: Finding Meaning, Not Just Keywords →