11. Indexing & Retrieval

Vector Databases

Vector databases store and search high-dimensional embeddings. They are the backbone of semantic search, RAG (Retrieval-Augmented Generation), and recommendation systems.

HNSW (Hierarchical Navigable Small World)

The dominant ANN (Approximate Nearest Neighbor) algorithm. Builds a multi-layer graph where higher layers have fewer, further-apart nodes (long-range connections) and lower layers have dense connections.

# HNSW search flow (conceptual)
Search starts at top layer (layer=3, few nodes)
Greedily navigate to closest node in layer 3
Drop to layer 2: repeat from entry point
Drop to layer 1: refine search
Drop to layer 0 (dense): return k nearest neighbors

Complexity: O(log N) for search, O(N log N) for build
Recall: 95—99% with proper parameter tuning

Key parameters: ef_construction (build accuracy vs speed), M (connections per node), ef (search accuracy vs speed).

Inverted Indexes

Classic information retrieval: maps terms to documents containing them. Essential for keyword search and hybrid search (combined with vector search).

# Inverted index structure
"fraud" → [doc_1, doc_5, doc_9, doc_23, ...]
"transaction" → [doc_1, doc_3, doc_5, doc_10, ...]
"account" → [doc_2, doc_5, doc_7, doc_11, ...]

Query: "fraud transaction"
Results: intersection of doc lists or TF-IDF scoring
doc_5: contains both "fraud" and "transaction" → highest score

Tries (Prefix Trees)

Tries enable fast autocomplete and prefix-based search. Each node represents a character; paths from root to leaves represent words.

Use case: AI search bars, typeahead suggestions, code completion. Can be combined with a scoring mechanism (frequency of completed query).

Hybrid Search

Combines vector (semantic) search with keyword (exact) search. Typical approach:

# Hybrid search scoring
final_score = α * vector_similarity + (1-α) * keyword_score

# α controls semantic vs exact matching weight
# α=1: pure semantic search (ignores exact terms)
# α=0: pure keyword search (ignores meaning)
# α=0.5: balanced

RAG (Retrieval-Augmented Generation)

The dominant pattern for grounding LLM responses in real data:

# RAG pipeline
User query → Embed query → Vector search (top-k chunks)
→ Retrieve chunks from document store
→ Concatenate: prompt = instruction + retrieved chunks + user query
→ LLM generates grounded response
→ [Optional] Cite source chunks in response