Module 4: Proximity Search

2. kNN Conceptually: The K Nearest Neighbors

Next →

Overview

The kNN (k-Nearest Neighbors) algorithm is the conceptual foundation of all proximity search: given N vectors, find the K closest to the query. Here you'll see how it works conceptually and why exhaustive search (checking every vector) doesn't scale.

What is kNN?

Definition: Given a query vector, find the K nearest vectors (neighbors) in a dataset.

Example:

Dataset: 1 million vectors (documents)
Query: "domestic animal"
K = 10

Result: The 10 documents with the highest cosine similarity

Exhaustive search (brute force)

The algorithm:

1. For every vector in the dataset:
     Compute similarity(query, vector)
2. Sort all the vectors by similarity
3. Return the top-K

Example with 5 vectors:

Query: [2, 3]

Vectors:
A = [2, 3]   → similarity = 1.00
B = [3, 4]   → similarity = 0.99
C = [1, 5]   → similarity = 0.85
D = [9, 1]   → similarity = 0.35
E = [0, -2]  → similarity = -0.12

Top-3: A, B, C ✅

The complexity of exhaustive search

Operations per query:

  • N similarity computations (N = the size of the dataset)
  • Sorting N results

Complexity: O(N × d) where d = dimensionality (1536 for OpenAI)

Scalability problems:

DatasetComputations per queryTime (estimated)
1,000 vectors1,000~1ms ✅
100,000100,000~100ms ⚠️
1M1,000,000~1s ❌
10M10,000,000~10s ❌
100M100,000,000~100s ❌

Conclusion: Exhaustive search does NOT scale to millions of vectors.

Why doesn't it scale?

Problem 1: Too many computations

With 10M vectors and 1536 dimensions:

10M × 1536 = 15.36 billion operations per query

Even on fast hardware, that takes seconds.

Problem 2: Unacceptable latency

In production:

  • A search must respond in < 100ms (ideally < 50ms)
  • Exhaustive search with 10M vectors → 10+ seconds ❌

The solution: Approximate search

The idea: Don't check EVERY vector. Use a smart data structure that lets you "jump" to the relevant regions of the space.

Trade-off:

  • ✅ Much faster (1000x-10000x)
  • ⚠️ It can miss some results (~1-5% error)

Why is that acceptable?

If the "true" top-10 is:

1. Doc A (score 0.95)
2. Doc B (score 0.94)
3. Doc C (score 0.93)
...
10. Doc J (score 0.85)

And the approximate index returns:

1. Doc A (score 0.95) ✅
2. Doc B (score 0.94) ✅
3. Doc D (score 0.92) ← Doc C was missed, but D is nearly as good
...
10. Doc K (score 0.84) ← Doc J was missed, but K is nearly as good

Users wouldn't notice the difference (Doc D is almost as good as Doc C).

Types of approximate indexes

1. HNSW (Hierarchical Navigable Small World)

  • A hierarchical graph
  • Very fast, ~99% precision
  • More memory

2. IVF (Inverted File Index)

  • Clustering + searching within clusters
  • Fast, ~95-98% precision
  • Less memory

3. LSH (Locality-Sensitive Hashing)

  • Special hashing
  • Very fast, lower precision
  • Less used in modern production

You'll see each one in detail in the following capsules.

Summary

Key points:

  • kNN: Finding the K nearest neighbors
  • Exhaustive: O(N × d) → doesn't scale to millions
  • Approximate: 1000x faster with ~1-5% error
  • An acceptable trade-off: Speed > perfection for UX

Next capsule: 03-search-indexes.md — Types of indexes, comparison.

← Previous1. Module Introduction: Proximity Search - Finding Nearest NeighborsNext →3. Search Indexes: Exact vs Approximate