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 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 led 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 nine. We start at the uppermost layer and move right until we reach nine or a number larger than nine. Once we reach that number, in this case twenty, we know we've gone too far in this layer, So we move back to five, the number in this layer that is closest to nine, and then move down a layer. In the second layer, we start at five and move across until we reach the next number in this layer, thirteen. Again, we're above nine, so we've gone too far. Let's go back to five and then move down a layer. In the third layer, we move to the right and reach nine. 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 twenty eleven, 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 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 the 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 maybe you're asking yourself, what do a bunch of graphs have to do with vector search? Well, the ideas behind skip list and NSW led to the development of hierarchical navigable small world graphs, also known as HNSW. An 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 lengths 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. With Atlas Vector Search, we have two different ways of navigating the HNSW graph, approximate nearest neighbor or exact nearest neighbor, often shortened to ANN and ENN respectively. Each method provides different trade offs between search speed and precision. 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 uppermost 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. On the other hand, exact nearest neighbor, or ENN, searches every point in the dataset to guarantee finding the true nearest neighbors without relying on the HNSW graph's navigational structure. This search provides perfect accuracy and eliminates any chance of outliers in your results, but it's computationally expensive and can be slow, especially with large datasets. So how do you determine which one to use? Choose ANN when you're working with large datasets, where search speed is important to your end user experience, and you can accept a slight trade off in precision for significantly faster performance. Choose ENN when you're in proof of concept development phases, where perfect accuracy is essential. You need to benchmark and validate your search results, or you're working with smaller filtered data sets, like under ten thousand documents. This probably seems quite complex, which it is. But the good news is that Atlas Vector Search takes care of all of 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.