1. Module Introduction: Proximity Search - Finding Nearest Neighbors

Overview

This is the module where you understand how to search for nearby vectors efficiently. So far you know what vectors are (Module 1), how they form spaces (Module 2), and how to measure closeness (Module 3). Now you'll see how to find the K nearest neighbors (kNN) without checking EVERY vector (which is inefficient across millions of documents).

This module is the bridge between theory and practice: you'll see conceptual algorithms (kNN, HNSW, IVF) without implementing code. You'll understand why vector databases (Pinecone, Weaviate) use specialized indexes and what trade-offs they carry.

Approach: 60% conceptual algorithmic theory, 40% diagrams and comparisons. There's NO code, but there is simple pseudocode and diagrams of data structures.

Estimated time: 2-2.5 hours

---

Module Objectives

By completing this module, you'll be able to:

1. Explain the search problem (exhaustive vs approximate search)
2. Understand kNN conceptually (the K nearest neighbors)
3. Compare indexes: Brute force, HNSW, IVF, LSH
4. Explain HNSW (hierarchical navigable graphs)
5. Explain IVF (clustering + searching within clusters)
6. Decide which index to use (trade-offs: speed vs precision)
7. Reason about scalability (millions of vectors)

Key competency gained: You'll understand that vector databases don't do "exhaustive search" (slow), but instead use approximate indexes (fast, with ~99% precision).

---

Module roadmap: the 7 capsules

#	Capsule	What you'll see	Duration
01	Module introduction	The search problem, an overview of indexes	15 min
02	kNN conceptually	The K nearest neighbors, exhaustive search	20 min
03	Search indexes	Types: exact vs approximate, trade-offs	20 min
04	HNSW and graphs	The hierarchical navigable graph (Pinecone, Weaviate)	30 min
05	IVF and clustering	The Inverted File Index (searching by clusters)	25 min
06	Trade-offs and decisions	When to use each index	20 min
07	Capstone exercise	Designing a search strategy	30 min

Total: ~2.5 hours

---

The central problem

The scenario:

You have: 10 million documents (10M vectors of 1536D)
Query: "domestic animal" → the query vector
Goal: Find the 10 most relevant documents (top-10)

The problem: How do you find the 10 closest without computing the distance to ALL 10M?

---

The solutions

1. Exhaustive search (brute force)

For every vector in the database:
  Compute similarity(query, vector)
Sort by similarity
Return the top-10

Advantage: ✅ It always finds the EXACT top-10

Disadvantage: ❌ Very slow (10M computations per query)

---

2. Approximate search (with indexes)

Use a specialized data structure (an index)
Search ONLY within the relevant region of the space
Return ~the top-10 (approximately correct)

Advantage: ✅ Very fast (1000x-10000x faster)

Disadvantage: ⚠️ It can miss some results (~1-5% error)

---

The main indexes

HNSW (Hierarchical Navigable Small World)

What it is: A multi-layer graph where each node is a vector. You navigate the graph by hopping from nearby node to nearby node.

Used by: Pinecone, Weaviate, Qdrant

Trade-off: Very fast, ~99% precision, uses a lot of memory

---

IVF (Inverted File Index)

What it is: Cluster the vectors into groups (e.g. 1000 clusters). Search only within the clusters closest to the query.

Used by: FAISS (Facebook), some Weaviate modes

Trade-off: Fast, ~95-98% precision, less memory than HNSW

---

LSH (Locality-Sensitive Hashing)

What it is: Hash the vectors so that similar vectors get similar hashes. Search only within the same buckets.

Used by: Less common in modern production

Trade-off: Very fast, lower precision than HNSW/IVF

---

Why approximate is acceptable

Question: Why accept ~1-5% error (missing some correct results)?

Answer:

1. The speed gain is enormous: 1000x-10000x faster

2. The "missed" results are usually marginal:

   • Result #11 (missed) vs result #10 (found) → nearly identical similarity
   • The user wouldn't notice the difference

3. In production, speed > perfection:

   • Better to return an answer in 10ms with 99% precision
   • Than to return it in 10s with 100% precision

---

Connection to the previous modules

Module 1: Individual vectors
Module 2: Vector spaces
Module 3: Measuring closeness (cosine)
Module 4: Searching for nearby vectors efficiently ← You are here

The logical flow:

1. You have vectors ✅
2. In a structured space ✅
3. With a closeness metric ✅
4. How do you find nearest neighbors among millions of vectors? ← Now

---

What you will NOT see in this module

To keep the focus conceptual:

• ❌ Implementation code: You won't implement HNSW or IVF
• ❌ Formal mathematics: You won't see O(log n) complexity proofs
• ❌ Low-level optimizations: You won't see SIMD, GPU, quantization (that's advanced)

This is 100% conceptual: Algorithms, data structures, trade-offs, decisions.

---

Success criteria

You'll know you completed the module if you can:

1. ✅ Explain the problem of searching across millions of vectors
2. ✅ Describe how HNSW works (a hierarchical navigable graph)
3. ✅ Describe how IVF works (clustering + searching within clusters)
4. ✅ Compare exact vs approximate search (trade-offs)
5. ✅ Decide which index to use based on the use case
6. ✅ Interpret the parameters (e.g. "ef_search" in HNSW, "nprobe" in IVF)
7. ✅ Reason about scalability (what happens with 1M, 10M, 100M vectors)

Quick test: If you can explain "Why does Pinecone use HNSW instead of exhaustive search?" without hesitating, you're ready for Module 5.

---

Direct application to production

Everything you'll see here is used in real vector databases:

Pinecone: HNSW by default (fast, high precision)
Weaviate: HNSW + IVF options
Qdrant: Optimized HNSW
FAISS: IVF + variants
Milvus: Support for multiple indexes

After this module, you'll understand why those tools make the decisions they make.

---

Next capsule: 02-knn-conceptual.md — The K nearest neighbors, exhaustive search.