Loading...
practical understanding of how approximate nearest neighbors' algorithms, also known as ANN, trade a little bit of accuracy or recall for a lot of performance. Specifically, you'll explore the hierarchical navigable small words ANN algorithm to understand how this powers the world's most powerful vector databases. We'll also demonstrate the scalability of HNSW and how it solves the runtime complexity issues of brute-force KNN. Let's get coding! So, if you look at this example with 20 vectors, searching for the nearest one is not necessarily a big issue. However, as soon as we get to thousands or millions of vectors, this is becoming a way bigger problem and definitely a big no-go. There are many algorithms that allow us to actually find the nearest vectors in a more efficient way. One of the algorithms that solve this problem is HNSW, which is based on small world phenomenon in human social networks. And the whole idea is that on average we are all connected from each other by six degrees of separation. So, it's very possible that you have a friend, who has a friend, who has a friend, who has a friend, who is connected to Andrew. And the whole idea is that you probably know somebody that knows everyone. And that person probably also knows somebody that's really well connected and through that you could actually through within six steps find the connection to the person you're looking for. And then, automatically we could apply the same concepts to vector embeddings if we build those kinds of connections. And now, let's have a look at navigable small world which is an algorithm that allows us to construct these connections between different nodes. So, for example, in here we have eight randomly generated vectors and let's have a look how we can connect all of them together to their nearest neighbors. So, if we start with vector 0, there's nothing to connect just yet. Then, we add vector 1 and the only possible connection is to a vector 0. And now ,we can add vector 2 and we can build two connections between 1 and 0. Following the same method, we can go to vector 3 and the two nearest connections will be to vectors 2 and 0. Cool! Next, let's go to number four and the two nearest connections probably two and zero. Great! Now, let's go to five is well connected to two and zero. Now, we can go to six connects to two and four. And then, finally, seven connects to vectors five and three and just like that we build a Navigo small world, and just as a note for you in this example we only try to build two connections per vector as we're going but in reality, you could have eight connections or 32 or even more depending on the number of vectors you have. Now, let's see how the search of the Navigo small world can be performed. In this example we have a query vector which is on the left and we could already kind of guess that number six will be the nearest vector and usually how you work with NSW, and we start with a random entry node and we try to move across towards the nearest neighbors. So, starting from node 7, which is connected to nodes 3 and 5, we can see that 5 is closer than node 7. So, we can move there. Great! Now, from node 5 we can see that we are also connected to 0 and 2 and 2 is definitely way closer. Great! And then, from 2 we have multiple candidates with the best option being node 6 and then from 6 there are no longer better candidates and therefore our query concludes here and that's how we found our best match. Which happens to be our nearest neighbor vector that we're looking for. So, the search with NSW doesn't always result in finding the best match. So, let's have a look at this from this example. If we start from node 0, in this case our potential candidates are here and the best possible version from this step is vector number 1. And then, from vector number 1 there are no longer any better candidates and therefore our search concludes here. In this case we didn't find the best possible result, however we found approximately nearest neighbor, which is still a pretty good result, but it's not necessarily the perfect result. Now, it's time to learn hierarchical navigable small world, which puts several layers of navigable small worlds on top of each other. And the way you can imagine it's a bit like if you were to travel to some place in the world. First, you probably you would take a plane to the nearest airport to where you're trying to get to. Then, maybe you would go to and catch a train that would take you to the town where you wanna get to. And then finally, once you are at the bottom layer, you would walk or maybe take a taxi to the destination that you're going to. And we're pointing out that the construction of each layer of HNSW is very similar to how it's done in NSW, so we won't be diving into that. And the way the querying works with HNSW is that, again, we're starting with a random node, and we only can choose from those available at the highest level, and then we move to the nearest one within that layer. Once we are there, we can find the best possible match at that and the next layer, and eventually, once we are at the bottom layer, we can go to the object which is the closest to the query vector, which will help us to the last mile of the search. And the way nodes are assigned to each different layer. It's done by randomly generating a number which assigns that node to that layer and all the ones below and it's worth pointing that the chances of landing in a higher layer is logarithmically lower versus the one below. And as a result we'll have a lot fewer nodes in the top layer versus the one towards the bottom. So, for example if the random number is 0 then that node would only exist on the bottom layer, layer 0. If the random number is 2, then that node will exist on layer 0, 1 and 2, etc. So, here are some characteristics of HNSW. So, I mentioned before, there's a lot lower likelihood for a node to exist in higher levels and query time increases logarithmically, which means that as the number of data points increases, the number of comparisons to perform vector search only goes up logarithmically. In computer science, this is known as OLOG and runtime complexity, which visualizes very nicely that as the number of data points grows, the speed doesn't necessarily suffer that much over time. And as you can see in this graph, if we go from half a million vectors to a million vectors, the increase of runtime is minimal. So, now let's see how this all works in code. So, in this notebook we'll start with 40 vectors with two dimensions for each and we will set the nearest neighbor connections to 2. And we can construct those randomly. So, now let's add a query vector which is located at 0.5, 0.5. So, in here, what we do is create a list of nodes with the query vector, which is that one single point. Then, we use the Network X library for illustration purposes, which we'll use later on in the next block again. Finally, we print our nodes, and this part creates the position of the query for plotting in the next box. Next, we will run a brute-force algorithm to find the best possible vector embedding for our search and then plot it on the graph. So, in this case we can see our query over here and the best possible match right next to it. In this step, we construct our HNSW layers. And then, in loop we go one by one. And then, print the layer ID. And then, we show all the nodes and the connections at each layer. So, let's have a look. So, at the top layer we can see that we have nodes 20, 34, 28 and 39 already connected to each other. Then, when we get to layer 2, we get more nodes with more connections. Then, at layer 1 we have pretty much most of the nodes already reconnected. And then finally, at layer 0 we have all the nodes present and connected to their nearest neighbors. And now, that we have the whole network built up across all the layers, we can run an actual HNSW search query. And the first thing that we will get is search path graph array, which contains the graph with the travel paths across all layers. And then next, we have entry graph array, which gives us the entry point to the graph. And then, we run across all the layers in a loop to plot all the results layer by layer for the visual purposes. So, we start at the top layer with the node 39, which from 39, we can move to node 20, which gets us closer to the query. And once we are on 20, there are no longer any nodes that are neighbors to 20 that will get us closer to the query. Then, we can move to the layer 2. From layer 2, node 20 can take us to node 16, but node 16 doesn't have any other candidates that could get us closer to the query, which then takes us to the next layer. From layer 1, we can move from node 16 to 2. And from 2, there are no longer any other candidates that would get us closer to the query. So, we can finally move to the bottom layer. And then, from node 2, we can actually go all the way to node 25, which as it happens, is the perfect match to our query. And just like that, we made HNSW query across all the layers and return the newest possible match. So now, let's have a look how we can perform vector search with a vector database, which pretty much encompasses all that functionality inside. So, for this we'll use Weaviate, an open-source vector database. And one of the modes that Weaviate offers is an embedded option, which allows us to run the vector database inside the notebook. So, as a first step, we need to create our data schema, or what I like to call it, data collection. So, in this case, what we'll do is call it myCollection or yourCollection with the vectorizer set to null, which basically means that we just want to use pure vector search. And the distance metric they want to use is set to cosine. And then, once we run that, we'll get a new empty collection in our database. And just in case, if you want to rerun the same example again later on, and you need to recreate their collection, I'm going to leave you a piece of code that allows you to just delete the collection if it exists and then recreate it, but don't necessarily feel like you have to rerun it over and over again. And now, it's time to import some data into the vector database. So, let's say we have these five random objects with a title and a full value and a vector embedding. And here's the code that will help us actually get our data object and load them into the database. We kind of set it up, this is basically a best practice although we only work with five objects. Usually if you're loading like tens of thousands or millions it's actually good to use a batch loading process. And then, what we do is actually run in a loop through all our data items and construct like let's call it a properties object. And then, we run this client batch add data object which insert the object into our database. So, what we need to do is add the collection name, so we call it myCollection. Then, the data object is properties that we had, and the vector actually exists inside itemVector, and that's how we actually pass the vectors into the database. And now, let's check how many objects we have inside our database. So, we can run this query on our collection and then we could just ask for the count of the objects inside and if you run. That we can see that our collection contains five objects. So now, let's have some fun with actually querying the database. The query is as follows. So, what we say like hey. I want to search to myCollection and I want to get the title back and I want to run it with this vector. So, this is like just a random vector across six dimensions just to match our original data, and by saying this we are telling Weaviate to only get two best matches. And if I run this it kind of tells us that the second object, the fourth object matches our results. And if you want to see the vector embeddings for all the matched objects we can maybe copy this code over here and add this line, which basically tells us to get also the distance the vector and the ID for our data and now we can see that the first object the distance was calculated as 0.65 and this is the vector that got matched and the same thing for this second matched vector. And since we are working with a vector database, we can do all the additional things like filtered on specific properties. So, in this case what we can do is add an extra bit of code which will tell the database to search on foo for values that are greater than 44 and only search on the pre-filtered objects like this. And you can see that the only object that got matched are those where the foo value indeed is greater than 44. And one other thing that we can do here with a vector search we can look for other similar objects based on a provided ID of an object. So, in here, we're just grabbing the first result from the previous query and we're looking for three objects that match this object. And in this case, you of course find itself along with the fourth and the first object too. And that's it for this lesson. In this lesson you learn how HNSW works, how you can construct HNSW layers and search across all of them, but also you learn how to use similar algorithms in a production ready database. And in the next lesson, you will learn how to use the vector database with machine learning models like OpenAI, how to vectorize the data and how to vectorize the queries, but also you will dive into CRUD operations for creating, reading, updating, deleting objects.