🏃 धडा 04 — Nearest neighbors: सगळ्यांना विचारणे विरुद्ध shortcut नकाशा

📍 तुम्ही इथे आहात: 8 पैकी धडा 04 · मागे: lesson-03-similarity · पुढे: lesson-05-build-a-vector-db

📦 या ब्रँचमध्ये काय आहे

धडे 01–03, आणि scaling ची गोष्ट: exact kNN, त्याला आडवी येणारी भिंत, आणि दहा लाख जागांचे halls milliseconds मध्ये शोधण्याजोगे करणारे ANN indexes (HNSW, IVF).

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

"माझ्यासारखी सर्वात जास्त असलेली 5 मुले शोधा."

प्रामाणिक पद्धत 🚶 (brute-force kNN, आपला toy हेच करतो): hall मधल्या प्रत्येक मुलाकडे जा, तुलना करा, सर्वोत्तम 5 ठेवा. पूर्णपणे बरोबर — आणि पूर्णपणे linear: 7 मुले, क्षणात; 7 million मुले × प्रत्येकी 1,000 निर्देशांक… तुमची query म्हातारी होऊन मरते. हीच भिंत.

Shortcut नकाशा 🗺️ (ANN — approximate nearest neighbors): hall गुपचूप स्वतःची मांडणी करतो:

HNSW — मैत्रीचा नकाशा 👋: प्रत्येक मुलाला काही शेजारी माहीत असतात, आणि काही मुलांचे hall च्या पलीकडे दूरचे पत्रमित्र असतात. तुमचा गट शोधायला: कुठूनही सुरुवात करा, लोभीपणे जास्त सारख्या मुलांकडे उड्या मारा — आधी express उड्या (पत्रमित्र), शेवटी जवळच्या उड्या. लाखो हस्तांदोलनांऐवजी साधारण log इतक्या उड्या. (प्रसिद्ध "six degrees" small-world युक्ती, engineering करून बनवलेली.)
IVF — वस्त्या 🏘️: hall चे आधीच districts मध्ये cluster करा; query ला जागा द्या, फक्त जवळचे काही districts शोधा. सोपे, memory ला सोयीचे; सीमेच्या अगदी पलीकडे उभा असलेला मित्र चुकू शकतो (सुधारण्यासाठी जास्त districts तपासा).

वेगाची किंमत: approximate. नकाशाकडून एखादा खरा शेजारी चुकू शकतो — हे recall ने मोजले जाते ("खऱ्या top-10 पैकी आपण किती परत दिले?"). खरे systems एक नॉब फिरवतात: जास्त मेहनत ↔ जास्त recall. ANN थोडा recall देऊन खूप वेगवान search मिळवते — speed ↔ recall चा नॉब तुमच्या स्वतःच्या data वर tune करा — आणि RAG साठी, जवळजवळ प्रत्येक वेळी बरोबर येणारा page-finder परिपूर्णपेक्षा वेगळा ओळखूही येत नाही.

🗺️ आकृती

flowchart TB
    q["❓ query seat"]
    subgraph brute["🚶 brute force - exact kNN"]
        b1["compare with ALL N seats<br/>N=7: instant · N=7M: 💀"]
    end
    subgraph hnsw["🗺️ HNSW - the friendship map"]
        h1["hop: pen-pal jumps first,<br/>local hops last → log-ish steps"]
    end
    subgraph ivf["🏘️ IVF - the neighborhoods"]
        i1["search only the nearest<br/>few districts"]
    end
    r["🎯 top-k · recall dial:<br/>speed ↔ % of true neighbors found"]
    q --> brute --> r
    q --> hnsw --> r
    q --> ivf --> r

❓ काय

Vector database ≠ vector index. Vector database म्हणजे storage-आणि-query system — जागा, stickers, filter, top-k (धडा 05 असा एक बनवतो). HNSW किंवा IVF ही त्या system च्या आतली indexing/search रणनीती आहे. Database आपला index बदलू शकतो; नुसता index म्हणजे database नाही.
kNN (exact) विरुद्ध ANN (approximate): अचूकता विरुद्ध scale. ~100k vectors पेक्षा कमी असतील तर आधुनिक hardware वर brute force बहुतेक वेळा पुरेसा असतो — एका वर्गासाठी नकाशा विकत घेऊ नका. 😄
HNSW (Hierarchical Navigable Small World): थरांचा graph; parameters M (प्रत्येक मुलाचे मित्र) आणि ef (search ची मेहनत — recall चा नॉब). बहुतेक आधुनिक vector DBs मधले default engine.
IVF (inverted file): k-means districts; nprobe = किती districts तपासायचे. बहुतेक वेळा compression (PQ) सोबत जोडले जाते — RAM मध्ये मावावे म्हणून जागा ढोबळ रेखाचित्रांसारख्या साठवल्या जातात; अंतिम उमेदवारांचे अचूक rerank करा.
Recall@k = प्रत्येक ANN benchmark सांगतो तो प्रामाणिकपणाचा metric. Recall च्या आकड्यांशिवाय speed चे आकडे म्हणजे marketing.
आपला toy मुद्दाम brute-force ठेवला आहे — तपासता न येणाऱ्या graph पेक्षा वाचता येणाऱ्या 70 ओळी जास्त चांगल्या. कोणत्या products मध्ये कोणता index आहे ते धडा 08 सांगतो, म्हणजे तुम्हाला तो कधीच स्वतः बनवावा लागत नाही.

🤔 का

हा धडा म्हणजे "हा database का आहे, for-loop का नाही" या प्रश्नाचे संपूर्ण उत्तर — for-loop बरोबरच आहे, फक्त तो scale होत नाही, आणि index रचना हेच product आहे. Vendor benchmarks साठी हा तुमचा थापा-ओळखणारा यंत्र पण आहे: "कोणत्या recall वर?" असे विचारा आणि खोली प्रामाणिक होताना पाहा.

🧪 करून पाहा — भिंत अनुभवा

python3 - <<'EOF'
import sys, time, random; sys.path.insert(0,'vectordb')
from vectordb import MiniVectorDB
words = ['robot','student','pizza','library','class','lunch','book','teacher']
db = MiniVectorDB()
for i in range(20000):
    db.add(f"d{i}", " ".join(random.choices(words, k=6)))
t = time.time()
db.search("robot library book", k=5)
print(f"brute-force over {len(db):,} chunks: {(time.time()-t)*1000:.0f} ms")
print("now imagine 7 million × 1536 dims — THAT'S why HNSW exists 🗺️")
EOF

⏭️ पुढे

यंत्र उघडा: vectordb.py, प्रत्येक ओळ — आणि त्यात तुमची पहिली भर.

git checkout lesson-05-build-a-vector-db

🏃 Lesson 04 — Nearest neighbors: asking everyone vs the shortcut map

📍 You are here: Lesson 04 of 8 · Previous: lesson-03-similarity · Next: lesson-05-build-a-vector-db

📦 What's in this branch

Lessons 01–03, plus the scaling story: exact kNN, the wall it hits, and the ANN indexes (HNSW, IVF) that make million-seat halls searchable in milliseconds.

🧒 Explain like I'm 5

"Find the 5 kids most similar to me."

The honest way 🚶 (brute-force kNN, what our toy does): walk up to EVERY kid in the hall, compare, keep the best 5. Perfectly correct — and perfectly linear: 7 kids, instant; 7 million kids × 1,000 coordinates each… your query dies of old age. That's the wall.

The shortcut map 🗺️ (ANN — approximate nearest neighbors): the hall secretly organizes itself:

HNSW — the friendship map 👋: every kid knows a few neighbors, plus some kids have long-distance pen-pals across the hall. To find your crowd: start anywhere, greedily hop toward more-similar kids — express hops first (pen-pals), local hops last. Log-ish hops instead of millions of handshakes. (The classic "six degrees" small-world trick, engineered.)
IVF — the neighborhoods 🏘️: pre-cluster the hall into districts; seat the query, search only the few nearest districts. Simple, memory-friendly; can miss a friend standing just across a border (probe more districts to fix).

The price of speed: approximate. The map might miss a true neighbor — measured as recall ("of the true top-10, how many did we return?"). Real systems tune a dial: more effort ↔ higher recall. ANN trades some recall for much faster search — tune the speed ↔ recall dial on your own data — and for RAG, a page-finder that is right nearly every time is indistinguishable from perfect.

🗺️ Diagram

flowchart TB
    q["❓ query seat"]
    subgraph brute["🚶 brute force - exact kNN"]
        b1["compare with ALL N seats<br/>N=7: instant · N=7M: 💀"]
    end
    subgraph hnsw["🗺️ HNSW - the friendship map"]
        h1["hop: pen-pal jumps first,<br/>local hops last → log-ish steps"]
    end
    subgraph ivf["🏘️ IVF - the neighborhoods"]
        i1["search only the nearest<br/>few districts"]
    end
    r["🎯 top-k · recall dial:<br/>speed ↔ % of true neighbors found"]
    q --> brute --> r
    q --> hnsw --> r
    q --> ivf --> r

❓ What

Vector database ≠ vector index. A vector database is the storage-and-query system — seats, stickers, filter, top-k (lesson 05 builds one). HNSW or IVF is an indexing/search strategy inside that system. A database can swap its index; an index alone is not a database.
kNN (exact) vs ANN (approximate): correctness vs scale. Under ~100k vectors, brute force on modern hardware is often FINE — don't buy a map for a classroom. 😄
HNSW (Hierarchical Navigable Small World): layered graph; parameters M (friends per kid) and ef (search effort — the recall dial). The default engine in most modern vector DBs.
IVF (inverted file): k-means districts; nprobe = how many districts to check. Often paired with compression (PQ) — seats stored as rough sketches to fit RAM; rerank the finalists exactly.
Recall@k = the honesty metric every ANN benchmark reports. Speed numbers without recall numbers are marketing.
Our toy stays brute-force ON PURPOSE — 70 readable lines beat a graph you can't inspect. Lesson 08 tells you which products carry which index so you never build one yourself.

🤔 Why

This lesson is the entire "why is this a database and not a for-loop" answer — the for-loop IS correct, it just doesn't scale, and the index structures are the product. It's also your BS-detector for vendor benchmarks: ask "at what recall?" and watch the room get honest.

🧪 Try it — feel the wall

python3 - <<'EOF'
import sys, time, random; sys.path.insert(0,'vectordb')
from vectordb import MiniVectorDB
words = ['robot','student','pizza','library','class','lunch','book','teacher']
db = MiniVectorDB()
for i in range(20000):
    db.add(f"d{i}", " ".join(random.choices(words, k=6)))
t = time.time()
db.search("robot library book", k=5)
print(f"brute-force over {len(db):,} chunks: {(time.time()-t)*1000:.0f} ms")
print("now imagine 7 million × 1536 dims — THAT'S why HNSW exists 🗺️")
EOF

⏭️ Next

Open the machine: vectordb.py, every line — and your first extension to it.

git checkout lesson-05-build-a-vector-db

This page is the lesson's README from the lesson-04-nearest-neighbors branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.