Explain k-nearest-neighbor search and the difference between exact and approximate nearest neighbor search.

beginner

← All Embeddings & Vector Databases questions

Re-explain

k-nearest-neighbor search, or k-NN, takes a query vector and returns the k stored vectors closest to it under a distance metric. It ranks by closeness, it does not look for an exact match.

Exact search compares the query against every stored vector. It always returns the true top k, but the work grows linearly with the collection size.

scores = corpus @ query          # touches every vector, every query
top_k = np.argsort(-scores)[:k]

Approximate nearest neighbor (ANN) search skips most of the collection by using an index built ahead of time. It is much faster, but it can miss some true neighbors.

Aspect	Exact	Approximate
Result	always the true top k	usually close to it
Query cost	scales with collection size	roughly sub-linear
Extra memory	none	index structure
Tuning	nothing to tune	speed versus recall

Exact search is fine for small collections. Once you reach millions of vectors, ANN is the practical default.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Embeddings & Vector Databases One question at a time. Answer out loud, get graded, see what you missed.

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

Pick one ANN index, say HNSW. How does it avoid comparing the query to every vector? A strong answer describes a layered proximity graph, a greedy walk from a coarse top layer down, and what M and ef control.
How would you measure how many true neighbors your ANN index misses? Use exact search on sample queries as ground truth, then report recall@k as the share of the true top k the ANN returns.
How would you tune an ANN index to hit a recall target inside a latency budget? Name the query-time knob, like efSearch or nprobe, sweep it while measuring recall@k and p99 latency, and pick the cheapest setting that meets the target.
When would you still choose exact search in production, even with a large collection? Think small or heavily filtered subsets, cases that need guaranteed results, offline ground truth, and GPU brute force at modest query rates.
Why do metadata filters cause trouble for an ANN index but not for exact search? Contrast pre- and post-filtering. Post-filtering can return fewer than k, and a selective filter can break graph traversal or leave probed clusters empty.

What you can say

k-nearest-neighbor search takes a query vector and returns the k stored vectors closest to it under a distance metric, so it ranks by closeness rather than looking for an exact match.
Exact search compares the query against every stored vector, so it always returns the true top k, but the cost grows linearly with the size of the collection.
In code that's one dot product of the query against the whole corpus and then a sort, and it touches every vector on every query.
Approximate nearest neighbor search builds an index ahead of time, so each query only looks at a small part of the collection and the cost is roughly sub-linear.
The price is extra memory for the index and some missed true neighbors, so you end up tuning speed against recall.
I'd use exact search for small collections, but once you're at millions of vectors, ANN is the practical default.

Weak answers to avoid

Treats k-NN as an exact-match lookup k-NN ranks by distance and returns k results even if none are close. Say it returns the k closest vectors under a metric, not matches.
Confuses k-NN search with the k-NN classifier The classifier votes on neighbor labels. This question is about retrieval, so talk about returning the top k vectors and what each query costs.
Says ANN is just faster, with no downside ANN can miss true neighbors and needs memory for its index. Name recall as the price and say you tune speed against it.
Can't say when exact search is good enough An index on a small collection adds memory and tuning for nothing. Say brute force is fine there and ANN becomes the default at millions of vectors.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Embeddings & Vector Databases cheatsheet.

← Back to all Embeddings & Vector Databases questions

Pro · $10/mo

49 of 56 Embeddings & Vector Databases answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →