Transcript: Exact vs Approximate (HNSW) Nearest Neighbors in Vector Databases

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=9NvO-VdjY80
• Video ID: 9NvO-VdjY80
• Word Count: 1,044 words

Full Transcript

When you first get started with vector search, it can be confusing to understand the difference between exact and approximate search methods. Often called KN&N for K nearest neighbors and A&N for approximate nearest neighbors. In this video, we'll break down the differences between these two methods and when to choose each. When performing vector search, we're trying to identify which vectors from our data set are most similar to our query vector. The closer two vectors are in vector space, the more similar they tend to be, which makes vector search especially powerful for finding relevant information, matching patterns, or surfacing related content based on meaning rather than just exact keywords. Because of this, vector search, especially when implemented with vector databases like radius, is the foundation of many modern AI applications. Vector search powers a variety of use cases including retrieve augmented generation rag recommendation systems semantic search anomaly detection and more. However, when you perform vector search, you usually need to choose between two types of vector search algorithms. Exact match or approximate nearest neighbors. Exact and nearest neighbor search guarantees that you find the truly closest vectors according to your chosen distance metric, but it can be slow and computationally expensive for large data sets. Exact neighbor is often called flat in radius and other vector databases because it works by implementing a flat index which is the simplest way to organize vectors in a data set. It just stores all the vectors in a single list or array without any special structure or partitioning. When you search using a flat index, the system compares the query vector to every vector in the data set to find the exact nearest neighbors. A brute force linear scan. While this approach guarantees perfect accuracy, as your data set grows, the time it takes to perform a query grows linearly, which can become a bottleneck in applications that require low latency or work with millions or even billions of actors. To overcome these inefficiencies of flat search, approximate nearest neighbors algorithms were developed. This method sacrifice a bit of precision in exchange for massive speed and scalability improvements. Approximate nearest neighbors algorithms allow you to quickly find vectors that are very close though not always exactly the closest, which is often more than good enough in real world applications where performance is critical. Among them, you'll find algorithms such as inverted file index, IFI, product quantization, PQ, approximate nearest neighbors, oh yeah, annoy, and hierarchical navigable small world, HNSW. Each of this takes a different approach to speed up search while balancing accuracy and performance trade-offs. In this video, we'll focus on HNSW, which has become one of the most widely used and effective ANN algorithms, especially modern vector databases and large scale AI applications. The way it works is by organizing vectors into several layers of graphs. The top layers are sparse, helping the algorithm move quickly in the right direction. As it goes down through the layers, the graphs get denser, allowing a more detailed search. When you run a query, the algorithm starts at the top and quickly heads towards similar vectors, refining its search as it goes lower. Imagine you have a data set with a thousand vectors. To make nearest neighbor search efficient, you organize these vectors into a multi-layer graph. At the very top, you have a sparse representation. Say only 100 of those vectors are included. These nodes are connected to each other forming a small world graph structure. You begin the search at this top layer by picking a random node. From there, you look at its neighbors and move to the one that is closest to your query vector. You keep repeating this process, always checking neighboring nodes and moving to the closest one until there are no closer options. This gets you close to your target, but only within the context of the sparse top layer. Once you are at the best position in that layer, you drop down to the next layer. This one is denser. It includes the 100 vectors from above plus several hundred more, maybe 400 in this case. You continue the same search strategy. From your starting point, explore neighboring nodes and move toward the one closest to the CRE vector, refining your position as you go. Finally, you reach the bottom layer, which includes all thousand vectors in your data set. This layer offers the most detail and the densest set of connections. You perform one final search here, again, navigating from node to node until you reach the one that is nearest to your query. Because each layer brings you progressively closer to the right region of the data set. This hierarchical process lets you find approximate nearest neighbors quickly and efficiently. This layered approach allows us to navigate through a much smaller number of vectors instead of having to scan through all of them. And its accuracy can be tuned by setting parameters such as M which controls how many connections each node keeps in the graph and EF or entry factor which determines how many candidate nodes the algorithm considers during the search. Increasing the entry factor improves accuracy but makes searches slower while lowering it speeds things up but may reduce precision. This flexibility lets you adjust HNSW to your specific performance and accuracy needs. Now what we recommend is that flat is chosen when absolute precision is required, the data set is a small less than a million vectors or when you can afford the latency of exact search. But when working with large data sets with greater than a million vectors where performance and scalability matter most in a small trade-off in accuracy is acceptable, we recommend opting for HNSW. In practice, hierarchical navigable small world provides excellent accuracy, often near exact with significant speed advantages, making it the go-to choice for most production scale vector search applications. And finally, if you're getting started with AI or want to follow the latest trends, don't forget to check out our ready AI researches GitHub repository, which is filled with recipes to get you started with AI fast. My name is Rafael De Leo. Thank you for watching and as always, stay curious.

Timestamped Segments

• [00:00] When you first get started with vector search, it can be confusing to understand the difference between exact and approximate search methods. Often called KN&N for K nearest neighbors and A&N for approximate nearest neighbors. In this video, we'll break down the differences between these two methods and when to choose each. When performing vector search, we're trying to identify which vectors from our data set are most similar to our query vector. The closer two vectors are in vector space, the more similar they tend to be, which makes vector search especially powerful for finding relevant information,
• [00:33] matching patterns, or surfacing related content based on meaning rather than just exact keywords. Because of this, vector search, especially when implemented with vector databases like radius, is the foundation of many modern AI applications. Vector search powers a variety of use cases including retrieve augmented generation rag recommendation systems semantic search anomaly detection and more. However, when you perform vector search, you usually need to choose between two types of vector search algorithms. Exact match or
• [01:05] approximate nearest neighbors. Exact and nearest neighbor search guarantees that you find the truly closest vectors according to your chosen distance metric, but it can be slow and computationally expensive for large data sets. Exact neighbor is often called flat in radius and other vector databases because it works by implementing a flat index which is the simplest way to organize vectors in a data set. It just stores all the vectors in a single list or array without any special structure or partitioning. When you search using a flat index, the system compares the query vector to
• [01:38] every vector in the data set to find the exact nearest neighbors. A brute force linear scan. While this approach guarantees perfect accuracy, as your data set grows, the time it takes to perform a query grows linearly, which can become a bottleneck in applications that require low latency or work with millions or even billions of actors. To overcome these inefficiencies of flat search, approximate nearest neighbors algorithms were developed. This method sacrifice a bit of precision in exchange for massive speed and scalability improvements. Approximate nearest
• [02:12] neighbors algorithms allow you to quickly find vectors that are very close though not always exactly the closest, which is often more than good enough in real world applications where performance is critical. Among them, you'll find algorithms such as inverted file index, IFI, product quantization, PQ, approximate nearest neighbors, oh yeah, annoy, and hierarchical navigable small world, HNSW.
• [02:36] Each of this takes a different approach to speed up search while balancing accuracy and performance trade-offs. In this video, we'll focus on HNSW, which has become one of the most widely used and effective ANN algorithms, especially modern vector databases and large scale AI applications. The way it works is by organizing vectors into several layers of graphs. The top layers are sparse, helping the algorithm move quickly in the right direction. As it goes down through the layers, the graphs get denser, allowing a more detailed search.
• [03:08] When you run a query, the algorithm starts at the top and quickly heads towards similar vectors, refining its search as it goes lower. Imagine you have a data set with a thousand vectors. To make nearest neighbor search efficient, you organize these vectors into a multi-layer graph. At the very top, you have a sparse representation.
• [03:26] Say only 100 of those vectors are included. These nodes are connected to each other forming a small world graph structure. You begin the search at this top layer by picking a random node. From there, you look at its neighbors and move to the one that is closest to your query vector. You keep repeating this process, always checking neighboring nodes and moving to the closest one until there are no closer options. This gets you close to your target, but only within the context of the sparse top layer. Once you are at the best position in that layer, you drop down to the next layer. This one is denser. It includes
• [04:00] the 100 vectors from above plus several hundred more, maybe 400 in this case. You continue the same search strategy. From your starting point, explore neighboring nodes and move toward the one closest to the CRE vector, refining your position as you go. Finally, you reach the bottom layer, which includes all thousand vectors in your data set.
• [04:20] This layer offers the most detail and the densest set of connections. You perform one final search here, again, navigating from node to node until you reach the one that is nearest to your query. Because each layer brings you progressively closer to the right region of the data set. This hierarchical process lets you find approximate nearest neighbors quickly and efficiently. This layered approach allows us to navigate through a much smaller number of vectors instead of having to scan through all of them. And its accuracy can be tuned by setting parameters such as M which controls how
• [04:53] many connections each node keeps in the graph and EF or entry factor which determines how many candidate nodes the algorithm considers during the search. Increasing the entry factor improves accuracy but makes searches slower while lowering it speeds things up but may reduce precision. This flexibility lets you adjust HNSW to your specific performance and accuracy needs. Now what we recommend is that flat is chosen when absolute precision is required, the data set is a small less than a million vectors or when you can afford the
• [05:25] latency of exact search. But when working with large data sets with greater than a million vectors where performance and scalability matter most in a small trade-off in accuracy is acceptable, we recommend opting for HNSW. In practice, hierarchical navigable small world provides excellent accuracy, often near exact with significant speed advantages, making it the go-to choice for most production scale vector search applications. And finally, if you're getting started with AI or want to follow the latest trends, don't forget to check out our ready AI researches
• [05:59] GitHub repository, which is filled with recipes to get you started with AI fast. My name is Rafael De Leo. Thank you for watching and as always, stay curious.