FAISS

FAISS is organized as a toolbox that contains a variety of indexing methods that commonly involve a chain of components (preprocessing, compression, non-exhaustive search, etc.). The scope of the library is intentionally limited to focus on ANNS algorithmic implementation and to avoid facilities related to database functionality, distributed computing or feature extraction algorithms.{{cite arXiv|title=The Faiss library|eprint=2401.08281 |last1=Douze |first1=Matthijs |last2=Guzhva |first2=Alexandr |last3=Deng |first3=Chengqi |last4=Johnson |first4=Jeff |last5=Szilvasy |first5=Gergely |last6=Mazaré |first6=Pierre-Emmanuel |last7=Lomeli |first7=Maria |last8=Hosseini |first8=Lucas |last9=Jégou |first9=Hervé |date=2024 |class=cs.LG }}

FAISS is designed with the following assumptions:

• Primary data type for vector representation is FP32. The support of other floating-point formats, such as BF16 and FP16, is provided.
• Prefer batches of input queries over a single input query for the search.
• Emphasize on allowing users to write a fast prototyping code using its Python wrappers.
• The code should be as open as possible, so that users can access all the implementation details of the indexes.

The following major categories of indexing methods are supported:

• Brute-force search
• Inverted-lists based indices{{cite book |title=Proceedings Ninth IEEE International Conference on Computer Vision |date=2003 |pages=1470–1477 vol.2 |doi=10.1109/ICCV.2003.1238663 |chapter=Video Google: A text retrieval approach to object matching in videos |last1=Sivic |last2=Zisserman |isbn=0-7695-1950-4 }}
• Graph indices, including (Hierarchical navigable small world) HNSW and Navigating Spread-out Graph (NSG){{cite arXiv|title=Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph|eprint=1707.00143 |last1=Fu |first1=Cong |last2=Xiang |first2=Chao |last3=Wang |first3=Changxu |last4=Cai |first4=Deng |date=2017 |class=cs.LG }}
• Locality-sensitive hashing (LSH)

The following families of vector quantization methods are supported:

• Binary Quantization
• Scalar Quantization (SQ)
• Product Quantization{{cite journal |last1=Jégou |first1=H |last2=Douze |first2=M |last3=Schmid |first3=C |title=Product Quantization for Nearest Neighbor Search |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |date=January 2011 |volume=33 |issue=1 |pages=117–128 |doi=10.1109/TPAMI.2010.57|pmid=21088323 |url=https://hal.inria.fr/inria-00514462/file/jegou_pq_postprint.pdf }} (PQ), including Polysemous Codes,{{cite book |last1=Douze |first1=Matthijs |last2=Jégou |first2=Hervé |last3=Perronnin |first3=Florent |chapter=Polysemous Codes |title=Computer Vision – ECCV 2016 |series=Lecture Notes in Computer Science |date=2016 |volume=9906 |pages=785–801 |doi=10.1007/978-3-319-46475-6_48|isbn=978-3-319-46474-9 }} Optimized Product Quantization{{cite journal |last1=Ge |first1=Tiezheng |last2=He |first2=Kaiming |last3=Ke |first3=Qifa |last4=Sun |first4=Jian |title=Optimized Product Quantization |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |date=April 2014 |volume=36 |issue=4 |pages=744–755 |doi=10.1109/TPAMI.2013.240|pmid=26353197 }} (OPQ) and Quicker ADC{{cite journal |last1=Andre |first1=Fabien |last2=Kermarrec |first2=Anne-Marie |last3=Le Scouarnec |first3=Nicolas |title=Quicker ADC : Unlocking the Hidden Potential of Product Quantization With SIMD |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |date=1 May 2021 |volume=43 |issue=5 |pages=1666–1677 |doi=10.1109/TPAMI.2019.2952606|pmid=31722477 |arxiv=1812.09162 }} (PQFastScan)
• Additive Quantization{{cite book |last1=Babenko |first1=Artem |last2=Lempitsky |first2=Victor |title=2014 IEEE Conference on Computer Vision and Pattern Recognition |chapter=Additive Quantization for Extreme Vector Compression |date=June 2014 |pages=931–938 |doi=10.1109/CVPR.2014.124|isbn=978-1-4799-5118-5 }} (AQ), including Residual Quantization{{cite arXiv|title=Improved Residual Vector Quantization for High-dimensional Approximate Nearest Neighbor Search|eprint=1509.05195 |last1=Liu |first1=Shicong |last2=Lu |first2=Hongtao |last3=Shao |first3=Junru |date=2015 |class=cs.CV }} (RQ) and Local Search Quantization{{cite book |last1=Martinez |first1=Julieta |last2=Zakhmi |first2=Shobhit |last3=Hoos |first3=Holger H. |last4=Little |first4=James J. |chapter=LSQ++: Lower Running Time and Higher Recall in Multi-codebook Quantization |title=Computer Vision – ECCV 2018 |series=Lecture Notes in Computer Science |date=2018 |volume=11220 |pages=508–523 |doi=10.1007/978-3-030-01270-0_30|isbn=978-3-030-01269-4 }} (LSQ)
• Neural Quantization, including QINCO{{cite arXiv|title=Residual Quantization with Implicit Neural Codebooks|eprint=2401.14732 |last1=Huijben |first1=Iris A. M. |last2=Douze |first2=Matthijs |last3=Muckley |first3=Matthew |last4=van Sloun |first4=Ruud J. G. |last5=Verbeek |first5=Jakob |date=2024 |class=cs.LG }}

FAISS focuses on euclidean distance and inner product distance for floating-point data. The limited support of other distances (manhattan distance, Lp distance, etc.) is also available.

FAISS code supports multithreading via OpenMP, utilizes BLAS via OpenBLAS or Intel MKL, and also uses custom SIMD kernels for x86 and ARM Neon CPUs.

Besides the similarity search, FAISS provides the following useful facilities:

• k-means clustering
• Random-matrix rotations{{cite book |last1=Sandhawalia |first1=Harsimrat |last2=Jegou |first2=Herve |title=2010 IEEE International Conference on Acoustics, Speech and Signal Processing |chapter=Searching with expectations |date=March 2010 |pages=1242–1245 |doi=10.1109/ICASSP.2010.5495403|isbn=978-1-4244-4295-9 |url=https://hal.inria.fr/inria-00548629/file/searching_with_expectations.pdf }} for spreading the variance over all the dimensions without changing the measured distances
• Principal component analysis
• Data deduplication, which is especially useful for image datasets.

FAISS has a standalone Vector Codec functionality for the lossy compression of vectors, allowing to trade the representation accuracy for the binary size.{{cite web|url=https://github.com/facebookresearch/faiss/wiki/Vector-codecs|title=FAISS vector codecs|website=GitHub }}

Typical FAISS applications include recommender systems, data mining,{{cite arXiv|title=RAFIC: Retrieval-Augmented Few-shot Image Classification|eprint=2312.06868 |last1=Lin |first1=Hangfei |last2=Miao |first2=Li |last3=Ziai |first3=Amir |date=2023 |class=cs.CV }} text retrieval and content moderation.{{cite web|url=https://github.com/thorn-oss/perception|title=Perceptual hashing tools|website=GitHub }}

FAISS was reported to index 1.5 trillion 144-dimensional vectors for internal Meta Platforms applications.{{cite web|url=https://github.com/facebookresearch/faiss/wiki/Indexing-1T-vectors|title=Indexing 1T vectors|website=GitHub }}

FAISS is used in vector databases as a core component of a search engine (OpenSearch,{{cite web|url=https://opensearch.org/docs/latest/search-plugins/knn/approximate-knn/|title=OpenSearch Approximate k-NN search}}{{cite web|url=https://aws.amazon.com/about-aws/whats-new/2023/10/amazon-opensearch-service-vector-query-filters-faiss/|title=Amazon OpenSearch Service now supports efficient vector query filters for FAISS}} Milvus,{{cite web|url=https://github.com/zilliztech/knowhere|title=Milvus Knowhere|website=GitHub }} Vearch{{cite web|url=https://github.com/vearch/vearch|title=Vearch: AI-native distributed vector database|website=GitHub }}).

FAISS is often considered as a baseline in similarity search benchmarks.{{cite arXiv|title=Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search|eprint=2205.03763 |author1=Harsha Vardhan Simhadri |last2=Williams |first2=George |last3=Aumüller |first3=Martin |last4=Douze |first4=Matthijs |last5=Babenko |first5=Artem |last6=Baranchuk |first6=Dmitry |last7=Chen |first7=Qi |last8=Hosseini |first8=Lucas |last9=Krishnaswamy |first9=Ravishankar |last10=Srinivasa |first10=Gopal |author11=Suhas Jayaram Subramanya |last12=Wang |first12=Jingdong |date=2022 |class=cs.LG }}{{cite arXiv|title=Results of the Big ANN: NeurIPS'23 competition|eprint=2409.17424 |author1=Harsha Vardhan Simhadri |last2=Aumüller |first2=Martin |last3=Ingber |first3=Amir |last4=Douze |first4=Matthijs |last5=Williams |first5=George |author6=Magdalen Dobson Manohar |last7=Baranchuk |first7=Dmitry |last8=Liberty |first8=Edo |last9=Liu |first9=Frank |last10=Landrum |first10=Ben |last11=Karjikar |first11=Mazin |last12=Dhulipala |first12=Laxman |last13=Chen |first13=Meng |last14=Chen |first14=Yue |last15=Ma |first15=Rui |last16=Zhang |first16=Kai |last17=Cai |first17=Yuzheng |last18=Shi |first18=Jiayang |last19=Chen |first19=Yizhuo |last20=Zheng |first20=Weiguo |last21=Wan |first21=Zihao |last22=Yin |first22=Jie |last23=Huang |first23=Ben |date=2024 |class=cs.IR }}{{cite web|url=https://github.com/erikbern/ann-benchmarks|title=Benchmarking nearest neighbors|website=GitHub }}{{cite web|url=https://github.com/matsui528/annbench|title=annbench: a lightweight benchmark for approximate nearest neighbor search|website=GitHub }}

FAISS has an integration with Haystack,{{cite web|url=https://haystack.deepset.ai/integrations/faiss-document-store|title=Use a FAISS vector database with Haystack}} LangChain{{cite web|url=https://python.langchain.com/docs/integrations/vectorstores/faiss/|title=FAISS integration with Langchain}} frameworks.

Various advanced code snippets for FAISS can be found on its [https://github.com/facebookresearch/faiss/wiki/Python-C---code-snippets snippets wiki page] and [https://github.com/facebookresearch/faiss/wiki/Case-studies case studies wiki page].

{{Portal|Free and open-source software}}

• Nearest neighbor search
• Similarity search
• Vector database
• Vector quantization

{{reflist}}

• {{Official website|https://faiss.ai/}}
• {{GitHub|facebookresearch/faiss}}
• [https://github.com/facebookresearch/faiss/wiki Official FAISS wiki]
• [https://github.com/facebookresearch/faiss/wiki/Guidelines-to-choose-an-index Guidelines to choose a FAISS index]
• [https://github.com/criteo/autofaiss Autofaiss] - automatically create Faiss knn indices with the most optimal similarity search parameters

Category:Free software programmed in C++

Category:Software using the MIT license