Faiss

Install

CUDA-enabled Linux:
conda install -c pytorch faiss-gpu
Others:
conda install -c pytorch faiss-cpu

IndexFlatL2

IndexFlatL2
Measures the L2 (or Euclidean) distance between all given points between the query vector and the vector loaded into the index. It's simple, very accurate, but not too fast.

Given a set of vectors ${ x_1,..., x_n }$ with dimensions $d$, Faiss constructs a data structure in Ram——index , after constructing the structure, when a new dimension $d$ vector $x$ is given, the following operations can be performed efficiently:

$$
i = \mathrm{argmin}_i || x - x_i ||
$$

Where $||.||$ represents the Euclidean distance (L2)

In Faiss terms, a data structure is a *index，index is a person withadd方法object. *add can be used to add x_ivector. Please note that it is assumed x_iis fixed.

In Python, we would initialize our IndexFlatL2 index with our vector dimension (768 - the output size of our sentence embedding) as follows:

import faiss
d=sentence_embeddings.shape[1]
# >> d=768
index = faiss.IndexFlatL2(d)
index.is_trained
# >> True

Often, the indexes we use require us to train them before loading the data.

In Faiss,**Index** is an index structure built on a vector data set to support fast similarity searches in vector data sets. **is_trained** Yes Index A method of the class used to check whether the index structure has been trained (i.e. initialized).

if index.is_trained Returning True indicates that the index has been trained and is ready to accept queries. In other words, this means that the index structure has been initialized, vectors can be read from it, vectors can be added or removed, and similarity search operations can be performed using it. if index.is_trained Returning False indicates that the index has not been trained and needs to be initialized with a vector dataset before query operations can be performed.

Once ready, we load our embed and query like this:

1 2	index.add(sentence_embeddings) index.ntotal

add() Yes Index A method of class that adds vector data to the index. **sentence_embeddings** is an array containing vectors, each vector corresponding to an embedding of a sentence.

index.ntotal Yes Index Another property of the class that returns the number of vectors contained in the current index. in use add() method will sentence_embeddings Once the vector in has been added to the index, it can be accessed by calling index.ntotal Method to get the number of vectors already contained in the index. This can be used to check that the index has been added correctly for all vectors.

For example, if sentence_embeddings There are embedding vectors for 100 sentences in , and these vectors are passed add() method is added to the index, then index.ntotal The method will return 100, indicating that the index now contains 100 vectors.

1 2	k = 4 xq = model.encode(["Someone sprints with a football"])

In this code, **k** is an integer variable representing the number of nearest neighbor vectors to return when performing a similarity search. In Faiss, similarity search can be done using Index class search() method, which takes a query vector as input and returns the k vector.

In addition, **model.encode(["Someone sprints with a football"])** is a method call used to calculate the embedding vector of the input sentence. This method uses a pre-trained model to convert the input sentence into a vector representation that contains the semantic information of the input sentence.

Therefore, combining the two parts in the above code, you can get a query vector **xq**, which represents the embedding vector of the sentence "Someone sprints with a football". Then, you can use Index class search() method to find with xq most similar k vectors and returns a list of indices and a list of similarity scores for these vectors.

1
2
3

%%time
D, I = index.search(xq, k)  # search
print(I)

In this code, **%%time** is a magic command in Jupyter Notebook that measures the running time of a cell of code. **D** and I is in use Index class search() Method returns two results when performing a similarity search.

Specifically, **D** is an array containing similarity scores, representing the query vector xq with the retrieved k The similarity between the most similar vectors. **I** is an array containing the index of the corresponding vector, representing the same query vector xq most similar k The index position of a vector in the index data set.

So, combining the two parts in the above code, you can use **Index**Class **search()**Method to find and query vectors in index **xq**most similar**k** vectors and returns a list of indices and a list of similarity scores for these vectors. Then, use **print(I)** to output a list of indices of the most similar vectors retrieved. Due to **%time**The magic command is used, and the code cell will also print out the execution time of the code cell.

Partitioning The Index

Faiss allows us to add multiple steps that can refine our search using many different methods.
A popular approach is to partition the index into Voronoi units

We can think of our vectors as each contained within a Voronoi cell - when we introduce a new query vector, we first measure the distance between its centroids and then limit our search to the cells at that centroid.

Using this approach, we would take a query vector xq, identify the cell it belongs to, and then use our IndexFlatL2 (or another metric) to search between the query vector and all other vectors belonging to that specific cell.

Therefore, we are narrowing the search to produce an approximate answer rather than an exact answer (derived from an exhaustive search).

To achieve this, we first initialize our index IndexFlatL2 - but this time, we use the L2 index as the quantizer step - which we feed into the partition index IndexIVFFlat.

1
2
3

nlist = 50  # how many cells
quantizer = faiss.IndexFlatL2(d)
index = faiss.IndexIVFFlat(quantizer, d, nlist)

In this code,nlist Is an integer variable used to specify the number of cluster centers stored in the IVF (inverted file) index, that is, how many subsets the data set is divided into.quantizer is a Faiss index object used to allocate vectors into subsets of the IVF index. Here we use Faiss provided IndexFlatL2 type as quantizer, which uses the Euclidean distance metric to calculate the similarity between vectors and stores the vectors in a flat index structure.

In addition,d is an integer variable representing the dimensionality of the embedding vector. This value is determined based on the pretrained model and the feature dimensions of the embedding vector.

Finally,index is a Faiss index object used to support fast similarity searches in vector datasets. Here we used IndexIVFFlat type as index, which uses a data structure called an inverted file to organize vector datasets and uses quantizer to distribute vectors into different subsets. This index structure speeds up similarity searches and is very efficient when storing large-scale vector data sets.

1 2	index.is_trained >> False

1
2
3

index.train(sentence_embeddings)
index.is_trained
>> True

1
2
3

index.add(sentence_embeddings)
index.ntotal
>> 14504

Now that our index is trained, we can add data as before.

Let's search again using the same index sentence embedding and the same query vectorxq

1
2
3

%%time
D, I = index.search(xq, k)  # search
print(I)

Quantization

All our indexes so far have stored our vectors as complete (e.g.Flat) vector. Now, in very large data sets, this can quickly become a problem.

Faiss has the ability to compress vectors using product quantization (PQ). We can think of this as an additional approximation step with results similar to what we would get with IVF. Where IVF allows us to approximate by narrowing the search range, PQ instead approximates distance/similarity.

We split the original vector into several sub-vectors.
For each set of sub-vectors, we perform a clustering operation - creating multiple centroids for each set of sub-vectors.
Within the subvectors, we replace each subvector with the ID of its nearest centroid of the particular set

we use IndexIVFPQ Train the index – before adding the embeddings we also need the index

m = 8  # number of centroid IDs in final compressed vectors
bits = 8 # number of bits in each centroid

quantizer = faiss.IndexFlatL2(d)  # we keep the same L2 distance flat index
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, bits)

**m** is an integer variable representing the number of cluster centers to retain after vector quantization of each vector. A cluster center is a representative set of vectors selected from a vector dataset using the K-means clustering algorithm and can be used to approximate the original vectors.

**bits** is an integer variable that specifies the number of digits for each cluster center after vector quantization. higher bits
values can improve the accuracy of vector quantization, but also increase storage and computational costs.

In addition, **quantizer** is a Faiss index object used to allocate vectors into a subset of the IVF index. Here we use Faiss provided IndexFlatL2 Type as **quantizer**, which uses the Euclidean distance metric to calculate the similarity between vectors and stores the vectors in a flat index structure.

Finally, **index** is a Faiss index object used to support fast similarity searches in vector datasets. Here we used IndexIVFPQ Type as **index**, which uses a data structure called an inverted file to organize vector data sets, and uses vector quantization and product quantization techniques to compress vectors. This index structure speeds up similarity searches and is very efficient when storing large-scale vector data sets.

Nearest Neighbour Indexes for Similarity Search

Flat

The index you should look at first is the simplest - a flat index.

Flat indexing is "flat", we do not modify the input vector. Since there are no approximations or clustering of vectors - these indexes produce the most accurate results. We have perfect search quality, but this comes at the cost of a lot of search time. Using a flat index, we introduce the query vector xq and compare it to all other full-size vectors in the index - calculating the distance to each vector.

Using a Flat index, we will search the queryxqCompare to every other vector in the index.

After calculating all these distances, we return the k nearest ones as our closest matches.
k-nearest neighbor (kNN) search.

So when should you use flat indexes? When search quality is undoubtedly a high priority - search speed is less important. Also for smaller data sets, search speed may be a less important factor - especially when using more powerful hardware.

In short, use flat indexes when:

Search quality is a very high priority.
When search time doesn't matter or when using small indexes (<10K).

How can we make our search faster? There are two main methods:

Reduce vector size - by reducing dimensionality or the number of bits that represent a vector value.
Narrow the search - We can cluster or organize vectors into a tree structure based on certain attributes, similarities or distances - and limit our search to the closest clusters or filter the most similar branches.

Using either of these methods means that we no longer perform an exhaustive nearest neighbor search, but an approximate nearest neighbor (ANN) search - since we no longer search the entire full data set.

Locality Sensitive Hashing

Locality-Sensitive Hashing (LSH) is a technique for fast approximate search of similar objects in high-dimensional space. In many real-world problems, we need to perform similarity searches on high-dimensional vectors (such as images, audio, text, etc.), but traditional linear search methods are very inefficient in high-dimensional spaces because as the dimension increases, the complexity of the search increases exponentially.

LSH is a technique that maps similar vectors into the same "bucket" through a hash function, thus greatly reducing the number of vectors that need to be compared, thereby improving search efficiency. Specifically, LSH maps each vector into multiple hash tables, each of which consists of multiple hash functions. For a query vector, LSH will map it into each hash table, and then only perform similarity comparisons on vectors in the same bucket.

LSH can design different hash functions based on different similarity measures, such as Euclidean distance, cosine similarity, etc. Different hash functions can capture different characteristics of vectors in different spaces, thus adapting to different application scenarios.

Locality-sensitive hashing (LSH) works by grouping vectors into buckets by processing each vector through a hash function that maximizes hash collisions, rather than minimizing them as you normally would with a hash function.

What does this mean? Suppose we have a Python dictionary. When we create a new key-value pair in the dictionary, we hash the key using a hash function. The hash of this key determines the "bucket" in which we store its respective value:

A Python dictionary is an example of a hash table, which uses a typical hash function tominimizeA hash collision is a hash collision in which two different objects (keys) produce the same hash.

In our dictionary, we want to avoid these conflicts, because it means we will map multiple objects to a key - but with LSH, we want to maximizehashconflict.

Why do we want to maximize collisions? Well, for searching, we use LSH to group similar objects together. When we introduce a new query object (or vector), our LSH algorithm can be used to find the closest matching group:

Our LSH hash function attempts to maximize hash collisions, producing vector groupings.

nbits = d*4  # resolution of bucketed vectors
# initialize index and add vectors
index = faiss.IndexLSH(d, nbits)
index.add(sentence_embeddings)
# and search
D, I = index.search(xq, k)

This code uses the LSH index in the Faiss library, where d is the dimension of the vector, nbits is the number of digits in the hash value, and the value of nbits is usually a multiple of d, here it is set to d*4.

After initializing the index, the code passes **addMethod adds all sentence embeddings to the LSH index. Next, the code passessearch**The method searches the LSH index for the k vectors most similar to the query vector xq. The returned D is the similarity score and I is the corresponding vector index.

It is worth noting that Faiss’s LSH index uses a hash function to map vectors into buckets, each bucket containing a set of similar vectors. Therefore, LSH index is suitable for similarity search of high-dimensional sparse vectors, where similar vectors are concentrated in a small number of buckets, thereby reducing the time complexity of the search. However, the accuracy of LSH indexes may be affected by hash collisions and needs to be adjusted based on specific application needs.

nbitsrefers to the "resolution" of the hash vector. highernbitsValues mean greater accuracy, but use more memory and slower searches. Generally speaking, the larger the nbits, the higher the hash calculation complexity. This is because the increase in nbits will make the hash value space larger, thereby increasing the amount of operations and storage space required to calculate the hash value.

Hierarchical Navigable Small World Graphs

Hierarchical Navigable Small World (HNSW) is an algorithm for high-dimensional vector indexing designed to provide fast and accurate similarity searches. It is further developed based on the Small World network and Navigable Small World algorithm.

The HNSW algorithm represents vectors in high-dimensional space as nodes and builds a tree structure to organize these nodes. Each node in the tree represents a vector and holds information about the vector's position in the index and its similarity to other nodes. HNSW uses an approximate similarity calculation method to connect nodes, which allows the structure of the tree to be quickly navigated in high-dimensional space.

When building the HNSW index, a dense initial graph is first constructed. Then, nodes are gradually added to the graph and an approximate similarity calculation method is used to connect the nodes. These connections are established at different levels of the tree structure, thus forming a set of hierarchical structures. HNSW uses this hierarchical structure to accelerate similarity search, thereby improving search efficiency.

Compared with traditional tree structure and linear scanning methods, HNSW has higher search efficiency and better scalability. It performs well in similarity search tasks for large-scale high-dimensional vectors, and is widely used in data mining and machine learning tasks in areas such as images, text, and speech.

# set HNSW index parameters
M = 64  # number of connections each vertex will have
ef_search = 32  # depth of layers explored during search
ef_construction = 64  # depth of layers explored during index construction

# initialize index (d == 128)
index = faiss.IndexHNSWFlat(d, M)
# set efConstruction and efSearch parameters
index.hnsw.efConstruction = ef_construction
index.hnsw.efSearch = ef_search
# add data to index
index.add(wb)

# search as usual
D, I = index.search(wb, k)

This code uses the HNSW algorithm to construct an index of high-dimensional vectors and perform a similarity search.

Among them

Mis the number of neighbors connected to each node, that is, each node is connected to at most M nearest neighbor nodes when building the index.
ef_searchis the number of layers traversed during search, that is, the depth of search,
ef_constructionIs the number of traversal levels used when building the index.

These parameters can be adjusted to balance the trade-off between search time and index build time.

MandefSearchHave a greater impact on search time;efConstructionMainly increased index build time (means slower index.add)

Next, usefaiss.IndexHNSWFlatInitialize HNSW index. Then, changeefConstructionandefSearchParameters are set to predefined values. Finally, useindex.addMethod adds vector data to the index.

The last line of code usesindex.searchmethod to search. It will return the query vectorwbThe distance and index position of the k nearest neighbor vectors in the index.