Binary Indexes

Overview

Binary embeddings are used for several applications at Facebook, most notably Xrayhash and Facer embeddings. Faiss supports indexing binary vectors (with Hamming distance) natively, with the IndexBinaryFlat and IndexBinaryIVF indexes (both inheriting from IndexBinary).

Those indexes store the vectors as arrays of bytes, so that a vector of size d takes only d / 8 bytes in memory. Note that at the moment, only vectors with sizes multiple of 8 are supported. Of course, you can round up the vector length if needed.

The input to the add() and search() methods are also byte arrays ("uint8_t" in C++, "uint8" in numpy).

The Hamming distance computations are optimized using popcount CPU instructions.

IndexBinaryFlat

The "flat" binary index performs an exhaustive search.

The exhaustive search is carefully optimized especially for 256-bit vectors that are quite common.

Batching is applied on the query and the database side to avoid cache misses.

The values of hamming_batch_size and faiss::IndexBinaryFlat#query_batch_size can be customized to adjust the batch sizes but the default values were found to be close to optimal for a large range of settings.

Example

C++

#include <faiss/IndexBinaryFlat.h>

// Dimension of the vectors.
int d = 256;

// Vectors to be indexed, each represented by d / 8 bytes, layed out sequentially,
// i.e. the i-th vector starts at db[i * (d / 8)].
std::vector<uint8_t> db = ...;

// Vectors to be queried from the index.
std::vector<uint8_t> queries = ...;

// Initializing index.
faiss::IndexBinaryFlat index(d);

// Adding the database vectors.
index.add(db.size(), db.data());

// Number of nearest neighbors to retrieve per query vector.
int k = ...;

// Output variables for the queries.
std::vector<int32_t> distances(n * k);
std::vector<faiss::Index::idx_t> labels(n * k);

// Querying the index
index.search(queries.size(), queries.data(), k, distances.data(), labels.data());

// distances[i * k + j] contains the distance from the i-th query vector to its j-th nearest neighbor.
// labels[i * k + j] contains the id of the j-th nearest neighbor of the i-th query vector.

Python

import faiss

# Dimension of the vectors.
d = 256

# Vectors to be indexed, each represented by d / 8 bytes, layed out sequentially,
# i.e. the i-th vector starts at db[i * (d / 8)].
db = ...

# Vectors to be queried from the index.
queries = ...

# Initializing index.
index = faiss.IndexBinaryFlat(d)

# Adding the database vectors.
index.add(db)

# Number of nearest neighbors to retrieve per query vector.
k = ...;

# Querying the index
D, I = index.search(queries, k)

# D[i, j] contains the distance from the i-th query vector to its j-th nearest neighbor.
# I[i, j] contains the id of the j-th nearest neighbor of the i-th query vector.

IndexBinaryIVF

The "IVF" (Inverse Vector File) flavor speeds up the search by clustering the vectors. This clustering is done using a second (binary) index for quantization (usually a flat index). This is equivalent to the IndexIVFFlat of the floating-point indexes.

Example

C++

#include <faiss/IndexBinaryIVF.h>

// Dimension of the vectors.
int d = 256;

// Vectors to be indexed, each represented by d / 8 bytes, layed out sequentially,
// i.e. the i-th vector starts at db[i * (d / 8)].
std::vector<uint8_t> db = ...;

// Vectors to train the quantizer.
std::vector<uint8_t> training = ...;

// Vectors to be queried from the index.
std::vector<uint8_t> queries = ...;

// Initializing the quantizer.
faiss::IndexBinaryFlat quantizer(d);

// Number of clusters.
int nlist = ...;

// Initializing index.
faiss::IndexBinaryIVF index(&quantizer, d, nlist);
index.nprobe = 4; // Number of nearest clusters to be searched per query. 

// Training the quantizer.
index.train(training.size(), training.data());

// Adding the database vectors.
index.add(db.size(), db.data());

// Number of nearest neighbors to retrieve per query vector.
int k = ...;

// Output variables for the queries.
std::vector<int32_t> distances(n * k);
std::vector<faiss::idx_t> labels(n * k);

// Querying the index
index.search(queries.size(), queries.data(), k, distances.data(), labels.data());

// distances[i * k + j] contains the distance from the i-th query vector to its j-th nearest neighbor.
// labels[i * k + j] contains the id of the j-th nearest neighbor of the i-th query vector.

Python

import faiss

# Dimension of the vectors.
d = 256

# Vectors to be indexed, each represented by d / 8 bytes, layed out sequentially,
# i.e. the i-th vector starts at db[i * (d / 8)].
db = ...

# Vectors to train the quantizer.
training = ...

# Vectors to be queried from the index.
queries = ...

# Initializing the quantizer.
quantizer = faiss.IndexBinaryFlat(d)

# Number of clusters.
nlist = ...

# Initializing index.
index = faiss.IndexBinaryIVF(quantizer, d, nlist)
index.nprobe = 4 # Number of nearest clusters to be searched per query. 

# Training the quantizer.
index.train(training)

# Adding the database vectors.
index.add(db)

# Number of nearest neighbors to retrieve per query vector.
k = ...

# Querying the index.
D, I = index.search(queries, k)

# D[i, j] contains the distance from the i-th query vector to its j-th nearest neighbor.
# I[i, j] contains the id of the j-th nearest neighbor of the i-th query vector.

Shorter versions using index factory

The faiss::index_binary_factory() allows for shorter declarations of binary indexes. It is especially useful for IndexBinaryIVF, for which a quantizer needs to be initialized.

Instead of the above initialization code:

C++

// Initializing the quantizer.
faiss::IndexBinaryFlat quantizer(d);

// Number of clusters.
int nlist = 32;

// Initializing index.
faiss::IndexBinaryIVF index(&quantizer, d, nlist);
index.nprobe = 4; // Number of nearest clusters to be searched per query. 

Python

# Initializing the quantizer.
quantizer = faiss.IndexBinaryFlat(d)

# Number of clusters.
nlist = 32

# Initializing index.
index = faiss.IndexBinaryIVF(quantizer, d, nlist)
index.nprobe = 4 # Number of nearest clusters to be searched per query. 

one could write:

C++

#include <faiss/AutoTune.h>
  
// Initializing the quantizer.
faiss::IndexBinaryIVF *index = dynamic_cast<faiss::IndexBinaryIVF *>(faiss::index_binary_factory(d, "BIVF32"));
index->nprobe = 4; // Number of nearest clusters to be searched per query.

Python

# Initializing the quantizer.
index = faiss.index_binary_factory(d, "BIVF32")
index.nprobe = 4 # Number of nearest clusters to be searched per query.