faiss Documentation

File: README.md Copy Chapter

Faiss

Faiss is a library for efficient similarity search and clustering of dense vectors. It contains algorithms that search in sets of vectors of any size, up to ones that possibly do not fit in RAM. It also contains supporting code for evaluation and parameter tuning. Faiss is written in C++ with complete wrappers for Python/numpy. Some of the most useful algorithms are implemented on the GPU. It is developed primarily at Meta's Fundamental AI Research group.

News Copy Chapter

See CHANGELOG.md for detailed information about latest features.

Introduction Copy Chapter

Faiss contains several methods for similarity search. It assumes that the instances are represented as vectors and are identified by an integer, and that the vectors can be compared with L2 (Euclidean) distances or dot products. Vectors that are similar to a query vector are those that have the lowest L2 distance or the highest dot product with the query vector. It also supports cosine similarity, since this is a dot product on normalized vectors.

Some of the methods, like those based on binary vectors and compact quantization codes, solely use a compressed representation of the vectors and do not require to keep the original vectors. This generally comes at the cost of a less precise search but these methods can scale to billions of vectors in main memory on a single server. Other methods, like HNSW and NSG add an indexing structure on top of the raw vectors to make searching more efficient.

The GPU implementation can accept input from either CPU or GPU memory. On a server with GPUs, the GPU indexes can be used a drop-in replacement for the CPU indexes (e.g., replace IndexFlatL2 with GpuIndexFlatL2) and copies to/from GPU memory are handled automatically. Results will be faster however if both input and output remain resident on the GPU. Both single and multi-GPU usage is supported.

Installing Copy Chapter

Faiss comes with precompiled libraries for Anaconda in Python, see faiss-cpu, faiss-gpu and faiss-gpu-cuvs. The library is mostly implemented in C++, the only dependency is a BLAS implementation. Optional GPU support is provided via CUDA or AMD ROCm, and the Python interface is also optional. The backend GPU implementations of NVIDIA cuVS can also be enabled optionally. It compiles with cmake. See INSTALL.md for details.

How Faiss works Copy Chapter

Faiss is built around an index type that stores a set of vectors, and provides a function to search in them with L2 and/or dot product vector comparison. Some index types are simple baselines, such as exact search. Most of the available indexing structures correspond to various trade-offs with respect to

• search time
• search quality
• memory used per index vector
• training time
• adding time
• need for external data for unsupervised training

The optional GPU implementation provides what is likely (as of March 2017) the fastest exact and approximate (compressed-domain) nearest neighbor search implementation for high-dimensional vectors, fastest Lloyd's k-means, and fastest small k-selection algorithm known. The implementation is detailed here.

Full documentation of Faiss Copy Chapter

The following are entry points for documentation:

• the full documentation can be found on the wiki page, including a tutorial, a FAQ and a troubleshooting section
• the doxygen documentation gives per-class information extracted from code comments
• to reproduce results from our research papers, Polysemous codes and Billion-scale similarity search with GPUs, refer to the benchmarks README. For
  Link and code: Fast indexing with graphs and compact regression codes, see the link_and_code README

Authors Copy Chapter

The main authors of Faiss are:

• Hervé Jégou initiated the Faiss project and wrote its first implementation
• Matthijs Douze implemented most of the CPU Faiss
• Jeff Johnson implemented all of the GPU Faiss
• Lucas Hosseini implemented the binary indexes and the build system
• Chengqi Deng implemented NSG, NNdescent and much of the additive quantization code.
• Alexandr Guzhva many optimizations: SIMD, memory allocation and layout, fast decoding kernels for vector codecs, etc.
• Gergely Szilvasy build system, benchmarking framework.

Reference Copy Chapter

References to cite when you use Faiss in a research paper:

@article{douze2024faiss,
      title={The Faiss library},
      author={Matthijs Douze and Alexandr Guzhva and Chengqi Deng and Jeff Johnson and Gergely Szilvasy and Pierre-Emmanuel Mazaré and Maria Lomeli and Lucas Hosseini and Hervé Jégou},
      year={2024},
      eprint={2401.08281},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

For the GPU version of Faiss, please cite:

@article{johnson2019billion,
  title={Billion-scale similarity search with {GPUs}},
  author={Johnson, Jeff and Douze, Matthijs and J{\'e}gou, Herv{\'e}},
  journal={IEEE Transactions on Big Data},
  volume={7},
  number={3},
  pages={535--547},
  year={2019},
  publisher={IEEE}
}

Join the Faiss community Copy Chapter

For public discussion of Faiss or for questions, visit https://github.com/facebookresearch/faiss/discussions.

We monitor the issues page of the repository.
You can report bugs, ask questions, etc.

Legal Copy Chapter

Faiss is MIT-licensed, refer to the LICENSE file in the top level directory.

Copyright © Meta Platforms, Inc.

File: benchs/bench_all_ivf/README.md Copy Chapter

Benchmark of IVF variants

This is a benchmark of IVF index variants, looking at compression vs. speed vs. accuracy.
The results are in this wiki chapter

The code is organized as:

• datasets.py: code to access the datafiles, compute the ground-truth and report accuracies

• bench_all_ivf.py: evaluate one type of inverted file

• run_on_cluster_generic.bash: call bench_all_ivf.py for all tested types of indices.
  Since the number of experiments is quite large the script is structured so that the benchmark can be run on a cluster.

• parse_bench_all_ivf.py: make nice tradeoff plots from all the results.

The code depends on Faiss and can use 1 to 8 GPUs to do the k-means clustering for large vocabularies.

It was run in October 2018 for the results in the wiki.

File: benchs/distributed_ondisk/README.md Copy Chapter

Distributed on-disk index for 1T-scale datasets

This is code corresponding to the description in Indexing 1T vectors.
All the code is in python 3 (and not compatible with Python 2).
The current code uses the Deep1B dataset for demonstration purposes, but can scale to 1000x larger.
To run it, download the Deep1B dataset as explained here, and edit paths to the dataset in the scripts.

The cluster commands are written for the Slurm batch scheduling system.
Hopefully, changing to another type of scheduler should be quite straightforward.

Distributed k-means Copy Chapter

To cluster 500M vectors to 10M centroids, it is useful to have a distributed k-means implementation.
The distribution simply consists in splitting the training vectors across machines (servers) and have them do the assignment.
The master/client then synthesizes the results and updates the centroids.

The distributed k-means implementation here is based on 3 files:

• distributed_kmeans.py contains the k-means implementation.
  The main loop of k-means is re-implemented in python but follows closely the Faiss C++ implementation, and should not be significantly less efficient.
  It relies on a DatasetAssign object that does the assignment to centroids, which is the bulk of the computation.
  The object can be a Faiss CPU index, a GPU index or a set of remote GPU or CPU indexes.

• run_on_cluster.bash contains the shell code to run the distributed k-means on a cluster.

The distributed k-means works with a Python install that contains faiss and scipy (for sparse matrices).
It clusters the training data of Deep1B, this can be changed easily to any file in fvecs, bvecs or npy format that contains the training set.
The training vectors may be too large to fit in RAM, but they are memory-mapped so that should not be a problem.
The file is also assumed to be accessible from all server machines with eg. a distributed file system.

Local tests Copy Section

Edit distributed_kmeans.py to point testdata to your local copy of the dataset.

Then, 4 levels of sanity check can be run:

# reference Faiss C++ run
python distributed_kmeans.py --test 0
# using the Python implementation
python distributed_kmeans.py --test 1
# use the dispatch object (on local datasets)
python distributed_kmeans.py --test 2
# same, with GPUs
python distributed_kmeans.py --test 3

The output should look like This gist.

Distributed sanity check Copy Section

To run the distributed k-means, distributed_kmeans.py has to be run both on the servers (--server option) and client sides (--client option).
Edit the top of run_on_cluster.bash to set the path of the data to cluster.

Sanity checks can be run with

# non distributed baseline
bash run_on_cluster.bash test_kmeans_0
# using all the machine's GPUs
bash run_on_cluster.bash test_kmeans_1
# distributed run, with one local server per GPU
bash run_on_cluster.bash test_kmeans_2

The test test_kmeans_2 simulates a distributed run on a single machine by starting one server process per GPU and connecting to the servers via the rpc protocol.
The output should look like this gist.

Distributed run Copy Section

The way the script can be distributed depends on the cluster's scheduling system.
Here we use Slurm, but it should be relatively easy to adapt to any scheduler that can allocate a set of machines and start the same executable on all of them.

The command

bash run_on_cluster.bash slurm_distributed_kmeans

asks SLURM for 5 machines with 4 GPUs each with the srun command.
All 5 machines run the script with the slurm_within_kmeans_server option.
They determine the number of servers and their own server id via the SLURM_NPROCS and SLURM_PROCID environment variables.

All machines start distributed_kmeans.py in server mode for the slice of the dataset they are responsible for.

In addition, the machine #0 also starts the client.
The client knows who are the other servers via the variable SLURM_JOB_NODELIST.
It connects to all clients and performs the clustering.

The output should look like this gist.

Run used for deep1B Copy Section

For the real run, we run the clustering on 50M vectors to 1M centroids.
This is just a matter of using as many machines / GPUs as possible in setting the output centroids with the --out filename option.
Then run

bash run_on_cluster.bash deep1b_clustering

The last lines of output read like:

Iteration 19 (898.92 s, search 875.71 s): objective=1.33601e+07 imbalance=1.303 nsplit=0
 0: writing centroids to /checkpoint/matthijs/ondisk_distributed/1M_centroids.npy

This means that the total training time was 899s, of which 876s were used for computation.
However, the computation includes the I/O overhead to the assignment servers.
In this implementation, the overhead of transmitting the data is non-negligible and so is the centroid computation stage.
This is due to the inefficient Python implementation and the RPC protocol that is not optimized for broadcast / gather (like MPI).
However, it is a simple implementation that should run on most clusters.

Making the trained index Copy Chapter

After the centroids are obtained, an empty trained index must be constructed.
This is done by:

• applying a pre-processing stage (a random rotation) to balance the dimensions of the vectors. This can be done after clustering, the clusters are just rotated as well.

• wrapping the centroids into a HNSW index to speed up the CPU-based assignment of vectors

• training the 6-bit scalar quantizer used to encode the vectors

This is performed by the script make_trained_index.py.

Building the index by slices Copy Chapter

We call the slices "vslices" as they are vertical slices of the big matrix, see explanation in the wiki section Split across database partitions.

The script make_index_vslice.py makes an index for a subset of the vectors of the input data and stores it as an independent index.
There are 200 slices of 5M vectors each for Deep1B.
It can be run in a brute-force parallel fashion, there is no constraint on ordering.
To run the script in parallel on a slurm cluster, use:

bash run_on_cluster.bash make_index_vslices

For a real dataset, the data would be read from a DBMS.
In that case, reading the data and indexing it in parallel is worthwhile because reading is very slow.

Splitting across inverted lists Copy Chapter

The 200 slices need to be merged together.
This is done with the script merge_to_ondisk.py, that memory maps the 200 vertical slice indexes, extracts a subset of the inverted lists and writes them to a contiguous horizontal slice.
We slice the inverted lists into 50 horizontal slices.
This is run with

bash run_on_cluster.bash make_index_hslices

Querying the index Copy Chapter

At this point the index is ready.
The horizontal slices need to be loaded in the right order and combined into an index to be usable.
This is done in the combined_index.py script.
It provides a CombinedIndexDeep1B object that contains an index object that can be searched.
To test, run:

python combined_index.py

The output should look like:

(faiss_1.5.2) matthijs@devfair0144:~/faiss_versions/faiss_1Tcode/faiss/benchs/distributed_ondisk$ python combined_index.py
reading /checkpoint/matthijs/ondisk_distributed//hslices/slice49.faissindex
loading empty index /checkpoint/matthijs/ondisk_distributed/trained.faissindex
replace invlists
loaded index of size  1000000000
nprobe=1 1-recall@1=0.2904 t=12.35s
nnprobe=10 1-recall@1=0.6499 t=17.67s
nprobe=100 1-recall@1=0.8673 t=29.23s
nprobe=1000 1-recall@1=0.9132 t=129.58s

ie. searching is a lot slower than from RAM.

Distributed query Copy Chapter

To reduce the bandwidth required from the machine that does the queries, it is possible to split the search across several search servers.
This way, only the effective results are returned to the main machine.

The search client and server are implemented in search_server.py.
It can be used as a script to start a search server for CombinedIndexDeep1B or as a module to load the clients.

The search servers can be started with

bash run_on_cluster.bash run_search_servers

(adjust to the number of servers that can be used).

Then an example of search client is distributed_query_demo.py.
It connects to the servers and assigns subsets of inverted lists to visit to each of them.

A typical output is this gist.
The number in MiB indicates the amount of data that is read from disk to perform the search.
In this case, the scale of the dataset is too small for the distributed search to have much impact, but on datasets > 10x larger, the difference becomes more significant.

Conclusion Copy Chapter

This code contains the core components to make an index that scales up to 1T vectors.
There are a few simplifications wrt. the index that was effectively used in Indexing 1T vectors.

File: benchs/link_and_code/README.md Copy Chapter

README for the link & code implementation

What is this? Copy Chapter

Link & code is an indexing method that combines HNSW indexing with
compression and exploits the neighborhood structure of the similarity
graph to improve the reconstruction. It is described in

@inproceedings{link_and_code,
   author = {Matthijs Douze and Alexandre Sablayrolles and Herv\'e J\'egou},
   title = {Link and code: Fast indexing with graphs and compact regression codes},
   booktitle = {CVPR},
   year = {2018}
}

ArXiV here

The necessary code for this paper was removed from Faiss in version 1.8.0.
For a functioning version, use Faiss 1.7.4.

File: benchs/README.md Copy Chapter

Benchmarking scripts

This directory contains benchmarking scripts that can reproduce the
numbers reported in the two papers

@inproceedings{DJP16,
  Author = {Douze, Matthijs and J{\'e}gou, Herv{\'e} and Perronnin, Florent},
  Booktitle = "ECCV",
  Organization = {Springer},
  Title = {Polysemous codes},
  Year = {2016}
}

and

@inproceedings{JDJ17,
   Author = {Jeff Johnson and Matthijs Douze and Herv{\'e} J{\'e}gou},
   journal = {arXiv:1702.08734},
   Title = {Billion-scale similarity search with GPUs},
   Year = {2017},
}

Note that the numbers (especially timings) change slightly due to changes in the implementation, different machines, etc.

The scripts are self-contained. They depend only on Faiss and external training data that should be stored in sub-directories.

SIFT1M experiments Copy Chapter

The script bench_polysemous_sift1m.py reproduces the numbers in
Figure 3 from the "Polysemous" paper.

Getting SIFT1M Copy Section

To run it, please download the ANN_SIFT1M dataset from

http://corpus-texmex.irisa.fr/

and unzip it to the subdirectory sift1M.

Result Copy Section

The output looks like:

PQ training on 100000 points, remains 0 points: training polysemous on centroids
add vectors to index
PQ baseline        7.517 ms per query, R@1 0.4474
Polysemous 64      9.875 ms per query, R@1 0.4474
Polysemous 62      8.358 ms per query, R@1 0.4474
Polysemous 58      5.531 ms per query, R@1 0.4474
Polysemous 54      3.420 ms per query, R@1 0.4478
Polysemous 50      2.182 ms per query, R@1 0.4475
Polysemous 46      1.621 ms per query, R@1 0.4408
Polysemous 42      1.448 ms per query, R@1 0.4174
Polysemous 38      1.331 ms per query, R@1 0.3563
Polysemous 34      1.334 ms per query, R@1 0.2661
Polysemous 30      1.272 ms per query, R@1 0.1794

Experiments on 1B elements dataset Copy Chapter

The script bench_polysemous_1bn.py reproduces a few experiments on
two datasets of size 1B from the Polysemous codes" paper.

Getting BIGANN Copy Section

Download the four files of ANN_SIFT1B from
http://corpus-texmex.irisa.fr/ to subdirectory bigann/

Getting Deep1B Copy Section

The ground-truth and queries are available here

https://yadi.sk/d/11eDCm7Dsn9GA

For the learning and database vectors, use the script

https://github.com/arbabenko/GNOIMI/blob/master/downloadDeep1B.py

to download the data to subdirectory deep1b/, then concatenate the
database files to base.fvecs and the training files to learn.fvecs

Running the experiments Copy Section

These experiments are quite long. To support resuming, the script
stores the result of training to a temporary directory, /tmp/bench_polysemous.

The script bench_polysemous_1bn.py takes at least two arguments:

• the dataset name: SIFT1000M (aka SIFT1B, aka BIGANN) or Deep1B. SIFT1M, SIFT2M,... are also supported to make subsets of for small experiments (note that SIFT1M as a subset of SIFT1B is not the same as the SIFT1M above)

• the type of index to build, which should be a valid index_factory key (see below for examples)

• the remaining arguments are parsed as search-time parameters.

Experiments of Table 2 Copy Section

The IMI*+PolyD+ADC results in Table 2 can be reproduced with (for 16 bytes):

python bench_polysemous_1bn.par SIFT1000M IMI2x12,PQ16 nprobe=16,max_codes={10000,30000},ht={44..54}

Training takes about 2 minutes and adding vectors to the dataset
takes 3.1 h. These operations are multithreaded. Note that in the command
above, we use bash's brace expansion to set a grid of parameters.

The search is not multithreaded, and the output looks like:

/* Detailed source-code truncated for AI context efficiency. */

The result reported in table 2 is the one for which the %pass (percentage of code comparisons that pass the Hamming check) is around 20%, which occurs for Hamming threshold ht=48.

The 8-byte results can be reproduced with the factory key IMI2x12,PQ8

Experiments of the appendix Copy Section

The experiments in the appendix are only in the ArXiv version of the paper (table 3).

python bench_polysemous_1bn.py SIFT1000M OPQ8_64,IMI2x13,PQ8 nprobe={1,2,4,8,16,32,64,128},ht={20,24,26,28,30}

                        R@1    R@10   R@100     time    %pass
nprobe=1,ht=20          0.0351 0.0616 0.0751    0.158   19.01
...
nprobe=32,ht=28         0.1256 0.3563 0.5026    0.561   52.61
...

Here again the runs are not exactly the same but the original result was obtained from nprobe=32,ht=28.

For Deep1B, we used a simple version of auto-tuning to sweep through the set of operating points:

python bench_polysemous_1bn.py Deep1B OPQ20_80,IMI2x14,PQ20 autotune
...
Done in 4067.555 s, available OPs:
Parameters                                1-R@1     time
                                          0.0000    0.000
nprobe=1,ht=22,max_codes=256              0.0215    3.115
nprobe=1,ht=30,max_codes=256              0.0381    3.120
...
nprobe=512,ht=68,max_codes=524288         0.4478   36.903
nprobe=1024,ht=80,max_codes=131072        0.4557   46.363
nprobe=1024,ht=78,max_codes=262144        0.4616   61.939
...

The original results were obtained with nprobe=1024,ht=66,max_codes=262144.

GPU experiments Copy Chapter

The benchmarks below run 1 or 4 Titan X GPUs and reproduce the results of the "GPU paper". They are also a good starting point on how to use GPU Faiss.

Search on SIFT1M Copy Section

See above on how to get SIFT1M into subdirectory sift1M/. The script bench_gpu_sift1m.py reproduces the "exact k-NN time" plot in the ArXiv paper, and the SIFT1M numbers.

The output is:

============ Exact search
add vectors to index
warmup
benchmark
k=1 0.715 s, R@1 0.9914
k=2 0.729 s, R@1 0.9935
k=4 0.731 s, R@1 0.9935
k=8 0.732 s, R@1 0.9935
k=16 0.742 s, R@1 0.9935
k=32 0.737 s, R@1 0.9935
k=64 0.753 s, R@1 0.9935
k=128 0.761 s, R@1 0.9935
k=256 0.799 s, R@1 0.9935
k=512 0.975 s, R@1 0.9935
k=1024 1.424 s, R@1 0.9935
============ Approximate search
train
WARNING clustering 100000 points to 4096 centroids: please provide at least 159744 training points
add vectors to index
WARN: increase temp memory to avoid cudaMalloc, or decrease query/add size (alloc 256000000 B, highwater 256000000 B)
warmup
benchmark
nprobe=   1 0.043 s recalls= 0.3909 0.4312 0.4312
nprobe=   2 0.040 s recalls= 0.5041 0.5636 0.5636
nprobe=   4 0.048 s recalls= 0.6048 0.6897 0.6897
nprobe=   8 0.064 s recalls= 0.6879 0.8028 0.8028
nprobe=  16 0.088 s recalls= 0.7534 0.8940 0.8940
nprobe=  32 0.134 s recalls= 0.7957 0.9549 0.9550
nprobe=  64 0.224 s recalls= 0.8125 0.9833 0.9834
nprobe= 128 0.395 s recalls= 0.8205 0.9953 0.9954
nprobe= 256 0.717 s recalls= 0.8227 0.9993 0.9994
nprobe= 512 1.348 s recalls= 0.8228 0.9999 1.0000

The run produces two warnings:

• the clustering complains that it does not have enough training data, there is not much we can do about this.

• the add() function complains that there is an inefficient memory allocation, but this is a concern only when it happens often, and we are not benchmarking the add time anyways.

To index small datasets, it is more efficient to use a GpuIVFFlat, which just stores the full vectors in the inverted lists. We did not mention this in the paper because it is not as scalable. To experiment with this setting, change the index_factory string from "IVF4096,PQ64" to "IVF16384,Flat". This gives:

nprobe=   1 0.025 s recalls= 0.4084 0.4105 0.4105
nprobe=   2 0.033 s recalls= 0.5235 0.5264 0.5264
nprobe=   4 0.033 s recalls= 0.6332 0.6367 0.6367
nprobe=   8 0.040 s recalls= 0.7358 0.7403 0.7403
nprobe=  16 0.049 s recalls= 0.8273 0.8324 0.8324
nprobe=  32 0.068 s recalls= 0.8957 0.9024 0.9024
nprobe=  64 0.104 s recalls= 0.9477 0.9549 0.9549
nprobe= 128 0.174 s recalls= 0.9760 0.9837 0.9837
nprobe= 256 0.299 s recalls= 0.9866 0.9944 0.9944
nprobe= 512 0.527 s recalls= 0.9907 0.9987 0.9987

Clustering on MNIST8m Copy Section

To get the "infinite MNIST dataset", follow the instructions on Léon Bottou's website. The script assumes the file mnist8m-patterns-idx3-ubyte is in subdirectory mnist8m

The script kmeans_mnist.py produces the following output:

python kmeans_mnist.py 1 256
...
Clustering 8100000 points in 784D to 256 clusters, redo 1 times, 20 iterations
  Preprocessing in 7.94526 s
  Iteration 19 (131.697 s, search 114.78 s): objective=1.44881e+13 imbalance=1.05963 nsplit=0
final objective: 1.449e+13
total runtime: 140.615 s

search on SIFT1B Copy Section

The script bench_gpu_1bn.py runs multi-gpu searches on the two 1-billion vector datasets we considered. It is more complex than the previous scripts, because it supports many search options and decomposes the dataset build process in Python to exploit the best possible CPU/GPU parallelism and GPU distribution.

Even on multiple GPUs, building the 1B datasets can last several hours. It is often a good idea to validate that everything is working fine on smaller datasets like SIFT1M, SIFT2M, etc.

The search results on SIFT1B in the "GPU paper" can be obtained with

python bench_gpu_1bn.py SIFT1000M OPQ8_32,IVF262144,PQ8 -nnn 10 -ngpu 1 -tempmem $[1536*1024*1024]
...
0/10000 (0.024 s)      probe=1  : 0.161 s 1-R@1: 0.0752 1-R@10: 0.1924
0/10000 (0.005 s)      probe=2  : 0.150 s 1-R@1: 0.0964 1-R@10: 0.2693
0/10000 (0.005 s)      probe=4  : 0.153 s 1-R@1: 0.1102 1-R@10: 0.3328
0/10000 (0.005 s)      probe=8  : 0.170 s 1-R@1: 0.1220 1-R@10: 0.3827
0/10000 (0.005 s)      probe=16 : 0.196 s 1-R@1: 0.1290 1-R@10: 0.4151
0/10000 (0.006 s)      probe=32 : 0.244 s 1-R@1: 0.1314 1-R@10: 0.4345
0/10000 (0.006 s)      probe=64 : 0.353 s 1-R@1: 0.1332 1-R@10: 0.4461
0/10000 (0.005 s)      probe=128: 0.587 s 1-R@1: 0.1341 1-R@10: 0.4502
0/10000 (0.006 s)      probe=256: 1.160 s 1-R@1: 0.1342 1-R@10: 0.4511

We use the -tempmem option to reduce the temporary memory allocation to 1.5G, otherwise the dataset does not fit in GPU memory

search on Deep1B Copy Section

The same script generates the GPU search results on Deep1B.

python bench_gpu_1bn.py  Deep1B OPQ20_80,IVF262144,PQ20 -nnn 10 -R 2 -ngpu 4 -altadd -noptables -tempmem $[1024*1024*1024]
...

0/10000 (0.115 s)      probe=1  : 0.239 s 1-R@1: 0.2387 1-R@10: 0.3420
0/10000 (0.006 s)      probe=2  : 0.103 s 1-R@1: 0.3110 1-R@10: 0.4623
0/10000 (0.005 s)      probe=4  : 0.105 s 1-R@1: 0.3772 1-R@10: 0.5862
0/10000 (0.005 s)      probe=8  : 0.116 s 1-R@1: 0.4235 1-R@10: 0.6889
0/10000 (0.005 s)      probe=16 : 0.133 s 1-R@1: 0.4517 1-R@10: 0.7693
0/10000 (0.005 s)      probe=32 : 0.168 s 1-R@1: 0.4713 1-R@10: 0.8281
0/10000 (0.005 s)      probe=64 : 0.238 s 1-R@1: 0.4841 1-R@10: 0.8649
0/10000 (0.007 s)      probe=128: 0.384 s 1-R@1: 0.4900 1-R@10: 0.8816
0/10000 (0.005 s)      probe=256: 0.736 s 1-R@1: 0.4933 1-R@10: 0.8912

Here we are a bit tight on memory so we disable precomputed tables (-noptables) and restrict the amount of temporary memory. The -altadd option avoids GPU memory overflows during add.

knn-graph on Deep1B Copy Section

The same script generates the KNN-graph on Deep1B. Note that the inverted file from above will not be re-used because the training sets are different. For the knngraph, the script will first do a pass over the whole dataset to compute the ground-truth knn for a subset of 10k nodes, for evaluation.

/* Detailed source-code truncated for AI context efficiency. */

Additional benchmarks

This directory also contains certain additional benchmarks (and serve as an additional source of examples of how to use the Faiss code).
Certain tests / benchmarks might be outdated.

• bench_6bit_codec.cpp - tests vector codecs for SQ6 quantization on a synthetic dataset
• bench_cppcontrib_sa_decode.cpp - benchmarks specialized kernels for vector codecs for PQ, IVFPQ and Resudial+PQ on a synthetic dataset
• bench_for_interrupt.py - evaluates the impact of the interrupt callback handler (which can be triggered from Python code)
• bench_hamming_computer.cpp - specialized implementations for Hamming distance computations
• bench_heap_replace.cpp - benchmarks different implementations of certain calls for a Heap data structure
• bench_hnsw.py - benchmarks HNSW in combination with other ones for SIFT1M dataset
• bench_hnsw_prune_headroom.py - benchmarks HNSW prune_headroom recall and build time impact
• bench_index_flat.py - benchmarks IndexFlatL2 on a synthetic dataset
• bench_index_pq.py - benchmarks PQ on SIFT1M dataset
• bench_ivf_fastscan_single_query.py - benchmarks a single query for different nprobe levels for IVF{nlist},PQ{M}x4fs on BIGANN dataset
• bench_ivf_fastscan.py - compares IVF{nlist},PQ{M}x4fs against other indices on SIFT1M dataset
• bench_ivf_selector.cpp - checks the possible overhead when using faiss::IDSelectorAll interface
• bench_pairwise_distances.py - benchmarks pairwise distance computation between two synthetic datasets
• bench_partition.py - benchmarks partitioning functions
• bench_pq_tables.py - benchmarks ProductQuantizer.compute_inner_prod_tables() and ProductQuantizer.compute_distance_tables() calls
• bench_quantizer.py - benchmarks various quantizers for SIFT1M, Deep1B, BigANN datasets
• bench_scalar_quantizer.py - benchmarks IVF+SQ on a Sift1M dataset
• bench_vector_ops.py - benchmarks dot product and distances computations on a synthetic dataset

File: contrib/torch/README.md Copy Chapter

The Torch contrib

This contrib directory contains a few Pytorch routines that
are useful for similarity search. They do not necessarily depend on Faiss.

The code is designed to work with CPU and GPU tensors.

File: contrib/README.md Copy Chapter

The contrib modules

The contrib directory contains helper modules for Faiss for various tasks.

Code structure Copy Chapter

The contrib directory gets compiled in the module faiss.contrib.
Note that although some of the modules may depend on additional modules (eg. GPU Faiss, pytorch, hdf5), they are not necessarily compiled in to avoid adding dependencies. It is the user's responsibility to provide them.

List of contrib modules Copy Chapter

rpc.py Copy Section

A very simple Remote Procedure Call library, where function parameters and results are pickled, for use with client_server.py

client_server.py Copy Section

The server handles requests to a Faiss index. The client calls the remote index.
This is mainly to shard datasets over several machines, see Distributed index

ondisk.py Copy Section

Encloses the main logic to merge indexes into an on-disk index.
See On-disk storage

exhaustive_search.py Copy Section

Computes the ground-truth search results for a dataset that possibly does not fit in RAM. Uses GPU if available.
Tested in tests/test_contrib.TestComputeGT

torch_utils.py Copy Section

Interoperability functions for pytorch and Faiss: Importing this will allow pytorch Tensors (CPU or GPU) to be used as arguments to Faiss indexes and other functions. Torch GPU tensors can only be used with Faiss GPU indexes. If this is imported with a package that supports Faiss GPU, the necessary stream synchronization with the current pytorch stream will be automatically performed.

Numpy ndarrays can continue to be used in the Faiss python interface after importing this file. All arguments must be uniformly either numpy ndarrays or Torch tensors; no mixing is allowed.

Tested in tests/test_contrib_torch.py (CPU) and gpu/test/test_contrib_torch_gpu.py (GPU).

inspect_tools.py Copy Section

Functions to inspect C++ objects wrapped by SWIG. Most often this just means reading
fields and converting them to the proper python array.

ivf_tools.py Copy Section

A few functions to override the coarse quantizer in IVF, providing additional flexibility for assignment.

datasets.py Copy Section

(may require h5py)

Definition of how to access data for some standard datasets.

factory_tools.py Copy Section

Functions related to factory strings.

evaluation.py Copy Section

A few non-trivial evaluation functions for search results

clustering.py Copy Section

Contains:

• a Python implementation of kmeans, that can be used for special datatypes (eg. sparse matrices).

• a 2-level clustering routine and a function that can apply it to train an IndexIVF

big_batch_search.py Copy Section

Search IVF indexes with one centroid after another. Useful for large
databases that do not fit in RAM and a large number of queries.

File: demos/offline_ivf/README.md Copy Chapter

Offline IVF

This folder contains the code for the offline ivf algorithm powered by faiss big batch search.

Create a conda env:

conda create --name oivf python=3.10

conda activate oivf

conda install -c pytorch/label/nightly -c nvidia faiss-gpu=1.7.4

conda install tqdm

conda install pyyaml

conda install -c conda-forge submitit

Run book Copy Chapter

1. Optionally shard your dataset (see create_sharded_dataset.py) and create the corresponding yaml file config_ssnpp.yaml. You can use generate_config.py by specifying the root directory of your dataset and the files with the data shards

python generate_config

2. Run the train index command

python run.py --command train_index --config config_ssnpp.yaml --xb ssnpp_1B

3. Run the index-shard command so it produces sharded indexes, required for the search step

python run.py --command index_shard --config config_ssnpp.yaml --xb ssnpp_1B

6. Send jobs to the cluster to run search

python run.py --command search --config config_ssnpp.yaml --xb ssnpp_1B --cluster_run --partition

Remarks about the search command: it is assumed that the database vectors are the query vectors when performing the search step.
a. If the query vectors are different than the database vectors, it should be passed in the xq argument
b. A new dataset needs to be prepared (step 1) before passing it to the query vectors argument –xq

python run.py --command search --config config_ssnpp.yaml --xb ssnpp_1B --xq <QUERIES_DATASET_NAME>

6. We can always run the consistency-check for sanity checks!

python run.py --command consistency_check --config config_ssnpp.yaml --xb ssnpp_1B

File: demos/rocksdb_ivf/README.md Copy Chapter

Storing Faiss inverted lists in RocksDB

Demo of storing the inverted lists of any IVF index in RocksDB or any similar key-value store which supports the prefix scan operation.

How to build

We use conda to create the build environment for simplicity. Only tested on Linux x86.

conda create -n rocksdb_ivf
conda activate rocksdb_ivf
conda install pytorch::faiss-cpu conda-forge::rocksdb cmake make gxx_linux-64 sysroot_linux-64
cd ~/faiss/demos/rocksdb_ivf
cmake -B build .
make -C build -j$(nproc)

Run the example

cd ~/faiss/demos/rocksdb_ivf/build
./demo_rocksdb_ivf test_db

File: demos/README.md Copy Chapter

Demos for a few Faiss functionalities

demo_auto_tune.py Copy Chapter

Demonstrates the auto-tuning functionality of Faiss

demo_ondisk_ivf.py Copy Chapter

Shows how to construct a Faiss index that stores the inverted file
data on disk, eg. when it does not fit in RAM. The script works on a
small dataset (sift1M) for demonstration and proceeds in stages:

0: train on the dataset

1-4: build 4 indexes, each containing 1/4 of the dataset. This can be
done in parallel on several machines

5: merge the 4 indexes into one that is written directly to disk
(needs not to fit in RAM)

6: load and test the index