What is Indexing? Indexing Methods for Vector Retrieval

Key Takeaways

Chad PT is pretty useful but you can't build a product out of it I have been talking about rag for many videos now and it's not for nothing as we've discussed in our book and course retrieving documents or useful text is necessary for all llm based products you need to give additional information to your llm if you want it to be really useful which means being more than just a Google Assistant it needs to have up toate context and relevant information to share with your user basically you want your own llm but without the cost of training one this is why rag exists but what if your database is immense or if there's a massive chunk of information to compare how do you ensure the retrieval part of the pipeline doesn't slow you down to start it's important to know that when we retrieve information we use a process called indexing so we have all our information stored in a database and then we want to index it as efficiently as possible for future retrieval let's see how we do that first in normal databases or search queries data is stored as rows with columns providing more information about the document such as metadata about the document like a date or authors Etc using a query from a user which is usually a question we used to find exact or very similar matches this has all change with the llm revolution instead of just finding precise matches we use a vector database our Vector database is basically all the database that we' fed into our llm to retrieve its own understanding of it which are our embeddings these embeddings are just a huge list of numbers that are attached to the general meaning of each chunk of text from our database then for each new query we can feed it to our embedding system and use this new list of numbers to compare it manually to all our database embeddings or vectors and retrieve the most similar ones in short in a vector database we use the content itself the semantic search to get similar content but we still have the volume problem what happens if we have millions and millions of vectors do we still compare each of them in our database to our query Vector not really this is where we need a good Vector index it's basically like a good sorting algorithm so what exactly is a vector index it's a data structure that searches and retrieves a vector embedding from a large data set of objects it needs to be both fast and accurate as we've seen an emitting is when an object is converted into a list of numbers each similar embedding is placed close to one another in the vector space how do we know two embeddings are similar we use distance metrics such as the Cene similarity do product or Olan distance to measure the distance and place the closer ones together they are basically all ways of comparing the numbers in large lists together and it gives us a number measuring dep there are various methods to create Vector indexes let's look at some of the popular methods in detail the easiest method is the flat index here we convert the text into a vector embedding and store it as it is we use a query to search it and get back the most similar information the advantage is that it is highly accurate still the disadvantage is that it makes searching very slow you need to compare your query embedding with all your data the next type of indexing is locality sensitive hashing or lsh indexes in this approach vectors are grouped into buckets based on similarity using special the locality sensitive hash functions when a query Vector is introduced it is hashed using the same functions to identify the most similar buckets only the vectors with this bucket are then searched to find a match it will be like a library where books are all categorized by fiction and general if you are looking for a specific book you only need to look into the category instead of the whole Library you can then order it by last name and you can find everything in a few seconds this method and that similarity items are grouped making the retrieval process efficient and precise another type of indexing is called the inverted file Index this is similar to the lsh algorithm we just saw but we use clustering to group vectors instead of hashing to create buckets we take a centroid and compute the Clusters so we calculate all embeddings of our data set and then group all of them using automatic algorithms that split our embeddings into dense groups based on resemblance in our library examp example comedy books might all be put together because of the laughs and other similar traits within the book one problem with this method is that when a query lies in the boundary of multiple clusters we tend to search all of them an improved version is called inverted file product quantization or IV fpq in IV fpq each Vector within a cluster is further broken down into smaller sub vectors and these sub vectors are encoded into bits AO process called Product quantization which really speeds up the comparison process we then compare these smaller encoded bits instead of the original embeddings for more efficiency so it's just a more efficient way of doing it but still we have the problem of checking the multiple clusters when it LS between each of them so instead we have another alternative the hierarchical navigable small words or hnsw index it's the most popular indexing method because it is fast and accurate narrowing down the search area to make it it easier to find what you need but how we first need to build a graph you start with an empty graph that looks like this when adding a document you start at the top and navigate down connecting to similar items at each layer each node is linked to its nearest neighbors creating a multi-layered structure then you search when searching for a vector You Again Begin at the top layer you find the nearest neighbors and move down through the nearest neighbors this continues layer by layer until you reach the bottom layer where you find the very few most similar vectors this process eliminates the vast majority of data by going down the layers through broadly similar vectors in a stepwise fashion we now know what a good index looks like so let's recap where it all fits together all your text or data from your database is split into small parts we call these text Parts our nodes they are essentially individual segments or units of the original data the text chunks here in our simple case these nodes are then converted into embeddings or numerical representations of the text into vectors or list of numbers and stored in a vector index database when your user asks a question which is your query it is converted into a vector embedding as well finally using the same indexing method the database searches for and Returns the top results that match the query this is a very basic setup and there's a lot you can do to in it a first quick Improvement will be to use prompting techniques to add context to the user question and help your retrieval system find the most relevant information possible as some questions might lack a lot of detail and be quite broad ending in disconnected Tings versus what you are really looking for then you can also Implement other types of search methods with keywords or hybrid search to further improve the system and help your indexing retrieve the desired information there are also other indexing methods like the multiscale tree graph you can look into we cover all this in depth in our course lessons and our book which are all linked below if you watch this from YouTube in any case the use of vector indexes in rag systems makes the retrieval of relevant information fast accurate and scalable by converting text into embeddings and storing them into a structured Vector index database the system can quickly and efficiently find semantically similar context in short Advanced indexing method such as hnsw lsh product quantization or mstg reduce the search space and ensure the high relevance of the retrieved information this can all be done with great Vector database platforms like chrom ADB or pine cone using L index as we see in the course I hope you now understand a bit more of what happens behind the scenes of indexing and why it's so important to implement one