10. Indexing

Indexing accelerates data retrieval in ML systems. Three types of indexing are commonly used.

Vector Indexing

Used for similarity search over embeddings. Essential for recommendation systems, semantic search, RAG, and similarity-based ML tasks.

Index Type	Search Speed	Recall	Memory
Flat (brute force)	Slow (O(N))	100%	Highest
IVF (Inverted File)	Fast (O(log N))	~90%	Moderate
HNSW	Fastest (O(log N))	~99%	High
PQ (Product Quantization)	Fast	~85%	Low (compressed)

# HNSW parameters
M = 16         # connections per node (higher = more accurate, more memory)
ef_construction = 200  # build quality (higher = better recall, slower build)
ef = 50        # search quality (higher = better recall, slower search)

Inverted Indexing

Classic information retrieval structure. Maps terms to documents. Used for keyword-based search and as a component in hybrid search systems.

# Inverted index structure
"machine" → [doc1, doc5, doc9, doc23]
"learning" → [doc1, doc3, doc5, doc12]
"system" → [doc2, doc5, doc7, doc9]

Query: "machine learning system"
Scoring: TF-IDF or BM25 on matching documents
Top result: doc5 (contains all three terms)

Hash Indexing

Provides O(1) lookups for exact key matches. Used for feature store lookups, cache keys, and model registry lookups.

Feature store: Redis hash maps entity_id → feature vector.
Prediction cache: Hash of (features + model_version) → prediction.
Model registry: model_name → latest_version mapping.

Which Index to Use Where

Component	Index Type	Why
Vector DB (semantic search)	HNSW	Best accuracy-speed trade-off for embeddings
Feature store (online)	Hash (Redis)	O(1) lookups by entity ID
Search (keyword)	Inverted index	Efficient term-document matching
Prediction cache	Hash	Fast exact match on request hash
Model registry search	Inverted + metadata	Find models by name, tag, metric

Exercise: Design the indexing strategy for a visual product search system where users upload an image and the system finds similar products. The product catalog has 10M items, each with a 512-dim embedding. Describe: vector DB choice, index parameters (HNSW M, ef), index build schedule (freshness), and how you handle new product additions without rebuilding the entire index.