Vector Search from First Principles

SIMD, Quantization, and Billion-Scale Retrieval

Introduction: Why Vector Search Matters Now

1. The Embedding Explosion
2. From Exact to Approximate: The Scaling Problem
3. What This Book Will Build
4. How to Read This Book

Chapter 1: Vectors, Embeddings, and Similarity

1. What Is a Vector (in This Context)?
2. How Embeddings Are Created
3. Distance Metrics: Euclidean, Cosine, Dot Product
4. Similarity as a Geometric Problem
5. Starting the Running Implementation: Vector Data Structures

Chapter 2: Brute-Force k-NN and Its Limits

1. The Exact Nearest-Neighbor Problem
2. Computational Complexity Analysis
3. Memory Bandwidth and the Real Bottleneck
4. Latency Budgets in Production Systems
5. Baseline Benchmarking Methodology

Chapter 3: Memory Hierarchy and Data Layout

1. The Memory Wall: Registers, Caches, RAM, Disk
2. Cache Lines and Spatial Locality
3. Array of Structures vs Structure of Arrays for Vectors
4. Memory Alignment and Padding
5. NUMA Architecture and Its Impact

Chapter 4: Floating-Point Representation and Quantization Foundations

1. IEEE 754 Floating-Point Format
2. The Cost of Float32 at Scale
3. Scalar Quantization (SQ)
4. Product Quantization (PQ): Subspace Compression
5. Binary Quantization and Hamming Distance

Chapter 5: Clustering-Based Indexes and IVF

1. The Partitioning Idea: Divide and Conquer in Vector Space
2. K-Means Clustering for Vector Indexes
3. Building an Inverted File Index (IVF)
4. IVF Search Parameters and Trade-offs
5. Extending the Running Implementation: IVF Index

Chapter 6: Graph-Based Search and HNSW

1. From Flat Graphs to Navigable Small Worlds
2. The HNSW Algorithm Explained
3. HNSW Parameters and Their Meaning
4. Memory Cost of HNSW Indexes
5. Extending the Running Implementation: HNSW Index

Chapter 7: Combining Techniques: Hybrid Approaches and Reranking

1. IVF-PQ: The Industrial Standard Combination
2. HNSW with Quantization
3. Two-Tier Retrieval: Fast Recall, Accurate Reranking
4. Hybrid Search: Combining Vectors with Keywords and Metadata
5. Extending the Running Implementation: Full Pipeline

Chapter 8: SIMD Vectorization and CPU-Level Optimization

1. What SIMD Actually Is
2. AVX2 Fundamentals: 256-Bit Registers and Instructions
3. Vectorizing Distance Computations
4. AVX-512: Doubling the Width, Adding Complexity
5. Benchmarking SIMD Speedups

Chapter 9: Parallelism, Concurrency, and Throughput

1. Multi-Core Threading for Vector Search
2. Lock-Free Index Reads and Safe Updates
3. Query Batching for Higher Throughput
4. Memory Mapping for Large Datasets
5. Extending the Running Implementation: Concurrent Server

Chapter 10: Persistence, Compression, and Disk-Backed Indexes

1. Serializing Index Structures to Disk
2. Fast Loading and Warm-Start Strategies
3. Incremental Updates and Write-Ahead Logging
4. Compression Beyond Quantization
5. Extending the Running Implementation: Persistent Indexes

Chapter 11: Distributed Architecture and Sharding

1. When Single-Machine Search Is No Longer Enough
2. Sharding Strategies for Vector Collections
3. Distributed Query Execution
4. Cross-Shard Recall and Its Degradation
5. Extending the Running Implementation: Multi-Node Cluster

Chapter 12: Observability, Benchmarking, and Capacity Planning

1. Proper Benchmark Methodology for Vector Search
2. Monitoring Vector Search Systems in Production
3. Capacity Planning: From Thousands to Billions
4. Profiling and Debugging Performance Problems
5. Comparative Analysis of Production Vector Search Systems

Chapter 13: Vector Search in Modern AI Infrastructure

1. Retrieval-Augmented Generation (RAG) Pipelines
2. Recommendation Systems and Vector Search
3. Multimodal Retrieval: Images, Audio, Text Together
4. The Future of Vector Search: Learned Indexes and Beyond

Conclusion: Principles Over Tools

1. The Stack Revisited: From Bits to Clusters
2. Choosing the Right Tool for Your Problem
3. Building Systems You Understand
4. Final Words on the Running Implementation

References