## File: README.md # 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](https://ai.facebook.com/) group. ## News See [CHANGELOG.md](CHANGELOG.md) for detailed information about latest features. ## Introduction 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 Faiss comes with precompiled libraries for Anaconda in Python, see [faiss-cpu](https://anaconda.org/pytorch/faiss-cpu), [faiss-gpu](https://anaconda.org/pytorch/faiss-gpu) and [faiss-gpu-cuvs](https://anaconda.org/pytorch/faiss-gpu-cuvs). The library is mostly implemented in C++, the only dependency is a [BLAS](https://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms) 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](https://github.com/rapidsai/cuvs) can also be enabled optionally. It compiles with cmake. See [INSTALL.md](INSTALL.md) for details. ## How Faiss works 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](https://arxiv.org/abs/1702.08734). ## Full documentation of Faiss The following are entry points for documentation: - the full documentation can be found on the [wiki page](https://github.com/facebookresearch/faiss/wiki), including a [tutorial](https://github.com/facebookresearch/faiss/wiki/Getting-started), a [FAQ](https://github.com/facebookresearch/faiss/wiki/FAQ) and a [troubleshooting section](https://github.com/facebookresearch/faiss/wiki/Troubleshooting) - the [doxygen documentation](https://faiss.ai/) gives per-class information extracted from code comments - to reproduce results from our research papers, [Polysemous codes](https://arxiv.org/abs/1609.01882) and [Billion-scale similarity search with GPUs](https://arxiv.org/abs/1702.08734), refer to the [benchmarks README](benchs/README.md). For [ Link and code: Fast indexing with graphs and compact regression codes](https://arxiv.org/abs/1804.09996), see the [link_and_code README](benchs/link_and_code) ## Authors The main authors of Faiss are: - [Hervé Jégou](https://github.com/jegou) initiated the Faiss project and wrote its first implementation - [Matthijs Douze](https://github.com/mdouze) implemented most of the CPU Faiss - [Jeff Johnson](https://github.com/wickedfoo) implemented all of the GPU Faiss - [Lucas Hosseini](https://github.com/beauby) implemented the binary indexes and the build system - [Chengqi Deng](https://github.com/KinglittleQ) implemented NSG, NNdescent and much of the additive quantization code. - [Alexandr Guzhva](https://github.com/alexanderguzhva) many optimizations: SIMD, memory allocation and layout, fast decoding kernels for vector codecs, etc. - [Gergely Szilvasy](https://github.com/algoriddle) build system, benchmarking framework. ## Reference 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 For public discussion of Faiss or for questions, visit https://github.com/facebookresearch/faiss/discussions. We monitor the [issues page](https://github.com/facebookresearch/faiss/issues) of the repository. You can report bugs, ask questions, etc. ## Legal Faiss is MIT-licensed, refer to the [LICENSE file](https://github.com/facebookresearch/faiss/blob/main/LICENSE) in the top level directory. Copyright © Meta Platforms, Inc. --- ## File: benchs/bench_all_ivf/README.md # 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](https://github.com/facebookresearch/faiss/wiki/Indexing-1G-vectors) 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 # Distributed on-disk index for 1T-scale datasets This is code corresponding to the description in [Indexing 1T vectors](https://github.com/facebookresearch/faiss/wiki/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](../#getting-deep1b), 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 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`](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`](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 Edit `distributed_kmeans.py` to point `testdata` to your local copy of the dataset. Then, 4 levels of sanity check can be run: ```bash # 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](https://gist.github.com/mdouze/ffa01fe666a9325761266fe55ead72ad). ### Distributed sanity check 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 ```bash # 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](https://gist.github.com/mdouze/5b2dc69b74579ecff04e1686a277d32e). ### Distributed run 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 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](https://gist.github.com/mdouze/8d25e89fb4af5093057cae0f917da6cd). ### Run used for deep1B 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 bash run_on_cluster.bash deep1b_clustering ``` The last lines of output read like: ```bash 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 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`](make_trained_index.py). ## Building the index by slices We call the slices "vslices" as they are vertical slices of the big matrix, see explanation in the wiki section [Split across database partitions](https://github.com/facebookresearch/faiss/wiki/Indexing-1T-vectors#split-across-database-partitions). The script [make_index_vslice.py](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 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 The 200 slices need to be merged together. This is done with the script [merge_to_ondisk.py](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 bash run_on_cluster.bash make_index_hslices ``` ## Querying the index 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](combined_index.py) script. It provides a `CombinedIndexDeep1B` object that contains an index object that can be searched. To test, run: ```bash python combined_index.py ``` The output should look like: ```bash (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 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`](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 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`](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](https://gist.github.com/mdouze/1585b9854a9a2437d71f2b2c3c05c7c5). 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 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](https://github.com/facebookresearch/faiss/wiki/Indexing-1T-vectors). --- ## File: benchs/link_and_code/README.md README for the link & code implementation ========================================= What is this? ------------- 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](https://arxiv.org/abs/1804.09996) 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 # 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 The script [`bench_polysemous_sift1m.py`](bench_polysemous_sift1m.py) reproduces the numbers in Figure 3 from the "Polysemous" paper. ### Getting SIFT1M To run it, please download the ANN_SIFT1M dataset from http://corpus-texmex.irisa.fr/ and unzip it to the subdirectory sift1M. ### Result 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 The script [`bench_polysemous_1bn.py`](bench_polysemous_1bn.py) reproduces a few experiments on two datasets of size 1B from the Polysemous codes" paper. ### Getting BIGANN Download the four files of ANN_SIFT1B from http://corpus-texmex.irisa.fr/ to subdirectory bigann/ ### Getting Deep1B 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 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](https://github.com/facebookresearch/faiss/wiki/High-level-interface-and-auto-tuning#index-factory) (see below for examples) - the remaining arguments are parsed as search-time parameters. ### Experiments of Table 2 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](https://www.gnu.org/software/bash/manual/html_node/Brace-Expansion.html) 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 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](https://github.com/facebookresearch/faiss/wiki/High-level-interface-and-auto-tuning/_edit#auto-tuning-the-runtime-parameters) 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 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 See above on how to get SIFT1M into subdirectory sift1M/. The script [`bench_gpu_sift1m.py`](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 To get the "infinite MNIST dataset", follow the instructions on [Léon Bottou's website](http://leon.bottou.org/projects/infimnist). The script assumes the file `mnist8m-patterns-idx3-ubyte` is in subdirectory `mnist8m` The script [`kmeans_mnist.py`](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 The script [`bench_gpu_1bn.py`](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 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 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 # 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 # The contrib modules The contrib directory contains helper modules for Faiss for various tasks. ## Code structure 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 ### rpc.py A very simple Remote Procedure Call library, where function parameters and results are pickled, for use with client_server.py ### client_server.py 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](https://github.com/facebookresearch/faiss/wiki/Indexes-that-do-not-fit-in-RAM#distributed-index) ### ondisk.py Encloses the main logic to merge indexes into an on-disk index. See [On-disk storage](https://github.com/facebookresearch/faiss/wiki/Indexes-that-do-not-fit-in-RAM#on-disk-storage) ### exhaustive_search.py 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 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 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 A few functions to override the coarse quantizer in IVF, providing additional flexibility for assignment. ### datasets.py (may require h5py) Definition of how to access data for some standard datasets. ### factory_tools.py Functions related to factory strings. ### evaluation.py A few non-trivial evaluation functions for search results ### clustering.py 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 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 # 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 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 ` 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 # 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 Demos for a few Faiss functionalities ===================================== demo_auto_tune.py ----------------- Demonstrates the auto-tuning functionality of Faiss demo_ondisk_ivf.py ------------------ 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