Skip to content
A library for efficient similarity search and clustering of dense vectors.
C++ Cuda Python C M4 Shell Other
Branch: master
Clone or download

Latest commit

Latest commit 833d417 May 5, 2020

Files

Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.github Update ISSUE_TEMPLATE.md Jun 25, 2018
.travis Add conda packages metadata + tests. (#769) Apr 5, 2019
acinclude Run time detection of avx2 for conda packages. (#957) Sep 20, 2019
benchs Facebook sync (2020-03-10) (#1136) Mar 10, 2020
build-aux Refactor makefiles and add configure script (#466) Jun 2, 2018
c_api C API : ClusteringIterationStats integration (#1140) Mar 12, 2020
conda Fix conda packages build reqs. Mar 25, 2020
demos Sync 20200323. (#1157) Mar 24, 2020
docs Facebook sync (May 2019) + relicense (#838) May 28, 2019
example_makefiles Facebook sync (May 2019) + relicense (#838) May 28, 2019
gpu Merge branch 'master' of https://github.com/facebookresearch/faiss Mar 30, 2020
impl Sync 20200323. (#1157) Mar 24, 2020
misc Facebook sync (May 2019) + relicense (#838) May 28, 2019
python Sync 20200323. (#1157) Mar 24, 2020
tests Sync 20200323. (#1157) Mar 24, 2020
tutorial Update 5-Multiple-GPUs.cpp Jan 16, 2020
utils Sync 20200323. (#1157) Mar 24, 2020
.dockerignore Add Dockerfile (#55) Mar 23, 2017
.gitignore Refactor makefiles and add configure script (#466) Jun 2, 2018
.travis.yml Dynamically detect avx2 capabilities (#877) Jun 28, 2019
AutoTune.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
AutoTune.h Correct a spelling mistake (#1190) May 5, 2020
CODE_OF_CONDUCT.md OSS Automated Fix: Addition of Code of Conduct Mar 22, 2019
CONTRIBUTING.md Update CONTRIBUTING.md Jun 25, 2019
Clustering.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
Clustering.h Sync 20200323. (#1157) Mar 24, 2020
DirectMap.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
DirectMap.h Facebook sync (2020-03-10) (#1136) Mar 10, 2020
Dockerfile Configure install paths in Dockerfile. (#772) Apr 7, 2019
INSTALL.md Update INSTALL.md Mar 29, 2020
IVFlib.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IVFlib.h Facebook sync (2020-03-10) (#1136) Mar 10, 2020
Index.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
Index.h Sync 20200323. (#1157) Mar 24, 2020
Index2Layer.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
Index2Layer.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexBinary.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexBinary.h Sync 20200323. (#1157) Mar 24, 2020
IndexBinaryFlat.cpp Sync 20200323. (#1157) Mar 24, 2020
IndexBinaryFlat.h Sync 20200323. (#1157) Mar 24, 2020
IndexBinaryFromFloat.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexBinaryFromFloat.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexBinaryHNSW.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexBinaryHNSW.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexBinaryHash.cpp Sync 20200323. (#1157) Mar 24, 2020
IndexBinaryHash.h Sync 20200323. (#1157) Mar 24, 2020
IndexBinaryIVF.cpp Sync 20200323. (#1157) Mar 24, 2020
IndexBinaryIVF.h Sync 20200323. (#1157) Mar 24, 2020
IndexFlat.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexFlat.h Sync 20200323. (#1157) Mar 24, 2020
IndexHNSW.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexHNSW.h Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexIVF.cpp Sync 20200323. (#1157) Mar 24, 2020
IndexIVF.h Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexIVFFlat.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexIVFFlat.h Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexIVFPQ.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexIVFPQ.h Sync 20200323. (#1157) Mar 24, 2020
IndexIVFPQR.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexIVFPQR.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexIVFSpectralHash.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexIVFSpectralHash.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexLSH.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexLSH.h Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexLattice.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexLattice.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexPQ.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexPQ.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexPreTransform.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexPreTransform.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexReplicas.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexReplicas.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexScalarQuantizer.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
IndexScalarQuantizer.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexShards.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
IndexShards.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
InvertedLists.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
InvertedLists.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
LICENSE Facebook sync (May 2019) + relicense (#838) May 28, 2019
Makefile Add cuh files to install include dir. Feb 29, 2020
MatrixStats.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
MatrixStats.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
MetaIndexes.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
MetaIndexes.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
MetricType.h Facebook sync (2020-03-10) (#1136) Mar 10, 2020
OnDiskInvertedLists.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
OnDiskInvertedLists.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
README.md Update README.md Mar 30, 2020
VectorTransform.cpp Facebook sync (2019-09-10) (#943) Sep 20, 2019
VectorTransform.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
clone_index.cpp Facebook sync 20191129 (#1048) Dec 4, 2019
clone_index.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
configure Run time detection of avx2 for conda packages. (#957) Sep 20, 2019
configure.ac Facebook sync (May 2019) + relicense (#838) May 28, 2019
depend Facebook sync (2019-09-10) (#943) Sep 20, 2019
faiss Facebook sync (2019-09-10) (#943) Sep 20, 2019
index_factory.cpp Facebook sync (2020-03-10) (#1136) Mar 10, 2020
index_factory.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
index_io.h Facebook sync (2019-09-10) (#943) Sep 20, 2019
makefile.inc.in Run time detection of avx2 for conda packages. (#957) Sep 20, 2019

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 by Facebook AI Research.

NEWS

NEW: version 1.6.3 (2020-03-27) IndexBinaryHash, GPU support for alternative distances.

NEW: version 1.6.1 (2019-11-29) bugfix.

NEW: version 1.6.0 (2019-10-15) code structure reorg, support for codec interface.

NEW: version 1.5.3 (2019-06-24) fix performance regression in IndexIVF.

NEW: version 1.5.2 (2019-05-27) the license was relaxed to MIT from BSD+Patents. Read LICENSE for details.

NEW: version 1.5.0 (2018-12-19) GPU binary flat index and binary HNSW index

NEW: version 1.4.0 (2018-08-30) no more crashes in pure Python code

NEW: version 1.3.0 (2018-07-12) support for binary indexes

NEW: latest commit (2018-02-22) supports on-disk storage of inverted indexes, see demos/demo_ondisk_ivf.py

NEW: latest commit (2018-01-09) includes an implementation of the HNSW indexing method, see benchs/bench_hnsw.py

NEW: there is now a Facebook public discussion group for Faiss users at https://www.facebook.com/groups/faissusers/

NEW: on 2017-07-30, the license on Faiss was relaxed to BSD from CC-BY-NC. Read LICENSE for details.

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.

Most 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.

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.

Building

The library is mostly implemented in C++, with optional GPU support provided via CUDA, and an optional Python interface. The CPU version requires a BLAS library. It compiles with a Makefile and can be packaged in a docker image. See 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
  • 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

The following are entry points for documentation:

Authors

The main authors of Faiss are:

Reference

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

@article{JDH17,
  title={Billion-scale similarity search with GPUs},
  author={Johnson, Jeff and Douze, Matthijs and J{\'e}gou, Herv{\'e}},
  journal={arXiv preprint arXiv:1702.08734},
  year={2017}
}

Join the Faiss community

For public discussion of Faiss or for questions, there is a Facebook group at https://www.facebook.com/groups/faissusers/

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

License

Faiss is MIT-licensed.

You can’t perform that action at this time.