Vector Databases Deep Dive (HNSW, Embeddings & ANN Search)

Vector databases (Pinecone, Milvus, Qdrant, pgvector) index multi-dimensional floating-point embeddings generated by machine learning models to enable semantic similarity search at millisecond latencies.

1. Distance Metrics for Embeddings

• Cosine Similarity: Measures the cosine of the angle between two vectors, invariant to vector magnitude:

$$\text{Cosine}(A, B) = \frac{A \cdot B}{\|A\| \|B\|}$$

• Dot Product: Useful when magnitude carries semantic weight (e.g. recommendation popularity).
• Euclidean Distance ($L2$): Straight-line distance in Euclidean space.

2. Approximate Nearest Neighbor (ANN) Algorithms

Exact search ($K$-Nearest Neighbors) requires comparing the query vector against every record in the database ($O(N \times D)$), which is prohibitively slow for millions of items. Vector DBs use ANN algorithms:

Hierarchical Navigable Small World (HNSW)

• Builds a multi-layer graph structure where upper layers contain sparse long-range highway edges, and lower layers contain dense local connections.
• Query starts at the top layer, performs greedy search, drops down a layer, and repeats, achieving $O(\log N)$ search latency with high recall ($> 95\%$).

Inverted File Index with Product Quantization (IVF-PQ)

• Divides the vector space into Voronoi cells via $K$-Means clustering.
• Compresses 1,536-dimensional float32 vectors into small 8-bit quantization codes, slashing memory footprints by up to 95%.

Key Architecture Trade-Offs & Decision Matrix