Introduction to FAISS

FAISS (Facebook AI Similarity Search) is an open-source library developed by Meta (formerly Facebook) for efficient similarity search and clustering of dense vectors. It is highly optimized for handling large-scale datasets and is widely used in applications such as recommendation systems, information retrieval, and natural language processing.

FAISS supports both exact and approximate nearest neighbor (ANN) search and is designed to work efficiently on both CPUs and GPUs.

Key Features of FAISS

1. High Performance:

   • Supports multi-threaded computation for large-scale vector searches.
   • Optimized for GPUs using CUDA for significant speed-ups.

2. Scalability:

   • Handles datasets containing millions or billions of vectors efficiently.

3. Versatile Indexes:

   • Offers various index types for exact and approximate searches, such as IndexFlatL2, IndexIVFFlat, and IndexHNSW.

4. Distance Metrics:

   • Supports multiple distance metrics like L2 (Euclidean distance) and cosine similarity.

Installing FAISS

To get started with FAISS, install it using pip: ```bash pip install faiss-cpu

For GPU support:

pip install faiss-gpu ```

Examples of Using FAISS

1. Exact Nearest Neighbor Search

The simplest use case of FAISS is performing an exact nearest neighbor search using L2 (Euclidean) distance.

import numpy as np
import faiss

# Generate random data
d = 128  # Dimensionality of vectors
nb = 10000  # Number of database vectors
nq = 5  # Number of query vectors

# Random database and query vectors
np.random.seed(0)
db_vectors = np.random.random((nb, d)).astype('float32')
query_vectors = np.random.random((nq, d)).astype('float32')

# Create a FAISS index for exact search
index = faiss.IndexFlatL2(d)  # L2 is the Euclidean distance
print("Is the index trained?", index.is_trained)

# Add database vectors to the index
index.add(db_vectors)
print(f"Number of vectors in the index: {index.ntotal}")

# Perform the search
k = 4  # Number of nearest neighbors to retrieve
distances, indices = index.search(query_vectors, k)

print("Distances:\n", distances)
print("Indices:\n", indices)

Output

This code will output the distances and indices of the k nearest neighbors for each query vector.

2. Approximate Nearest Neighbor Search

FAISS supports approximate search using indexes like IndexIVFFlat for faster searches on large datasets.

# Define an IVF index (Inverted File Index)
nlist = 100  # Number of clusters
quantizer = faiss.IndexFlatL2(d)  # The quantizer for clustering
ivf_index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)

# Train the index (required for IVF indexes)
ivf_index.train(db_vectors)
ivf_index.add(db_vectors)

# Perform the search
ivf_index.nprobe = 10  # Number of clusters to search
distances, indices = ivf_index.search(query_vectors, k)

print("Distances:\n", distances)
print("Indices:\n", indices)

Key Notes

• nlist: Controls the number of clusters; higher values improve accuracy but reduce speed.
• nprobe: Controls the number of clusters searched during query; higher values improve accuracy but reduce speed.

3. Cosine Similarity Search

FAISS natively supports L2 distance, but cosine similarity can be implemented by normalizing the vectors.

# Normalize the vectors to have unit norm
db_vectors = db_vectors / np.linalg.norm(db_vectors, axis=1)[:, np.newaxis]
query_vectors = query_vectors / np.linalg.norm(query_vectors, axis=1)[:, np.newaxis]

# Create a FAISS index
index = faiss.IndexFlatIP(d)  # Inner Product for cosine similarity
index.add(db_vectors)

# Perform the search
distances, indices = index.search(query_vectors, k)

print("Cosine Similarity Scores:\n", distances)
print("Indices:\n", indices)

4. Using FAISS with GPUs

FAISS can leverage GPUs for faster computation by simply transferring the index to GPU.

# Create a FAISS index and move it to GPU
gpu_index = faiss.index_cpu_to_gpu(faiss.StandardGpuResources(), 0, index)

# Perform the search on GPU
distances, indices = gpu_index.search(query_vectors, k)

print("Distances on GPU:\n", distances)
print("Indices on GPU:\n", indices)

5. Saving and Loading an Index

You can save and load FAISS indexes to disk for reuse.

# Save the index
faiss.write_index(index, "example.index")

# Load the index
loaded_index = faiss.read_index("example.index")
distances, indices = loaded_index.search(query_vectors, k)

print("Loaded Index Results:\n", distances)

Choosing the Right Index

1. IndexFlatL2:

   • Exact search using L2 distance.
   • Suitable for small datasets or when accuracy is critical.

2. IndexIVFFlat:

   • Approximate search using inverted files.
   • Ideal for large datasets when speed is important.

3. IndexHNSW:

   • Approximate search using hierarchical navigable small world graphs.
   • Balances accuracy and speed.

4. IndexFlatIP:

   • Exact search using inner product (useful for cosine similarity).

Use Cases of FAISS

1. Recommendation Systems:

   • Match users with similar profiles or products with similar descriptions.

2. Image Retrieval:

   • Find visually similar images by comparing image feature embeddings.

3. Text Embedding Search:

   • Efficiently search large text corpora using embeddings from models like BERT or OpenAI.

4. Clustering:

   • Use FAISS for k-means clustering of high-dimensional data.

Conclusion

FAISS is a powerful and flexible tool for high-performance similarity search and clustering. Its ability to handle large-scale datasets with efficiency makes it invaluable in applications ranging from search engines to machine learning pipelines. By combining its features with GPU acceleration, FAISS becomes an indispensable tool for handling large-scale vector search problems.