C8Approximate nearest neighbor

Approximate nearest neighbor search is how you find the closest vectors to a query when there are millions or billions of them and exact comparison is hopeless. By trading a sliver of accuracy for orders-of-magnitude speed, ANN methods make similarity search practical at scale, and they have quietly become critical infrastructure behind retrieval, recommendation, and every RAG pipeline.

You will state the ANN problem and the recall@k metric, then build the major index families: locality-sensitive hashing (with MinHash for Jaccard and SimHash for cosine), inverted-file partitioning with product quantization for billion-scale compressed search, and HNSW small-world graphs that support near-logarithmic greedy traversal. You will close by comparing FAISS, pgvector, and managed vector databases along recall, throughput, and operational cost.

This is the engine room of modern semantic search: embeddings from any model become useful only once you can query them fast, which is why these structures sit underneath LLM retrieval, deduplication, and large-scale recommendation alike.