Transcript: Vector Database Search： HNSW Algorithm Explained

Version 1: Source Transcript

This document represents the raw lecture transcript recorded from the video lecture. For architectural study notes and system design documentation, see Version 2.

• Video URL: https://www.youtube.com/watch?v=cZyTZ-EMskI
• Video ID: cZyTZ-EMskI
• Word Count: 1,892 words

Full Transcript

What if I told you the movie Finding Nemo accidentally created the perfect explanation for one of computer science most elegant search algorithms? Today we're diving deep into how Finding Nemo teachs us the hierarchical navigable small word algorithm or HMSSW for short. HMSW transform an impossible challenge of searching through billions of items into something achievable in milliseconds. HS down quickly became one of the backbones of modern vector similarity search. And I'll bet this is the reason why you picked this video to watch, right? Well, I'm glad you're here. And if you stick to the end, I promise you, you won't regret it. [Music] When Nemo gets taken to Sydney, Marlin faces an impossible challenge. He needs to find one tiny clown fish in the entire ocean. If he tried to check every single fish one by one, it would take him years. We call this linear search or all of N complexity in computer science. HNSW transformed this into a logarithm search or O log of N, which is way faster. Let's put this way. This is exactly what Marlin wanted, a faster way to find Nemo. Let's dive into how HNSW works. Let's start with one fundamental concept. Imagine every fish as a point in a multi-dimensional space based on characteristics like helpfulness or size or swimming style etc. Similar fish will naturally cluster together. The rare fish here, sharks there, turtles elsewhere. This clustering of data is what A10SW exploits the most. The magic happens through a small word network. Dory knows both the raffish and sharks. The shark Bruce on the other hand knows about the EAC, the East Australian current. In the EAC, the turtle crush knows the way to Sydney. These long range connections transform an impossible search into a navigable journey. HNSW formalizes this by creating a hierarchical graph. Each layer is a proximity graph where fish connect to their nearest neighbors. But here's the trick. Not every fish appears in every layer. The number of layers grows on a logarithm scale. A 100 fish, for example, might need two layers. A million fish might need six layers whereas one billion fish may need nine. So as you can see space-wise hnssw is also a very efficient data structury. It means that more data doesn't mean proportionally more layers. This is the power of logarithmic scaling. [Music] mine. >> Let's follow Marley's journey to better understand HNSW's search algorithm. HNSW uses greedy search starting from the highest layer. Marley meets Dory who exists in multiple layers. Dory is a good example of what we call a hubby node which connect different communities. The EAC represents the highest later with sparse but powerful connections spanning vast distances. When Marlin rides with Crush the Turtle, he efficiently use this long range connections. When he reaches Sydney's vicinity, the algorithms drop the two lower layers for refined search, sparse layers for coarse navigation, and dense layers for precision. The idea here is at each layer, move toward the target until you can't get any closer, then drop down. It's like taking highways as far as possible, then switching to local roads. Here's the beauty of this. When Marlin finally reached Sydney Harbor, he only checks for a few fish instead of checking for a millions of them. The hierarchical structury guided him to precisely the right neighborhood. This is O log of N in action. [Music] >> Now let's discuss how data is organized with HNSW. Layer assignment is probabilistic. New fish are assigned at a maximum layer using an exponential distribution. Most stay in lower layers and some become highway connectors. This creates a self-organizing structury that maintains itself as the ocean grows. Of course, by ocean we are meaning your data set. This creates HNSW's foundation through three key principles. The first one is the small word phenomenon. Just like how Marlin reached Sydney through only a few key connections. For example, Dory connected to Bruce, Bruce connected to Crush. Any two points in the data can be connected through a small number of hoops. The second principle is navigability. At each step, you can greedily move closer to your target just like Marlin always moved towards Sydney. And the third principle is hierarchy. Having multiple layers means you can search efficiently. Whether you have a 100 fish or a billion, let's apply what you have learned so far with a quick demo using vector sets. Vector sets are a new data type introducing in Radis 8 that allows you to store and query highdimensional vector embeddings. At the heart of vector sets implementation is the HNSW algorithm. I will demonstrate how HNSW works by reproducing Marlin's relationships with the fishes shown in the Finding Nemo movie. As we execute a vector similarity search on the data, this is the graph output that we should see. First, it start with Marley. Marley meets Dory who leads them to the charts. After that, they meet the moonfish, then the turtles, then the whale, then Nigel, and finally reaching Nemo. [Music] So, let's start this demo by explaining what's going to be the data that we're going to put into Rad. So, as you can see here, I'm using the command V add, which is the uh the command that you can use to add data into a vector set. So the name of the key that we're going to use is going to be called finding name for obvious purposes. And then along with that key, we're going to associate a set of embeddings. Uh in this case, we're going to add five dimensions, right? But you are free to use how many dimensions you set properly. Each one of those dimensions are carrying some uh peculiar peculiar information from the fishes such as for example uh the journey position, uh the helpfulness of the journey, the size of the fish, etc., etc. And those are going to be the names of each element. Nigel, Dory, whale, moonfish. And along with each element, you can optionally right set a specific set of attributes that uh you put this in this JSON format. Uh I'm going to execute this command. So as you can see here, uh the data has been added. And one thing I would like to point out before we continue is that all the data has been added in a kind of a random order. So I didn't like put them in a biset order or the order that I want them to be shown when we perform the search. Um so you can really believe that the output is going to be based on the embeddings that we have set for this. Right? So uh I'm going to clear the results and then we can actually inspect the data type that's being used here using the command type. So as you can see here we're using a vector set and uh the also the other command that you can also use the command v info right so the info command kind of a gives you like a debug visualization of that specific key uh for all the metadata that is peculiar to the vector set. So for example the type of quantitization that we're using. So by default vector sets us uh integer uh the eight right. So there are some specific attributes that are unique to the HNSW algorithm. So it's very interesting because of this. Now let's do what we're all here for which is performing the actual search, right? So we're going to use the command vim or v similarity if you will. So we provide the key that you were going to perform the similarity search and those are going to be the values that basically is going to kind of a mimic all the relationships from all the fishes, right? zone from the uh the very early uh type of fish added to the the the maximum position. So if we execute this right now, you're going to see that the order represents what we were expecting before. So it all started with Marley and then Dory then meets the sharks that led them to the moon fish then the turtles the whale Nigel to finally uh reach and niml right. So one of the interesting thing that you can actually do with the vector set now that you saw that it exactly work it is also kind of a do a little bit of debugging of the proximity between the elements. For example, if you want to see what are the three closest fishes uh near to Martin, we can use this command here and as you can see the fishes are Marlin itself, Dory and the sharks, right? So if we do the same thing for Dory, remember that Dory is one of the hub nodes, right? So she connects through different layers. Um we're going to see that yeah there's Dory itself then the sharks then the moonfish right. Um and finally you can also use like the attributes that we have used it before to perform some specific type of searches. So in this case for example we're searching for all the fishes that are either the helpers right or they are transporters. So th those are features that carry over right for a specific uh destination. So, in this case, it's going to be Dory. Dory is definitely the most helper uh according to the movie, right? You can see that she's always trying to kind of make her best to uh help Marlin to find Nemo and the turtles to who are actually the carriers that lead them to uh Sydney right to the final destination. So as you can see the this is the proof that the hnssw algorithm is correctly working with the vector sets implementation at radis and I mean it is awesome as you can see here let's recap what finding nemo thought us today first hierarchical organization matters just like the ocean has local rafts regional territories and ocean spanning currents hnsw builds multiple scales of organization that grow logarithmically with your data. Second, not all connections are equal. Hub nodes like DRI who bridge different communities are essential for maintaining the small word property. And third, gritty navigation works when you have the right strategy. By always moving toward your target and dropping layers strategically, you can find anything quicker. This isn't just too radical anymore. Right now, HNSW powers Spotify's recommendation systems, similarity search and open AIS and battings, image search at Pinterest, and countless other applications handling billions of vectors. The beauty of computer science, in my opinion, is that elegant solutions often mirror patterns in nature and storytelling. Take Pixar's animators for example. They created an ocean that perfectly demonstrate advanced graph theory that is shown in the movie probably without even knowing it. So the next time you are designing a system that needs to find data quickly just remember this. You don't need to check every fish in the ocean. The only thing you need is just keep swimming. Just keep swimming swimming. Swimming through hierarchical nav go small words. hierarchical nav go small words. You got it. You got it. See you in the next time. [Music]

Timestamped Segments

• [00:00] What if I told you the movie Finding Nemo accidentally created the perfect explanation for one of computer science most elegant search algorithms? Today we're diving deep into how Finding Nemo teachs us the hierarchical navigable small word algorithm or HMSSW for short.
• [00:20] HMSW transform an impossible challenge of searching through billions of items into something achievable in milliseconds. HS down quickly became one of the backbones of modern vector similarity search. And I'll bet this is the reason why you picked this video to watch, right? Well, I'm glad you're here. And if you stick to the end, I promise you, you won't regret it.
• [00:47] [Music] When Nemo gets taken to Sydney, Marlin faces an impossible challenge. He needs to find one tiny clown fish in the entire ocean. If he tried to check every single fish one by one, it would take him years. We call this linear search or all of N complexity in computer science.
• [01:09] HNSW transformed this into a logarithm search or O log of N, which is way faster. Let's put this way. This is exactly what Marlin wanted, a faster way to find Nemo. Let's dive into how HNSW works. Let's start with one fundamental concept. Imagine every fish as a point in a multi-dimensional space based on characteristics like helpfulness or size or swimming style etc. Similar fish will naturally cluster together. The rare
• [01:42] fish here, sharks there, turtles elsewhere. This clustering of data is what A10SW exploits the most. The magic happens through a small word network. Dory knows both the raffish and sharks. The shark Bruce on the other hand knows about the EAC, the East Australian current. In the EAC, the turtle crush knows the way to Sydney. These long range connections transform an
• [02:14] impossible search into a navigable journey. HNSW formalizes this by creating a hierarchical graph. Each layer is a proximity graph where fish connect to their nearest neighbors. But here's the trick. Not every fish appears in every layer. The number of layers grows on a logarithm scale. A 100 fish, for example, might need two layers. A million fish might need six layers whereas one billion fish may need nine.
• [02:48] So as you can see space-wise hnssw is also a very efficient data structury. It means that more data doesn't mean proportionally more layers. This is the power of logarithmic scaling. [Music] mine.
• [03:09] >> Let's follow Marley's journey to better understand HNSW's search algorithm. HNSW uses greedy search starting from the highest layer. Marley meets Dory who exists in multiple layers. Dory is a good example of what we call a hubby node which connect different communities. The EAC represents the highest later with sparse but powerful connections spanning vast distances.
• [03:39] When Marlin rides with Crush the Turtle, he efficiently use this long range connections. When he reaches Sydney's vicinity, the algorithms drop the two lower layers for refined search, sparse layers for coarse navigation, and dense layers for precision.
• [03:59] The idea here is at each layer, move toward the target until you can't get any closer, then drop down. It's like taking highways as far as possible, then switching to local roads. Here's the beauty of this. When Marlin finally reached Sydney Harbor, he only checks for a few fish instead of checking for a millions of them. The hierarchical structury guided him to precisely the right neighborhood. This is O log of N in action.
• [04:37] [Music] >> Now let's discuss how data is organized with HNSW. Layer assignment is probabilistic. New fish are assigned at a maximum layer using an exponential distribution. Most stay in lower layers and some become highway connectors. This creates a self-organizing structury that maintains itself as the ocean grows. Of course, by ocean we are meaning your data set. This creates HNSW's foundation through three key principles. The first
• [05:12] one is the small word phenomenon. Just like how Marlin reached Sydney through only a few key connections. For example, Dory connected to Bruce, Bruce connected to Crush. Any two points in the data can be connected through a small number of hoops.
• [05:31] The second principle is navigability. At each step, you can greedily move closer to your target just like Marlin always moved towards Sydney. And the third principle is hierarchy. Having multiple layers means you can search efficiently. Whether you have a 100 fish or a billion, let's apply what you have learned so far with a quick demo using vector sets. Vector sets are a new data type introducing in Radis 8 that allows you to store and query highdimensional
• [06:05] vector embeddings. At the heart of vector sets implementation is the HNSW algorithm. I will demonstrate how HNSW works by reproducing Marlin's relationships with the fishes shown in the Finding Nemo movie. As we execute a vector similarity search on the data, this is the graph output that we should see. First, it start with Marley. Marley meets Dory who leads them to the charts.
• [06:32] After that, they meet the moonfish, then the turtles, then the whale, then Nigel, and finally reaching Nemo. [Music] So, let's start this demo by explaining what's going to be the data that we're going to put into Rad. So, as you can see here, I'm using the command V add, which is the uh the command that you can
• [07:04] use to add data into a vector set. So the name of the key that we're going to use is going to be called finding name for obvious purposes. And then along with that key, we're going to associate a set of embeddings. Uh in this case, we're going to add five dimensions, right? But you are free to use how many dimensions you set properly. Each one of those dimensions are carrying some uh peculiar peculiar information from the fishes such as for example uh the journey position, uh the helpfulness of the journey, the size of the fish, etc., etc. And those are going to be the names
• [07:37] of each element. Nigel, Dory, whale, moonfish. And along with each element, you can optionally right set a specific set of attributes that uh you put this in this JSON format. Uh I'm going to execute this command. So as you can see here, uh the data has been added. And one thing I would like to point out before we continue is that all the data has been added in a kind of a random order. So I didn't like put them in a biset order or the order that I want them to be shown when we perform the search. Um so you can really believe that the output is going to be based on
• [08:14] the embeddings that we have set for this. Right? So uh I'm going to clear the results and then we can actually inspect the data type that's being used here using the command type. So as you can see here we're using a vector set and uh the also the other command that you can also use the command v info right so the info command kind of a gives you like a debug visualization of that specific key uh for all the metadata that is peculiar to the vector set. So for example the type of quantitization that we're using. So by
• [08:46] default vector sets us uh integer uh the eight right. So there are some specific attributes that are unique to the HNSW algorithm. So it's very interesting because of this. Now let's do what we're all here for which is performing the actual search, right? So we're going to use the command vim or v similarity if you will. So we provide the key that you were going to perform the similarity search and those are going to be the values that basically is going to kind of a mimic all the relationships from all the fishes, right? zone from the uh
• [09:21] the very early uh type of fish added to the the the maximum position. So if we execute this right now, you're going to see that the order represents what we were expecting before. So it all started with Marley and then Dory then meets the sharks that led them to the moon fish then the turtles the whale Nigel to finally uh reach and niml right. So one of the interesting thing that you can actually do with the vector set now that you saw that it exactly work it is also kind of a do a little bit of debugging
• [09:55] of the proximity between the elements. For example, if you want to see what are the three closest fishes uh near to Martin, we can use this command here and as you can see the fishes are Marlin itself, Dory and the sharks, right? So if we do the same thing for Dory, remember that Dory is one of the hub nodes, right? So she connects through different layers. Um we're going to see that yeah there's Dory itself then the sharks then the moonfish right. Um and finally you can also use like the attributes that we have used it before
• [10:29] to perform some specific type of searches. So in this case for example we're searching for all the fishes that are either the helpers right or they are transporters. So th those are features that carry over right for a specific uh destination. So, in this case, it's going to be Dory. Dory is definitely the most helper uh according to the movie, right? You can see that she's always trying to kind of make her best to uh help Marlin to find Nemo and the turtles to who are actually the carriers that lead them to uh Sydney right to the final destination. So as you can see the
• [11:04] this is the proof that the hnssw algorithm is correctly working with the vector sets implementation at radis and I mean it is awesome as you can see here let's recap what finding nemo thought us today first hierarchical organization matters just like the ocean has local rafts regional territories and ocean spanning currents hnsw builds multiple scales of organization that grow logarithmically with your data. Second, not all connections are equal. Hub nodes
• [11:38] like DRI who bridge different communities are essential for maintaining the small word property. And third, gritty navigation works when you have the right strategy. By always moving toward your target and dropping layers strategically, you can find anything quicker.
• [11:57] This isn't just too radical anymore. Right now, HNSW powers Spotify's recommendation systems, similarity search and open AIS and battings, image search at Pinterest, and countless other applications handling billions of vectors. The beauty of computer science, in my opinion, is that elegant solutions often mirror patterns in nature and storytelling.
• [12:23] Take Pixar's animators for example. They created an ocean that perfectly demonstrate advanced graph theory that is shown in the movie probably without even knowing it. So the next time you are designing a system that needs to find data quickly just remember this. You don't need to check every fish in the ocean. The only thing you need is just keep swimming. Just keep swimming swimming. Swimming through hierarchical nav go small words. hierarchical nav go small words. You got it. You got it. See you in the next time.
• [12:59] [Music]