Vector Databases & How They Work

How Distance Calculation Works

For example, to find the distance between points (2,3) and (3,4):

Euclidean distance: √((2-3)² + (3-4)²)

With brute force, the system compares the query vector with every single vector in the database, calculating the distance each time. It then returns the items with the shortest distances.

Phase 1: Indexing (The one-time setup)

1. Find the 'Centers': The database first looks at all of your million vectors and uses an algorithm (like k-means clustering) to find, let's say, 100 'center points' or centroids. Each centroid is itself a vector that represents the average of a region in your data. Think of these as the signs for the sections in our library: "Fiction," "Science," etc.

2. Assign to Clusters: The database then goes through every single one of your million vectors and figures out which of the 100 centroids it's closest to. It then puts a "pointer" to that vector into a list for that centroid.

Searching (When you make a query)

1. Find the Closest Section(s): The database does NOT compare your query to all one million vectors. Instead, it just compares it to the 100 centroids. This is super fast. It finds that your query is closest to, say, 'Centroid #42' (the "men's casual shirts" section).

2. Search Only Within That Section: Now, the database knows your best matches are probably in the list for Centroid #42. So it only searches through the 10,000 vectors in that one cluster.

How It Works:

1. First Split: We pick a dimension (e.g., the x-axis) and find the middle point (the median). We draw a vertical line there. All points to the left go into the "left" branch of our tree, and all points to the right go into the "right" branch.

2. Second Split: Now we look at the two new groups. For each group, we pick the other dimension (the y-axis) and split it in half with a horizontal line.

3. Keep Splitting: We keep repeating this process, alternating which dimension we split on, until we only have a few points left in each final, tiny rectangle.

How HNSW Works

HNSW organizes vectors in a hierarchical graph structure with multiple layers:

• Layer 2: Highest level with few nodes
• Layer 1: Mid-level with alpha=3 connections per node
• Layer 0: Base level with alpha=6 connections per node

The Memory Problem

A single vector using 1536 dimensions of 32-bit floating-point numbers takes up 1536 * 4 bytes = 6,144 bytes. If you have a billion vectors, that's 6.1 Terabytes of RAM! That's incredibly expensive.

Product Quantization solves this by compressing vectors while maintaining their similarity relationships.

How Product Quantization Works

It chops the big vector into smaller segments. For example, a 16-dimension vector could be chopped into 4 segments of 4 dimensions each. [41, 42, ..., 416] → [chunk1], [chunk2], ..., [chunk4]

Step A: Split V into chunks

V = [1.1, 2.3, 0.9, 3.4, 8.8, 7.6, 9.1, 6.5, 4.2, 5.5, 3.4, 5.1, 9.9, 8.1, 7.7, 9.3]
total size = 16*4 = 64 bytes

v_chunk1 = [1.1, 2.3, 0.9, 3.4] -> mapped to [10]
v_chunk2 = [8.8, 7.6, 9.1, 6.5] -> mapped to [23]
v_chunk3 = [4.2, 5.5, 3.9, 5.1] -> mapped to [123]
v_chunk4 = [9.9, 8.1, 7.7, 9.3] -> mapped to [16]

Resulting compressed vector: [10, 23, 123, 16]

Step B: Create the Codebooks (k cluster/centroid)

For each chunk position, we create a codebook of representative vectors:

• Chunk 1 (dims 1-4): We take all the first chunks and look at Codebook 1.
• Chunk 2 (dims 5-8): We do the same for the second chunks and look at Codebook 2.
• Chunk 3 (dims 9-12): This gives us Codebook 3.
• Chunk 4 (dims 13-16): This gives us Codebook 4.

Codebook 1 might look like this (for 1 billion records, chunk1 might have 256 clusters/centroids):

0 : [1,2,3,6,4,7,2,1]
1 : [1,1,3,2,4,5,2,8]
2 : [2,2,3,6,5,7,1,1]
3 : [1,1,2,4,1,0,3,3]
...
255 : [4,2,3,6,1,7,2,1]

Vector databases typically store three types of information:

// Example record in a vector database
{
  id: "product_456", // unique identifier
  vector: [0.98, 0.23, -0.11, ...], // the numerical representation
  metadata: {
    product_name: "Red Running Shoes",
    price: 89.99,
    link: "https://example.com/shoes/456"
  }
}