Video Transcript (English)

Welcome back. So we have all these vectors. Now if only we had an easy way to compare them.

As you may remember, vector embeddings are used to find similarities based on semantic meaning.

When we have vectors with hundreds or thousands of dimensions, how can we efficiently find those similarities?

Let’s take a moment to explore how this works behind the scenes.

In this lesson, we’ll learn how Atlas Vector Search indexes vector embeddings using Hierarchical Navigable Small World graphs or HNSW for short.

Then we'll learn about the approximate nearest neighbors algorithm used to search through the HNSW graph.

Before we dive in let's take a quick look at two major developments that lead to HNSW.

The first development is the skip list.

A skip list is similar to a sorted linked list but with much improved efficiency.

In fact, a skip list is made up of multiple layers of linked lists, and each layer includes various points on the list.

To help us understand how it works, let’s use this skip list to find the number 9.

We start at the upper most layer and move right until we reach 9 or a number larger than 9.

Once we reach that number, in this case 20, we know we've gone too far in this layer. So we move back to 5, the number in this layer that is closest to 9, and then move down a layer.

In the second layer, we start at 5 and move across until we reach the next number in this layer, 13. Again, we're above 9 so we've gone too far, let's go back to 5 and then move down a layer.

In the third layer, we move to the right and reach 9. Perfect!

Skip lists are an improvement on sorted linked lists, but they still take too much time when working with large datasets.

So now let's talk about the other development that informed HNSW.

In 2011, navigable small world graphs came into the picture.

NSW graphs are a type of proximity graph used to find similarities.

NSW graphs are made up of vertices with short and long links.

Each vertex, or node, is a data point in a highly dimensional space.

Each link, or edge, represents the similarity between the two points.

To illustrate, let's assume we have a data point in this highly dimensional space that is not part of the graph. We call this a query point.

We'd like to find the nearest graph point to our query point.

Our search begins at a random entry point in the graph and moves along the links to connected vertices. The goal is to move from the entry point to the query point in as few jumps as possible.

Once we arrive at the nearest neighbor to our query, we stop.

One problem with NSW graphs is that sometimes they'll stop too early.

If the random point where the search begins is closer to the query point

than the points it must traverse to get closer, it will stop.

This produces subpar results.

But our final development, HNSW, solves this problem!

Now you're probably asking yourself: “What do a bunch of graphs have to do with vector search?”

The ideas behind skip list and NSW lead to the development of Hierarchical Navigable Small World graphs also known as HNSW. And HNSW is the graph we use to index embeddings in Atlas Vector search.

HNSW graphs plot multiple points with long and short links, similar to an NSW graph.

But unlike NSW graphs which are on one plane, HNSW graphs are made up of multiple layers, like a skip list.

Layer zero contains all the plotted points with shorter links.

As we move up in the HNSW graph, there are fewer points and the links become longer. This creates a simpler view of the layer below it.

The top layer will have a few points with the greatest distance between them.

A good analogy for this is to imagine you're looking at a GPS map. The more you zoom out the less detail you see. As you zoom in, the view of your surroundings becomes more clear.

The next thing we should discuss is how to navigate the HNSW graph - or how we use the graph to perform an approximate nearest neighbor search, also known as aNN.

Approximate nearest neighbors or aNN doesn't search every point in the graph, it uses the HNSW graph to search until it finds an approximate neighbor.

This search is efficient, especially when you have a large dataset, but there's a slight chance of having an outlier in your results.

Let’s use the HNSW graph we went through earlier to see how searching works with the approximate nearest neighbor algorithm.

The blue point is our query point.

The entry point will be at a random point in the upper-most layer.

From here it selects the closest vertex it can find to the query point.

Then it will move down a layer.

Just like our skip list earlier, the process repeats at every layer.

Once we've reached the bottom layer, we’ll be at the query point surrounded by similarities.

This probably seems quite complex, which it is, but the good news is that Atlas Vector Search takes care of all this for us.

All we have to do is create a vector type search index, which you'll learn how to do in the next lesson.

Let’s recap what we learned.

First, we learned that Atlas Vector Search indexes vector embeddings using a Hierarchical Navigable Small World graph.

Next, we learned that HNSW graphs are made up of multiple layers. Each layer contains plotted points that are linked.

Finally, we learned that you can use aNN, the approximate nearest neighbor algorithm, which leverages the HNSW graph, to search for similarity.

Check out the next lesson to see how we build a Vector Search Index in Atlas!