-
Notifications
You must be signed in to change notification settings - Fork 3.7k
Faiss indexes
The basic indexes are given hereafter:
Method | Class name | index_factory |
Main parameters | Bytes/vector | Exhaustive | Comments |
---|---|---|---|---|---|---|
Exact Search for L2 | IndexFlatL2 |
"Flat" |
d |
4*d |
yes | brute-force |
Exact Search for Inner Product | IndexFlatIP |
- | d |
4*d |
yes | also for cosine (normalize vectors beforehand) |
Inverted file with exact post-verification | IndexIVFFlat |
"IVFx,Flat" |
quantizer , d , nlists , metric
|
4*d |
no | Take another index to assign vectors to inverted lists |
Locality-Sensitive Hashing (binary flat index) | IndexLSH |
- |
d , nbits
|
nbits/8 |
yes | optimized by using random rotation instead of random projections |
Product quantizer (PQ) in flat mode | IndexPQ |
"PQx" |
d , M , nbits
|
M (if nbits=8) |
yes | |
IVFADC (coarse quantizer+PQ on residuals) | IndexIVFPQ |
"IVFx,PQy" |
quantizer , d , nlists , M , nbits
|
M+4 or M+8
|
no | the memory cost depends on the data type used to represent ids (int or long), currently supports only nbits <= 8 |
IVFADC+R (same as IVFADC with re-ranking based on codes) | IndexIVFPQR |
"IVFx,PQy+z" |
quantizer , d , nlists , M , nbits , M_refine , nbits_refine
|
M+M_refine+4 or M+M_refine+8
|
no |
The index can be constructed explicitly with the class constructor, or by using index_factory
.
A typical way to speed-up the process at the cost of loosing the guarantee to find the nearest neighbor is to employ a partitioning technique such as k-means. The corresponding algorithms are sometimes referred to as cell-probe methods.
We use a partition-based method based on Multi-probing (a reminiscent variant of best-bin KD-tree).
- The feature space is partitioned into
ncells
cells. - The database vectors are assigned to one of these cells thanks to a hashing function (in the case of k-means, the assignment to the centroid closest to the query), and stored in an inverted file structure formed of
ncells
inverted lists. - At query time, a set of
nprobe
inverted lists is selected - The query is compared to each of the database vector assigned to these lists.
Doing so, only a fraction of the database is compared to the query: as a first approximation, this fraction is nprobe/ncells
, but note that this approximation is usually under-estimated because the inverted lists have not equal lengths.
The failure case appears when the cell of the nearest neighbor of a given query is not selected.
In C++, the corresponding index is the index IndexIVFFlat
.
The constructor takes an index as a parameter, which is used to do the assignment to the inverted lists. The query is searched in this index, and the returned vector id(s) are the inverted list(s) that should be visited.
Typically, one would use a Flat index as coarse quantizer. The train method of the IndexIVF adds the centroids to the flat index. The nprobe
is specified at query time (useful for measuring trade-offs between speed and accuracy).
NOTE: As a rule of thumb, denoting by n
the number of points to be indexed, a typical way to select the number of centroids is to aim at balancing the cost of the assignment to the centroids (ncentroidsd for a plain k-means) with the number of exact distance computations performed when parsing the inverted lists (in the order of 'kprobe/ncellsn*C', where the constant accounts for the uneven distribution of the list and the fact that a single vector comparison is done more efficiently when done by batch with centroids, say C=10 to give an idea). This leads to a number of centroids of the form ncentroids = C * sqrt (n)
.
NOTE: Under the hood, IndexIVFKmeans
and IndexIVFSphericalKmeans
are not objects but functions that return IndexIVFFlat
objects that a properly set up.
WARNING: partitioning methods are prone to suffer the curse of dimensionality. For truly high-dimensional data, achieving good recall requires to have a very large number of probes.
The most popular cell-probe method is probably the original Locality Sensitive Hashing method referred to as [E2LSH] (http://www.mit.edu/~andoni/LSH/). However this method and its derivatives suffer from two drawbacks:
- They require a lot of hash functions (=partitions) to achieve acceptable results, leading to a lot of extra memory. Memory is not cheap.
- The hash function are not adapted to the input data. This is good for proofs but leads to suboptimal choice results in practice.
In C++, a LSH index (binary vector mode, See Charikar STOC'2002) is declared as follows:
IndexLSH * index = new faiss::IndexLSH (d, nbits);
where d
is the input vector dimensionality and nbits
the number of bits use per stored vector.
In Python, the (improved) LSH index is constructed and search as follows
n_bits = 2 * d
lsh = faiss.IndexLSH (d, n_bits)
lsh.train (x_train)
lsh.add (x_base)
D, I = lsh.search (x_query, k)
NOTE: The algorithm is not vanilla-LSH, but a better choice. Instead of set of orthogonal projectors is used if n_bits <= d, or a tight frame if n_bits > d.
In C++, the indexes based on product quantization are identified by the keyword PQ. For instance, the most common indexes based on product quantization are declared as follows:
#include <faiss/IndexPQ.h>
#include <faiss/IndexIVFPQ.h>
// Define a product quantizer for vectors of dimensionality d=128,
// with 8 bits per subquantizer and M=16 distinct subquantizer
size_t d = 128;
int M = 16;
int nbits = 8;
faiss:IndexPQ * index_pq = new faiss::IndexPQ (d, M, nbits);
// Define an index using both PQ and an inverted file with nlists to avoid exhaustive search
// The index 'quantizer' must be already declared
faiss::IndexIVFPQ * ivfpq = new faiss::IndexIVFPQ (quantizer, d, nlists, M, nbits);
// Same but with another level of refinement
faiss::IndexIVFPQR * ivfpqr = new faiss::IndexIVFPQR (quantizer, d, nclust, M, nbits, M_refine, nbits);
In Python, a product quantizer is defined by:
m = 16 # number of subquantizers
n_bits = 8 # bits allocated per subquantizer
pq = faiss.IndexPQ (d, m, n_bits) # Create the index
pq.train (x_train) # Training
pq.add (x_base) # Populate the index
D, I = pq.search (x_query, k) # Perform a search
The number of bits n_bits
must be equal to 8, 12 or 16. The dimension d
should be a multiple of m
The IndexIVFPQ
is probably the most useful indexing structure for large-scale search. It is used like
coarse_quantizer = faiss.IndexFlatL2 (d)
index = faiss.IndexIVFPQ (coarse_quantizer, d,
ncentroids, code_size, 8)
index.nprobe = 5
See the chapter about IndexIVFFlat
for the setting of ncentroids
. The code_size
is typically a power of two between 4 and 64. Like for IndexPQ
, d
should be a multiple of m
.
Faiss building blocks: clustering, PCA, quantization
Index IO, cloning and hyper parameter tuning
Threads and asynchronous calls
Inverted list objects and scanners
Indexes that do not fit in RAM
Brute force search without an index
Fast accumulation of PQ and AQ codes (FastScan)
Setting search parameters for one query
Binary hashing index benchmark