Nearest Neighbor Search

Nearest neighbor search is the general computational problem vector databases solve: given a query point, find the closest point(s) to it in a space, by some distance/similarity metric (typically cosine similarity for embeddings).

The Problem, Stated Simply

Given:
  - A query vector Q
  - A collection of stored vectors [V1, V2, V3, ..., Vn]

Find:
  - The k vectors from the collection closest to Q
    (by cosine similarity, or another chosen distance metric)

This is a well-studied problem in computer science generally — vector databases apply it specifically to high-dimensional embedding vectors at large scale.

Exact Nearest Neighbor — The Brute-Force Baseline

def exact_nearest_neighbors(query, all_vectors, k=5):
    scored = [(v, cosine_similarity(query, v.embedding)) for v in all_vectors]
    scored.sort(key=lambda x: x[1], reverse=True)
    return scored[:k]

# Correct, but compares against EVERY vector — O(n) per query,
# which becomes slow as n (the collection size) grows large

This guarantees the mathematically correct top-k result, but its cost grows linearly with collection size — impractical for real-time search over millions of vectors.

Why Approximate Methods Exist

At real scale, exact search becomes too slow for interactive use cases. Approximate nearest neighbor (ANN) algorithms trade a small, typically negligible chance of missing the absolute best match for dramatically better speed — this tradeoff is what makes vector databases practical at scale, and is the default approach essentially all production vector databases use.

Practical Use Case

Understanding "nearest neighbor search" as the underlying problem — separate from any specific database's implementation — helps you reason about tradeoffs (exact vs approximate, index type choices) independent of which specific vector database product you're using.

Common Mistakes

• Implementing brute-force nearest neighbor search in application code for a dataset that's grown well beyond what that approach can handle efficiently
• Not understanding that "nearest" depends entirely on the chosen distance/similarity metric — different metrics can produce different rankings for the same data

Interview Relevance

"What's the computational challenge with nearest neighbor search at scale?" — brute-force comparison scales linearly with collection size, becoming impractically slow for real-time use at millions of vectors — the core motivation for approximate methods and specialized indexes.

Practice Question

Estimate, conceptually, why searching 100 vectors vs 100 million vectors with brute-force nearest neighbor search would have a meaningfully different practical impact on a real-time application.

Related Notes

• Approximate Nearest Neighbor
• Vector Index
• Cosine Similarity