Namespace faiss

namespace faiss

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree.

Throughout the library, vectors are provided as float * pointers. Most algorithms can be optimized when several vectors are processed (added/searched) together in a batch. In this case, they are passed in as a matrix. When n vectors of size d are provided as float * x, component j of vector i is

x[ i * d + j ]

where 0 <= i < n and 0 <= j < d. In other words, matrices are always compact. When specifying the size of the matrix, we call it an n*d matrix, which implies a row-major storage.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. I/O functions can read/write to a filename, a file handle or to an object that abstracts the medium.

The read functions return objects that should be deallocated with delete. All references within these objectes are owned by the object.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Definition of inverted lists + a few common classes that implement the interface.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Since IVF (inverted file) indexes are of so much use for large-scale use cases, we group a few functions related to them in this small library. Most functions work both on IndexIVFs and IndexIVFs embedded within an IndexPreTransform.

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. In this file are the implementations of extra metrics beyond L2 and inner product

Copyright (c) Facebook, Inc. and its affiliates.

This source code is licensed under the MIT license found in the LICENSE file in the root directory of this source tree. Defines a few objects that apply transformations to a set of vectors Often these are pre-processing steps.

Typedefs

using IndexIDMap = IndexIDMapTemplate<Index>

using IndexBinaryIDMap = IndexIDMapTemplate<IndexBinary>

using IndexIDMap2 = IndexIDMap2Template<Index>

using IndexBinaryIDMap2 = IndexIDMap2Template<IndexBinary>

using IVFSearchParameters = SearchParametersIVF

using IndexReplicas = IndexReplicasTemplate<Index>

using IndexBinaryReplicas = IndexReplicasTemplate<IndexBinary>

using IndexShards = IndexShardsTemplate<Index>

using IndexBinaryShards = IndexShardsTemplate<IndexBinary>

using ConcatenatedInvertedLists = HStackInvertedLists

using idx_t = int64_t

all vector indices are this type

typedef HeapArray<CMin<float, int64_t>> float_minheap_array_t

typedef HeapArray<CMin<int, int64_t>> int_minheap_array_t

typedef HeapArray<CMax<float, int64_t>> float_maxheap_array_t

typedef HeapArray<CMax<int, int64_t>> int_maxheap_array_t

Enums

enum MetricType

The metric space for vector comparison for Faiss indices and algorithms.

Most algorithms support both inner product and L2, with the flat (brute-force) indices supporting additional metric types for vector comparison.

Values:

enumerator METRIC_INNER_PRODUCT

maximum inner product search

enumerator METRIC_L2

squared L2 search

enumerator METRIC_L1

L1 (aka cityblock)

enumerator METRIC_Linf

infinity distance

enumerator METRIC_Lp

L_p distance, p is given by a faiss::Index metric_arg

enumerator METRIC_Canberra

some additional metrics defined in scipy.spatial.distance

enumerator METRIC_BrayCurtis

enumerator METRIC_JensenShannon

Functions

Index *clone_index(const Index*)

Quantizer *clone_Quantizer(const Quantizer *quant)

float kmeans_clustering(size_t d, size_t n, size_t k, const float *x, float *centroids)

simplified interface

Parameters:

• d – dimension of the data

• n – nb of training vectors

• k – nb of output centroids

• x – training set (size n * d)

• centroids – output centroids (size k * d)

Returns:

final quantization error

Index *index_factory(int d, const char *description, MetricType metric = METRIC_L2)

Build and index with the sequence of processing steps described in the string.

IndexBinary *index_binary_factory(int d, const char *description)

void write_index(const Index *idx, const char *fname)

void write_index(const Index *idx, FILE *f)

void write_index(const Index *idx, IOWriter *writer)

void write_index_binary(const IndexBinary *idx, const char *fname)

void write_index_binary(const IndexBinary *idx, FILE *f)

void write_index_binary(const IndexBinary *idx, IOWriter *writer)

Index *read_index(const char *fname, int io_flags = 0)

Index *read_index(FILE *f, int io_flags = 0)

Index *read_index(IOReader *reader, int io_flags = 0)

IndexBinary *read_index_binary(const char *fname, int io_flags = 0)

IndexBinary *read_index_binary(FILE *f, int io_flags = 0)

IndexBinary *read_index_binary(IOReader *reader, int io_flags = 0)

void write_VectorTransform(const VectorTransform *vt, const char *fname)

void write_VectorTransform(const VectorTransform *vt, IOWriter *f)

VectorTransform *read_VectorTransform(const char *fname)

VectorTransform *read_VectorTransform(IOReader *f)

ProductQuantizer *read_ProductQuantizer(const char *fname)

ProductQuantizer *read_ProductQuantizer(IOReader *reader)

void write_ProductQuantizer(const ProductQuantizer *pq, const char *fname)

void write_ProductQuantizer(const ProductQuantizer *pq, IOWriter *f)

void write_InvertedLists(const InvertedLists *ils, IOWriter *f)

InvertedLists *read_InvertedLists(IOReader *reader, int io_flags = 0)

void initialize_IVFPQ_precomputed_table(int &use_precomputed_table, const Index *quantizer, const ProductQuantizer &pq, AlignedTable<float> &precomputed_table, bool verbose)

Pre-compute distance tables for IVFPQ with by-residual and METRIC_L2

Parameters:

• use_precomputed_table – (I/O) =-1: force disable =0: decide heuristically (default: use tables only if they are < precomputed_tables_max_bytes), set use_precomputed_table on output =1: tables that work for all quantizers (size 256 * nlist * M) =2: specific version for MultiIndexQuantizer (much more compact)

• precomputed_table – precomputed table to initialize

inline uint64_t lo_build(uint64_t list_id, uint64_t offset)

inline uint64_t lo_listno(uint64_t lo)

inline uint64_t lo_offset(uint64_t lo)

template<int A = 32>
inline bool is_aligned_pointer(const void *x)

float fvec_L2sqr(const float *x, const float *y, size_t d)

Squared L2 distance between two vectors.

float fvec_inner_product(const float *x, const float *y, size_t d)

inner product

float fvec_L1(const float *x, const float *y, size_t d)

L1 distance.

float fvec_Linf(const float *x, const float *y, size_t d)

infinity distance

void pairwise_L2sqr(int64_t d, int64_t nq, const float *xq, int64_t nb, const float *xb, float *dis, int64_t ldq = -1, int64_t ldb = -1, int64_t ldd = -1)

Compute pairwise distances between sets of vectors

Parameters:

• d – dimension of the vectors

• nq – nb of query vectors

• nb – nb of database vectors

• xq – query vectors (size nq * d)

• xb – database vectors (size nb * d)

• dis – output distances (size nq * nb)

• ldq, ldb, ldd – strides for the matrices

void fvec_inner_products_ny(float *ip, const float *x, const float *y, size_t d, size_t ny)

void fvec_L2sqr_ny(float *dis, const float *x, const float *y, size_t d, size_t ny)

size_t fvec_L2sqr_ny_nearest(float *distances_tmp_buffer, const float *x, const float *y, size_t d, size_t ny)

size_t fvec_L2sqr_ny_nearest_y_transposed(float *distances_tmp_buffer, const float *x, const float *y, const float *y_sqlen, size_t d, size_t d_offset, size_t ny)

float fvec_norm_L2sqr(const float *x, size_t d)

squared norm of a vector

void fvec_norms_L2(float *norms, const float *x, size_t d, size_t nx)

compute the L2 norms for a set of vectors

Parameters:

• norms – output norms, size nx

• x – set of vectors, size nx * d

void fvec_norms_L2sqr(float *norms, const float *x, size_t d, size_t nx)

same as fvec_norms_L2, but computes squared norms

void fvec_renorm_L2(size_t d, size_t nx, float *x)

void inner_product_to_L2sqr(float *dis, const float *nr1, const float *nr2, size_t n1, size_t n2)

void fvec_add(size_t d, const float *a, const float *b, float *c)

compute c := a + b for vectors

c and a can overlap, c and b can overlap

Parameters:

• a – size d

• b – size d

• c – size d

void fvec_add(size_t d, const float *a, float b, float *c)

compute c := a + b for a, c vectors and b a scalar

c and a can overlap

Parameters:

• a – size d

• c – size d

void fvec_sub(size_t d, const float *a, const float *b, float *c)

compute c := a - b for vectors

c and a can overlap, c and b can overlap

Parameters:

• a – size d

• b – size d

• c – size d

void fvec_inner_products_by_idx(float *ip, const float *x, const float *y, const int64_t *ids, size_t d, size_t nx, size_t ny)

void fvec_L2sqr_by_idx(float *dis, const float *x, const float *y, const int64_t *ids, size_t d, size_t nx, size_t ny)

void pairwise_indexed_L2sqr(size_t d, size_t n, const float *x, const int64_t *ix, const float *y, const int64_t *iy, float *dis)

compute dis[j] = L2sqr(x[ix[j]], y[iy[j]]) forall j=0..n-1

Parameters:

• x – size (max(ix) + 1, d)

• y – size (max(iy) + 1, d)

• ix – size n

• iy – size n

• dis – size n

void pairwise_indexed_inner_product(size_t d, size_t n, const float *x, const int64_t *ix, const float *y, const int64_t *iy, float *dis)

void knn_inner_product(const float *x, const float *y, size_t d, size_t nx, size_t ny, float_minheap_array_t *res, const IDSelector *sel = nullptr)

Return the k nearest neighors of each of the nx vectors x among the ny vector y, w.r.t to max inner product.

Parameters:

• x – query vectors, size nx * d

• y – database vectors, size ny * d

• res – result heap structure, which also provides k. Sorted on output

void knn_inner_product(const float *x, const float *y, size_t d, size_t nx, size_t ny, size_t k, float *distances, int64_t *indexes, const IDSelector *sel = nullptr)

Return the k nearest neighors of each of the nx vectors x among the ny vector y, for the inner product metric.

Parameters:

• x – query vectors, size nx * d

• y – database vectors, size ny * d

• distances – output distances, size nq * k

• indexes – output vector ids, size nq * k

void knn_L2sqr(const float *x, const float *y, size_t d, size_t nx, size_t ny, float_maxheap_array_t *res, const float *y_norm2 = nullptr, const IDSelector *sel = nullptr)

Return the k nearest neighors of each of the nx vectors x among the ny vector y, for the L2 distance

Parameters:

• x – query vectors, size nx * d

• y – database vectors, size ny * d

• res – result heap strcture, which also provides k. Sorted on output

• y_norm2 – (optional) norms for the y vectors (nullptr or size ny)

• sel – search in this subset of vectors

void knn_L2sqr(const float *x, const float *y, size_t d, size_t nx, size_t ny, size_t k, float *distances, int64_t *indexes, const float *y_norm2 = nullptr, const IDSelector *sel = nullptr)

Return the k nearest neighors of each of the nx vectors x among the ny vector y, for the L2 distance

Parameters:

• x – query vectors, size nx * d

• y – database vectors, size ny * d

• distances – output distances, size nq * k

• indexes – output vector ids, size nq * k

• y_norm2 – (optional) norms for the y vectors (nullptr or size ny)

• sel – search in this subset of vectors

void knn_inner_products_by_idx(const float *x, const float *y, const int64_t *subset, size_t d, size_t nx, size_t nsubset, size_t k, float *vals, int64_t *ids, int64_t ld_ids = -1)

Find the max inner product neighbors for nx queries in a set of ny vectors indexed by ids. May be useful for re-ranking a pre-selected vector list

Parameters:

• x – query vectors, size nx * d

• y – database vectors, size (max(ids) + 1) * d

• ids – subset of database vectors to consider, size (nx, nsubset)

• res – result structure

• ld_ids – stride for the ids array. -1: use nsubset, 0: all queries process the same subset

void knn_L2sqr_by_idx(const float *x, const float *y, const int64_t *subset, size_t d, size_t nx, size_t nsubset, size_t k, float *vals, int64_t *ids, int64_t ld_subset = -1)

Find the nearest neighbors for nx queries in a set of ny vectors indexed by ids. May be useful for re-ranking a pre-selected vector list

Parameters:

• x – query vectors, size nx * d

• y – database vectors, size (max(ids) + 1) * d

• subset – subset of database vectors to consider, size (nx, nsubset)

• res – rIDesult structure

• ld_subset – stride for the subset array. -1: use nsubset, 0: all queries process the same subset

void range_search_L2sqr(const float *x, const float *y, size_t d, size_t nx, size_t ny, float radius, RangeSearchResult *result, const IDSelector *sel = nullptr)

Return the k nearest neighors of each of the nx vectors x among the ny vector y, w.r.t to max inner product

Parameters:

• x – query vectors, size nx * d

• y – database vectors, size ny * d

• radius – search radius around the x vectors

• result – result structure

void range_search_inner_product(const float *x, const float *y, size_t d, size_t nx, size_t ny, float radius, RangeSearchResult *result, const IDSelector *sel = nullptr)

same as range_search_L2sqr for the inner product similarity

void compute_PQ_dis_tables_dsub2(size_t d, size_t ksub, const float *centroids, size_t nx, const float *x, bool is_inner_product, float *dis_tables)

specialized function for PQ2

bool exhaustive_L2sqr_fused_cmax(const float *x, const float *y, size_t d, size_t nx, size_t ny, SingleBestResultHandler<CMax<float, int64_t>> &res, const float *y_norms)

void pairwise_extra_distances(int64_t d, int64_t nq, const float *xq, int64_t nb, const float *xb, MetricType mt, float metric_arg, float *dis, int64_t ldq = -1, int64_t ldb = -1, int64_t ldd = -1)

void knn_extra_metrics(const float *x, const float *y, size_t d, size_t nx, size_t ny, MetricType mt, float metric_arg, float_maxheap_array_t *res)

FlatCodesDistanceComputer *get_extra_distance_computer(size_t d, MetricType mt, float metric_arg, size_t nb, const float *xb)

get a DistanceComputer that refers to this type of distance and indexes a flat array of size nb

inline uint16_t encode_fp16(float x)

inline float decode_fp16(uint16_t x)

template<size_t nbits, typename T>
inline T hamming(const uint8_t *bs1, const uint8_t *bs2)

template<size_t nbits>
inline hamdis_t hamming(const uint64_t *bs1, const uint64_t *bs2)

template<>
inline hamdis_t hamming<64>(const uint64_t *pa, const uint64_t *pb)

template<>
inline hamdis_t hamming<128>(const uint64_t *pa, const uint64_t *pb)

template<>
inline hamdis_t hamming<256>(const uint64_t *pa, const uint64_t *pb)

inline hamdis_t hamming(const uint64_t *bs1, const uint64_t *bs2, size_t nwords)

SPECIALIZED_HC (4)

SPECIALIZED_HC (8)

SPECIALIZED_HC (16)

SPECIALIZED_HC (20)

SPECIALIZED_HC (32)

SPECIALIZED_HC (64)

inline int generalized_hamming_64(uint64_t a)

void generalized_hammings_knn_hc(int_maxheap_array_t *ha, const uint8_t *a, const uint8_t *b, size_t nb, size_t code_size, int ordered = true)

generalized Hamming distances (= count number of code bytes that are the same)

void bitvec_print(const uint8_t *b, size_t d)

void fvecs2bitvecs(const float *x, uint8_t *b, size_t d, size_t n)

void bitvecs2fvecs(const uint8_t *b, float *x, size_t d, size_t n)

void fvec2bitvec(const float *x, uint8_t *b, size_t d)

void bitvec_shuffle(size_t n, size_t da, size_t db, const int *order, const uint8_t *a, uint8_t *b)

Shuffle the bits from b(i, j) := a(i, order[j])

inline int popcount64(uint64_t x)

void hammings(const uint8_t *a, const uint8_t *b, size_t na, size_t nb, size_t nbytespercode, hamdis_t *dis)

Compute a set of Hamming distances between na and nb binary vectors

Parameters:

• a – size na * nbytespercode

• b – size nb * nbytespercode

• nbytespercode – should be multiple of 8

• dis – output distances, size na * nb

void hammings_knn_hc(int_maxheap_array_t *ha, const uint8_t *a, const uint8_t *b, size_t nb, size_t ncodes, int ordered)

Return the k smallest Hamming distances for a set of binary query vectors, using a max heap.

Parameters:

• a – queries, size ha->nh * ncodes

• b – database, size nb * ncodes

• nb – number of database vectors

• ncodes – size of the binary codes (bytes)

• ordered – if != 0: order the results by decreasing distance (may be bottleneck for k/n > 0.01)

void hammings_knn(int_maxheap_array_t *ha, const uint8_t *a, const uint8_t *b, size_t nb, size_t ncodes, int ordered)

void hammings_knn_mc(const uint8_t *a, const uint8_t *b, size_t na, size_t nb, size_t k, size_t ncodes, int32_t *distances, int64_t *labels)

Return the k smallest Hamming distances for a set of binary query vectors, using counting max.

Parameters:

• a – queries, size na * ncodes

• b – database, size nb * ncodes

• na – number of query vectors

• nb – number of database vectors

• k – number of vectors/distances to return

• ncodes – size of the binary codes (bytes)

• distances – output distances from each query vector to its k nearest neighbors

• labels – output ids of the k nearest neighbors to each query vector

void hamming_range_search(const uint8_t *a, const uint8_t *b, size_t na, size_t nb, int radius, size_t ncodes, RangeSearchResult *result)

same as hammings_knn except we are doing a range search with radius

void hamming_count_thres(const uint8_t *bs1, const uint8_t *bs2, size_t n1, size_t n2, hamdis_t ht, size_t ncodes, size_t *nptr)

size_t match_hamming_thres(const uint8_t *bs1, const uint8_t *bs2, size_t n1, size_t n2, hamdis_t ht, size_t ncodes, int64_t *idx, hamdis_t *dis)

void crosshamming_count_thres(const uint8_t *dbs, size_t n, hamdis_t ht, size_t ncodes, size_t *nptr)

template<class C>
inline void heap_pop(size_t k, typename C::T *bh_val, typename C::TI *bh_ids)

Pops the top element from the heap defined by bh_val[0..k-1] and bh_ids[0..k-1]. on output the element at k-1 is undefined.

template<class C>
inline void heap_push(size_t k, typename C::T *bh_val, typename C::TI *bh_ids, typename C::T val, typename C::TI id)

Pushes the element (val, ids) into the heap bh_val[0..k-2] and bh_ids[0..k-2]. on output the element at k-1 is defined.

template<class C>
inline void heap_replace_top(size_t k, typename C::T *bh_val, typename C::TI *bh_ids, typename C::T val, typename C::TI id)

Replaces the top element from the heap defined by bh_val[0..k-1] and bh_ids[0..k-1], and for identical bh_val[] values also sorts by bh_ids[] values.

template<typename T>
inline void minheap_pop(size_t k, T *bh_val, int64_t *bh_ids)

template<typename T>
inline void minheap_push(size_t k, T *bh_val, int64_t *bh_ids, T val, int64_t ids)

template<typename T>
inline void minheap_replace_top(size_t k, T *bh_val, int64_t *bh_ids, T val, int64_t ids)

template<typename T>
inline void maxheap_pop(size_t k, T *bh_val, int64_t *bh_ids)

template<typename T>
inline void maxheap_push(size_t k, T *bh_val, int64_t *bh_ids, T val, int64_t ids)

template<typename T>
inline void maxheap_replace_top(size_t k, T *bh_val, int64_t *bh_ids, T val, int64_t ids)

template<class C>
inline void heap_heapify(size_t k, typename C::T *bh_val, typename C::TI *bh_ids, const typename C::T *x = nullptr, const typename C::TI *ids = nullptr, size_t k0 = 0)

template<typename T>
inline void minheap_heapify(size_t k, T *bh_val, int64_t *bh_ids, const T *x = nullptr, const int64_t *ids = nullptr, size_t k0 = 0)

template<typename T>
inline void maxheap_heapify(size_t k, T *bh_val, int64_t *bh_ids, const T *x = nullptr, const int64_t *ids = nullptr, size_t k0 = 0)

template<class C>
inline void heap_addn(size_t k, typename C::T *bh_val, typename C::TI *bh_ids, const typename C::T *x, const typename C::TI *ids, size_t n)

template<typename T>
inline void minheap_addn(size_t k, T *bh_val, int64_t *bh_ids, const T *x, const int64_t *ids, size_t n)

template<typename T>
inline void maxheap_addn(size_t k, T *bh_val, int64_t *bh_ids, const T *x, const int64_t *ids, size_t n)

template<typename C>
inline size_t heap_reorder(size_t k, typename C::T *bh_val, typename C::TI *bh_ids)

template<typename T>
inline size_t minheap_reorder(size_t k, T *bh_val, int64_t *bh_ids)

template<typename T>
inline size_t maxheap_reorder(size_t k, T *bh_val, int64_t *bh_ids)

template<class C>
inline void indirect_heap_pop(size_t k, const typename C::T *bh_val, typename C::TI *bh_ids)

template<class C>
inline void indirect_heap_push(size_t k, const typename C::T *bh_val, typename C::TI *bh_ids, typename C::TI id)

template<typename T>
inline T cmin_nextafter(T x)

template<typename T>
inline T cmax_nextafter(T x)

template<>
inline float cmin_nextafter<float>(float x)

template<>
inline float cmax_nextafter<float>(float x)

template<>
inline uint16_t cmin_nextafter<uint16_t>(uint16_t x)

template<>
inline uint16_t cmax_nextafter<uint16_t>(uint16_t x)

template<class C>
C::T partition_fuzzy(typename C::T *vals, typename C::TI *ids, size_t n, size_t q_min, size_t q_max, size_t *q_out)

partitions the table into 0:q and q:n where all elements above q are >= all elements below q (for C = CMax, for CMin comparisons are reversed)

Returns the partition threshold. The elements q:n are destroyed on output.

template<class C>
inline C::T partition(typename C::T *vals, typename C::TI *ids, size_t n, size_t q)

simplified interface for when the parition is not fuzzy

void simd_histogram_8(const uint16_t *data, int n, uint16_t min, int shift, int *hist)

low level SIMD histogramming functions 8-bin histogram of (x - min) >> shift values outside the range are ignored. the data table should be aligned on 32 bytes

void simd_histogram_16(const uint16_t *data, int n, uint16_t min, int shift, int *hist)

same for 16-bin histogram

void float_rand(float *x, size_t n, int64_t seed)

void float_randn(float *x, size_t n, int64_t seed)

void int64_rand(int64_t *x, size_t n, int64_t seed)

void byte_rand(uint8_t *x, size_t n, int64_t seed)

void int64_rand_max(int64_t *x, size_t n, uint64_t max, int64_t seed)

void rand_perm(int *perm, size_t n, int64_t seed)

void rand_smooth_vectors(size_t n, size_t d, float *x, int64_t seed)

inline simd16uint16 min(simd16uint16 a, simd16uint16 b)

inline simd16uint16 max(simd16uint16 a, simd16uint16 b)

inline simd16uint16 combine2x2(simd16uint16 a, simd16uint16 b)

inline uint32_t cmp_ge32(simd16uint16 d0, simd16uint16 d1, simd16uint16 thr)

inline uint32_t cmp_le32(simd16uint16 d0, simd16uint16 d1, simd16uint16 thr)

inline simd32uint8 uint16_to_uint8_saturate(simd16uint16 a, simd16uint16 b)

inline uint32_t get_MSBs(simd32uint8 a)

get most significant bit of each byte

inline simd32uint8 blendv(simd32uint8 a, simd32uint8 b, simd32uint8 mask)

use MSB of each byte of mask to select a byte between a and b

inline simd8float32 hadd(simd8float32 a, simd8float32 b)

inline simd8float32 unpacklo(simd8float32 a, simd8float32 b)

inline simd8float32 unpackhi(simd8float32 a, simd8float32 b)

inline simd8float32 fmadd(simd8float32 a, simd8float32 b, simd8float32 c)

inline void cmplt_and_blend_inplace(const simd8float32 candidateValues, const simd8uint32 candidateIndices, simd8float32 &lowestValues, simd8uint32 &lowestIndices)

inline simd16uint16 min(const simd16uint16 &av, const simd16uint16 &bv)

inline simd16uint16 max(const simd16uint16 &av, const simd16uint16 &bv)

inline simd16uint16 combine2x2(const simd16uint16 &a, const simd16uint16 &b)

inline uint32_t cmp_ge32(const simd16uint16 &d0, const simd16uint16 &d1, const simd16uint16 &thr)

inline uint32_t cmp_le32(const simd16uint16 &d0, const simd16uint16 &d1, const simd16uint16 &thr)

inline simd32uint8 uint16_to_uint8_saturate(const simd16uint16 &a, const simd16uint16 &b)

inline uint32_t get_MSBs(const simd32uint8 &a)

get most significant bit of each byte

inline simd32uint8 blendv(const simd32uint8 &a, const simd32uint8 &b, const simd32uint8 &mask)

use MSB of each byte of mask to select a byte between a and b

inline simd8float32 hadd(const simd8float32 &a, const simd8float32 &b)

inline simd8float32 unpacklo(const simd8float32 &a, const simd8float32 &b)

inline simd8float32 unpackhi(const simd8float32 &a, const simd8float32 &b)

inline simd8float32 fmadd(const simd8float32 &a, const simd8float32 &b, const simd8float32 &c)

void fvec_argsort(size_t n, const float *vals, size_t *perm)

Indirect sort of a floating-point array

Parameters:

• n – size of the array

• vals – array to sort, size n

• perm – output: permutation of [0..n-1], st. vals[perm[i + 1]] >= vals[perm[i]]

void fvec_argsort_parallel(size_t n, const float *vals, size_t *perm)

Same as fvec_argsort, parallelized

void bucket_sort(size_t nval, const uint64_t *vals, uint64_t nbucket, int64_t *lims, int64_t *perm, int nt = 0)

Bucket sort of a list of values

Parameters:

• vals – values to sort, size nval, max value nbucket - 1

• lims – output limits of buckets, size nbucket + 1

• perm – output buckets, the elements of bucket i are in perm[lims[i]:lims[i + 1]]

• nt – number of threads (0 = pure sequential code)

void matrix_bucket_sort_inplace(size_t nrow, size_t ncol, int32_t *vals, int32_t nbucket, int64_t *lims, int nt = 0)

in-place bucket sort (with attention to memory=>int32) on input the values are in a nrow * col matrix we want to store the row numbers in the output.

Parameters:

• vals – positive values to sort, size nrow * ncol, max value nbucket - 1

• lims – output limits of buckets, size nbucket + 1

• nt – number of threads (0 = pure sequential code)

std::string get_compile_options()

get compile options

double getmillisecs()

ms elapsed since some arbitrary epoch

size_t get_mem_usage_kb()

get current RSS usage in kB

uint64_t get_cycles()

void fvec_madd(size_t n, const float *a, float bf, const float *b, float *c)

compute c := a + bf * b for a, b and c tables

Parameters:

• n – size of the tables

• a – size n

• b – size n

• c – restult table, size n

int fvec_madd_and_argmin(size_t n, const float *a, float bf, const float *b, float *c)

same as fvec_madd, also return index of the min of the result table

Returns:

index of the min of table c

void reflection(const float *u, float *x, size_t n, size_t d, size_t nu)

void matrix_qr(int m, int n, float *a)

compute the Q of the QR decomposition for m > n

Parameters:

a – size n * m: input matrix and output Q

void ranklist_handle_ties(int k, int64_t *idx, const float *dis)

distances are supposed to be sorted. Sorts indices with same distance

size_t ranklist_intersection_size(size_t k1, const int64_t *v1, size_t k2, const int64_t *v2)

count the number of common elements between v1 and v2 algorithm = sorting + bissection to avoid double-counting duplicates

size_t merge_result_table_with(size_t n, size_t k, int64_t *I0, float *D0, const int64_t *I1, const float *D1, bool keep_min = true, int64_t translation = 0)

merge a result table into another one

Parameters:

• I0, D0 – first result table, size (n, k)

• I1, D1 – second result table, size (n, k)

• keep_min – if true, keep min values, otherwise keep max

• translation – add this value to all I1’s indexes

Returns:

nb of values that were taken from the second table

double imbalance_factor(int n, int k, const int64_t *assign)

a balanced assignment has a IF of 1

double imbalance_factor(int k, const int *hist)

same, takes a histogram as input

int ivec_hist(size_t n, const int *v, int vmax, int *hist)

compute histogram on v

void bincode_hist(size_t n, size_t nbits, const uint8_t *codes, int *hist)

Compute histogram of bits on a code array

Parameters:

• codes – size(n, nbits / 8)

• hist – size(nbits): nb of 1s in the array of codes

size_t ivec_checksum(size_t n, const int32_t *a)

compute a checksum on a table.

const float *fvecs_maybe_subsample(size_t d, size_t *n, size_t nmax, const float *x, bool verbose = false, int64_t seed = 1234)

random subsamples a set of vectors if there are too many of them

Parameters:

• d – dimension of the vectors

• n – on input: nb of input vectors, output: nb of output vectors

• nmax – max nb of vectors to keep

• x – input array, size *n-by-d

• seed – random seed to use for sampling

Returns:

x or an array allocated with new [] with *n vectors

void binary_to_real(size_t d, const uint8_t *x_in, float *x_out)

Convert binary vector to +1/-1 valued float vector.

Parameters:

• d – dimension of the vector (multiple of 8)

• x_in – input binary vector (uint8_t table of size d / 8)

• x_out – output float vector (float table of size d)

void real_to_binary(size_t d, const float *x_in, uint8_t *x_out)

Convert float vector to binary vector. Components > 0 are converted to 1, others to 0.

Parameters:

• d – dimension of the vector (multiple of 8)

• x_in – input float vector (float table of size d)

• x_out – output binary vector (uint8_t table of size d / 8)

uint64_t hash_bytes(const uint8_t *bytes, int64_t n)

A reasonable hashing function

bool check_openmp()

Whether OpenMP annotations were respected.

Variables

FAISS_API int index2layer_sa_encode_bs

FAISS_API int index_factory_verbose

set to > 0 to get more logs from index_factory

const int IO_FLAG_READ_ONLY = 2

const int IO_FLAG_ONDISK_SAME_DIR = 4

const int IO_FLAG_SKIP_IVF_DATA = 8

const int IO_FLAG_SKIP_PRECOMPUTE_TABLE = 16

const int IO_FLAG_MMAP = IO_FLAG_SKIP_IVF_DATA | 0x646f0000

FAISS_API IndexBinaryHashStats indexBinaryHash_stats

FAISS_API FastScanStats FastScan_stats

FAISS_API bool check_compatible_for_merge_expensive_check

FAISS_API IndexIVFStats indexIVF_stats

FAISS_API IVFFastScanStats IVFFastScan_stats

FAISS_API size_t precomputed_table_max_bytes

FAISS_API int index_ivfpq_add_core_o_bs

FAISS_API IndexIVFPQStats indexIVFPQ_stats

FAISS_API IndexPQStats indexPQ_stats

FAISS_API int multi_index_quantizer_search_bs

FAISS_API int rowwise_minmax_sa_encode_bs

block size for performing sa_encode and sa_decode

FAISS_API int rowwise_minmax_sa_decode_bs

FAISS_API int distance_compute_blas_threshold

FAISS_API int distance_compute_blas_query_bs

FAISS_API int distance_compute_blas_database_bs

FAISS_API int distance_compute_min_k_reservoir

const uint8_t hamdis_tab_ham_bytes[256]

FAISS_API size_t hamming_batch_size

FAISS_API PartitionStats partition_stats

FAISS_API int bucket_sort_verbose

increase verbosity of the bucket_sort functions

struct AutoTuneCriterion

#include <AutoTune.h>

Evaluation criterion. Returns a performance measure in [0,1], higher is better.

Subclassed by faiss::IntersectionCriterion, faiss::OneRecallAtRCriterion

Public Functions

AutoTuneCriterion(idx_t nq, idx_t nnn)

void set_groundtruth(int gt_nnn, const float *gt_D_in, const idx_t *gt_I_in)

Intitializes the gt_D and gt_I vectors. Must be called before evaluating

Parameters:

• gt_D_in – size nq * gt_nnn

• gt_I_in – size nq * gt_nnn

virtual double evaluate(const float *D, const idx_t *I) const = 0

Evaluate the criterion.

Parameters:

• D – size nq * nnn

• I – size nq * nnn

Returns:

the criterion, between 0 and 1. Larger is better.

inline virtual ~AutoTuneCriterion()

Public Members

idx_t nq

nb of queries this criterion is evaluated on

idx_t nnn

nb of NNs that the query should request

idx_t gt_nnn

nb of GT NNs required to evaluate criterion

std::vector<float> gt_D

Ground-truth distances (size nq * gt_nnn)

std::vector<idx_t> gt_I

Ground-truth indexes (size nq * gt_nnn)

struct OneRecallAtRCriterion : public faiss::AutoTuneCriterion

Public Functions

OneRecallAtRCriterion(idx_t nq, idx_t R)

virtual double evaluate(const float *D, const idx_t *I) const override

Evaluate the criterion.

Parameters:

• D – size nq * nnn

• I – size nq * nnn

Returns:

the criterion, between 0 and 1. Larger is better.

inline ~OneRecallAtRCriterion() override

void set_groundtruth(int gt_nnn, const float *gt_D_in, const idx_t *gt_I_in)

Intitializes the gt_D and gt_I vectors. Must be called before evaluating

Parameters:

• gt_D_in – size nq * gt_nnn

• gt_I_in – size nq * gt_nnn

Public Members

idx_t R

idx_t nq

nb of queries this criterion is evaluated on

idx_t nnn

nb of NNs that the query should request

idx_t gt_nnn

nb of GT NNs required to evaluate criterion

std::vector<float> gt_D

Ground-truth distances (size nq * gt_nnn)

std::vector<idx_t> gt_I

Ground-truth indexes (size nq * gt_nnn)

struct IntersectionCriterion : public faiss::AutoTuneCriterion

Public Functions

IntersectionCriterion(idx_t nq, idx_t R)

virtual double evaluate(const float *D, const idx_t *I) const override

Evaluate the criterion.

Parameters:

• D – size nq * nnn

• I – size nq * nnn

Returns:

the criterion, between 0 and 1. Larger is better.

inline ~IntersectionCriterion() override

void set_groundtruth(int gt_nnn, const float *gt_D_in, const idx_t *gt_I_in)

Intitializes the gt_D and gt_I vectors. Must be called before evaluating

Parameters:

• gt_D_in – size nq * gt_nnn

• gt_I_in – size nq * gt_nnn

Public Members

idx_t R

idx_t nq

nb of queries this criterion is evaluated on

idx_t nnn

nb of NNs that the query should request

idx_t gt_nnn

nb of GT NNs required to evaluate criterion

std::vector<float> gt_D

Ground-truth distances (size nq * gt_nnn)

std::vector<idx_t> gt_I

Ground-truth indexes (size nq * gt_nnn)

struct OperatingPoint

#include <AutoTune.h>

Maintains a list of experimental results. Each operating point is a (perf, t, key) triplet, where higher perf and lower t is better. The key field is an arbitrary identifier for the operating point.

Includes primitives to extract the Pareto-optimal operating points in the (perf, t) space.

Public Members

double perf

performance measure (output of a Criterion)

double t

corresponding execution time (ms)

std::string key

key that identifies this op pt

int64_t cno

integer identifer

struct OperatingPoints

Public Functions

OperatingPoints()

int merge_with(const OperatingPoints &other, const std::string &prefix = "")

add operating points from other to this, with a prefix to the keys

void clear()

bool add(double perf, double t, const std::string &key, size_t cno = 0)

add a performance measure. Return whether it is an optimal point

double t_for_perf(double perf) const

get time required to obtain a given performance measure

void display(bool only_optimal = true) const

easy-to-read output

void all_to_gnuplot(const char *fname) const

output to a format easy to digest by gnuplot

void optimal_to_gnuplot(const char *fname) const

Public Members

std::vector<OperatingPoint> all_pts

all operating points

std::vector<OperatingPoint> optimal_pts

optimal operating points, sorted by perf

struct ParameterRange

#include <AutoTune.h>

possible values of a parameter, sorted from least to most expensive/accurate

Public Members

std::string name

std::vector<double> values

struct ParameterSpace

#include <AutoTune.h>

Uses a-priori knowledge on the Faiss indexes to extract tunable parameters.

Subclassed by faiss::gpu::GpuParameterSpace

Public Functions

ParameterSpace()

size_t n_combinations() const

nb of combinations, = product of values sizes

bool combination_ge(size_t c1, size_t c2) const

returns whether combinations c1 >= c2 in the tuple sense

std::string combination_name(size_t cno) const

get string representation of the combination

void display() const

print a description on stdout

ParameterRange &add_range(const std::string &name)

add a new parameter (or return it if it exists)

virtual void initialize(const Index *index)

initialize with reasonable parameters for the index

void set_index_parameters(Index *index, size_t cno) const

set a combination of parameters on an index

void set_index_parameters(Index *index, const char *param_string) const

set a combination of parameters described by a string

virtual void set_index_parameter(Index *index, const std::string &name, double val) const

set one of the parameters, returns whether setting was successful

void update_bounds(size_t cno, const OperatingPoint &op, double *upper_bound_perf, double *lower_bound_t) const

find an upper bound on the performance and a lower bound on t for configuration cno given another operating point op

void explore(Index *index, size_t nq, const float *xq, const AutoTuneCriterion &crit, OperatingPoints *ops) const

explore operating points

Parameters:

• index – index to run on

• xq – query vectors (size nq * index.d)

• crit – selection criterion

• ops – resulting operating points

inline virtual ~ParameterSpace()

Public Members

std::vector<ParameterRange> parameter_ranges

all tunable parameters

int verbose

verbosity during exploration

int n_experiments

nb of experiments during optimization (0 = try all combinations)

size_t batchsize

maximum number of queries to submit at a time.

bool thread_over_batches

use multithreading over batches (useful to benchmark independent single-searches)

double min_test_duration

run tests several times until they reach at least this duration (to avoid jittering in MT mode)

struct Cloner

#include <clone_index.h>

Cloner class, useful to override classes with other cloning functions. The cloning function above just calls Cloner::clone_Index.

Subclassed by faiss::gpu::ToCPUCloner, faiss::gpu::ToGpuCloner, faiss::gpu::ToGpuClonerMultiple

Public Functions

virtual VectorTransform *clone_VectorTransform(const VectorTransform*)

virtual Index *clone_Index(const Index*)

virtual IndexIVF *clone_IndexIVF(const IndexIVF*)

inline virtual ~Cloner()

struct ClusteringParameters

#include <Clustering.h>

Class for the clustering parameters. Can be passed to the constructor of the Clustering object.

Subclassed by faiss::Clustering, faiss::ProgressiveDimClusteringParameters

Public Functions

ClusteringParameters()

sets reasonable defaults

Public Members

int niter

clustering iterations

int nredo

redo clustering this many times and keep best

bool verbose

bool spherical

do we want normalized centroids?

bool int_centroids

round centroids coordinates to integer

bool update_index

re-train index after each iteration?

bool frozen_centroids

use the centroids provided as input and do not change them during iterations

int min_points_per_centroid

otherwise you get a warning

int max_points_per_centroid

to limit size of dataset

int seed

seed for the random number generator

size_t decode_block_size

how many vectors at a time to decode

struct ClusteringIterationStats

Public Members

float obj

objective values (sum of distances reported by index)

double time

seconds for iteration

double time_search

seconds for just search

double imbalance_factor

imbalance factor of iteration

int nsplit

number of cluster splits

struct Clustering : public faiss::ClusteringParameters

#include <Clustering.h>

K-means clustering based on assignment - centroid update iterations

The clustering is based on an Index object that assigns training points to the centroids. Therefore, at each iteration the centroids are added to the index.

On output, the centoids table is set to the latest version of the centroids and they are also added to the index. If the centroids table it is not empty on input, it is also used for initialization.

Subclassed by faiss::Clustering1D

Public Functions

Clustering(int d, int k)

Clustering(int d, int k, const ClusteringParameters &cp)

virtual void train(idx_t n, const float *x, faiss::Index &index, const float *x_weights = nullptr)

run k-means training

Parameters:

• x – training vectors, size n * d

• index – index used for assignment

• x_weights – weight associated to each vector: NULL or size n

void train_encoded(idx_t nx, const uint8_t *x_in, const Index *codec, Index &index, const float *weights = nullptr)

run with encoded vectors

win addition to train()’s parameters takes a codec as parameter to decode the input vectors.

Parameters:

codec – codec used to decode the vectors (nullptr = vectors are in fact floats) *

void post_process_centroids()

Post-process the centroids after each centroid update. includes optional L2 normalization and nearest integer rounding

inline virtual ~Clustering()

Public Members

size_t d

dimension of the vectors

size_t k

nb of centroids

std::vector<float> centroids

centroids (k * d) if centroids are set on input to train, they will be used as initialization

std::vector<ClusteringIterationStats> iteration_stats

stats at every iteration of clustering

int niter

clustering iterations

int nredo

redo clustering this many times and keep best

bool verbose

bool spherical

do we want normalized centroids?

bool int_centroids

round centroids coordinates to integer

bool update_index

re-train index after each iteration?

bool frozen_centroids

use the centroids provided as input and do not change them during iterations

int min_points_per_centroid

otherwise you get a warning

int max_points_per_centroid

to limit size of dataset

int seed

seed for the random number generator

size_t decode_block_size

how many vectors at a time to decode

struct Clustering1D : public faiss::Clustering

#include <Clustering.h>

Exact 1D clustering algorithm

Since it does not use an index, it does not overload the train() function

Public Functions

explicit Clustering1D(int k)

Clustering1D(int k, const ClusteringParameters &cp)

void train_exact(idx_t n, const float *x)

inline virtual ~Clustering1D()

virtual void train(idx_t n, const float *x, faiss::Index &index, const float *x_weights = nullptr)

run k-means training

Parameters:

• x – training vectors, size n * d

• index – index used for assignment

• x_weights – weight associated to each vector: NULL or size n

void train_encoded(idx_t nx, const uint8_t *x_in, const Index *codec, Index &index, const float *weights = nullptr)

run with encoded vectors

win addition to train()’s parameters takes a codec as parameter to decode the input vectors.

Parameters:

codec – codec used to decode the vectors (nullptr = vectors are in fact floats) *

void post_process_centroids()

Post-process the centroids after each centroid update. includes optional L2 normalization and nearest integer rounding

Public Members

size_t d

dimension of the vectors

size_t k

nb of centroids

std::vector<float> centroids

centroids (k * d) if centroids are set on input to train, they will be used as initialization

std::vector<ClusteringIterationStats> iteration_stats

stats at every iteration of clustering

int niter

clustering iterations

int nredo

redo clustering this many times and keep best

bool verbose

bool spherical

do we want normalized centroids?

bool int_centroids

round centroids coordinates to integer

bool update_index

re-train index after each iteration?

bool frozen_centroids

use the centroids provided as input and do not change them during iterations

int min_points_per_centroid

otherwise you get a warning

int max_points_per_centroid

to limit size of dataset

int seed

seed for the random number generator

size_t decode_block_size

how many vectors at a time to decode

struct ProgressiveDimClusteringParameters : public faiss::ClusteringParameters

Subclassed by faiss::ProgressiveDimClustering

Public Functions

ProgressiveDimClusteringParameters()

Public Members

int progressive_dim_steps

number of incremental steps

bool apply_pca

apply PCA on input

int niter

clustering iterations

int nredo

redo clustering this many times and keep best

bool verbose

bool spherical

do we want normalized centroids?

bool int_centroids

round centroids coordinates to integer

bool update_index

re-train index after each iteration?

bool frozen_centroids

use the centroids provided as input and do not change them during iterations

int min_points_per_centroid

otherwise you get a warning

int max_points_per_centroid

to limit size of dataset

int seed

seed for the random number generator

size_t decode_block_size

how many vectors at a time to decode

struct ProgressiveDimIndexFactory

#include <Clustering.h>

generates an index suitable for clustering when called

Subclassed by faiss::gpu::GpuProgressiveDimIndexFactory

Public Functions

virtual Index *operator()(int dim)

ownership transferred to caller

inline virtual ~ProgressiveDimIndexFactory()

struct ProgressiveDimClustering : public faiss::ProgressiveDimClusteringParameters

#include <Clustering.h>

K-means clustering with progressive dimensions used

The clustering first happens in dim 1, then with exponentially increasing dimension until d (I steps). This is typically applied after a PCA transformation (optional). Reference:

“Improved Residual Vector Quantization for High-dimensional Approximate

Nearest Neighbor Search”

Shicong Liu, Hongtao Lu, Junru Shao, AAAI’15

https://arxiv.org/abs/1509.05195

Public Functions

ProgressiveDimClustering(int d, int k)

ProgressiveDimClustering(int d, int k, const ProgressiveDimClusteringParameters &cp)

void train(idx_t n, const float *x, ProgressiveDimIndexFactory &factory)

inline virtual ~ProgressiveDimClustering()

Public Members

size_t d

dimension of the vectors

size_t k

nb of centroids

std::vector<float> centroids

centroids (k * d)

std::vector<ClusteringIterationStats> iteration_stats

stats at every iteration of clustering

int progressive_dim_steps

number of incremental steps

bool apply_pca

apply PCA on input

int niter

clustering iterations

int nredo

redo clustering this many times and keep best

bool verbose

bool spherical

do we want normalized centroids?

bool int_centroids

round centroids coordinates to integer

bool update_index

re-train index after each iteration?

bool frozen_centroids

use the centroids provided as input and do not change them during iterations

int min_points_per_centroid

otherwise you get a warning

int max_points_per_centroid

to limit size of dataset

int seed

seed for the random number generator

size_t decode_block_size

how many vectors at a time to decode

struct SearchParameters

#include <Index.h>

Parent class for the optional search paramenters.

Sub-classes with additional search parameters should inherit this class. Ownership of the object fields is always to the caller.

Subclassed by faiss::SearchParametersIVF, faiss::SearchParametersPQ, faiss::SearchParametersPreTransform

Public Functions

inline virtual ~SearchParameters()

make sure we can dynamic_cast this

Public Members

IDSelector *sel = nullptr

if non-null, only these IDs will be considered during search.

struct Index

#include <Index.h>

Abstract structure for an index, supports adding vectors and searching them.

All vectors provided at add or search time are 32-bit float arrays, although the internal representation may vary.

Subclassed by faiss::AdditiveCoarseQuantizer, faiss::IndexFastScan, faiss::IndexFlatCodes, faiss::IndexHNSW, faiss::IndexIVF, faiss::IndexLattice, faiss::IndexNNDescent, faiss::IndexNSG, faiss::IndexPreTransform, faiss::IndexRandom, faiss::IndexRefine, faiss::IndexRowwiseMinMaxBase, faiss::IndexSplitVectors, faiss::MultiIndexQuantizer, faiss::gpu::GpuIndex

Public Types

using component_t = float

using distance_t = float

Public Functions

inline explicit Index(idx_t d = 0, MetricType metric = METRIC_L2)

virtual ~Index()

virtual void train(idx_t n, const float *x)

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void add(idx_t n, const float *x) = 0

Add n vectors of dimension d to the index.

Vectors are implicitly assigned labels ntotal .. ntotal + n - 1 This function slices the input vectors in chunks smaller than blocksize_add and calls add_core.

Parameters:

x – input matrix, size n * d

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const = 0

query n vectors of dimension d to the index.

return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

• distances – output pairwise distances, size n*k

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual void reset() = 0

removes all elements from the database.

virtual size_t remove_ids(const IDSelector &sel)

removes IDs from the index. Not supported by all indexes. Returns the number of elements removed.

virtual void reconstruct(idx_t key, float *recons) const

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual void reconstruct_batch(idx_t n, const idx_t *keys, float *recons) const

Reconstruct several stored vectors (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• n – number of vectors to reconstruct

• keys – ids of the vectors to reconstruct (size n)

• recons – reconstucted vector (size n * d)

virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const

Reconstruct vectors i0 to i0 + ni - 1

this function may not be defined for some indexes

Parameters:

recons – reconstucted vector (size ni * d)

virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons, const SearchParameters *params = nullptr) const

Similar to search, but also reconstructs the stored vectors (or an approximation in the case of lossy coding) for the search results.

If there are not enough results for a query, the resulting arrays is padded with -1s.

Parameters:

recons – reconstructed vectors size (n, k, d)

virtual void compute_residual(const float *x, float *residual, idx_t key) const

Computes a residual vector after indexing encoding.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• x – input vector, size d

• residual – output residual vector, size d

• key – encoded index, as returned by search and assign

virtual void compute_residual_n(idx_t n, const float *xs, float *residuals, const idx_t *keys) const

Computes a residual vector after indexing encoding (batch form). Equivalent to calling compute_residual for each vector.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• n – number of vectors

• xs – input vectors, size (n x d)

• residuals – output residual vectors, size (n x d)

• keys – encoded index, as returned by search and assign

virtual DistanceComputer *get_distance_computer() const

Get a DistanceComputer (defined in AuxIndexStructures) object for this kind of index.

DistanceComputer is implemented for indexes that support random access of their vectors.

virtual size_t sa_code_size() const

size of the produced codes in bytes

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const

encode a set of vectors

Parameters:

• n – number of vectors

• x – input vectors, size n * d

• bytes – output encoded vectors, size n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const

decode a set of vectors

Parameters:

• n – number of vectors

• bytes – input encoded vectors, size n * sa_code_size()

• x – output vectors, size n * d

virtual void merge_from(Index &otherIndex, idx_t add_id = 0)

moves the entries from another dataset to self. On output, other is empty. add_id is added to all moved ids (for sequential ids, this would be this->ntotal)

virtual void check_compatible_for_merge(const Index &otherIndex) const

check that the two indexes are compatible (ie, they are trained in the same way and have the same parameters). Otherwise throw.

Public Members

int d

vector dimension

idx_t ntotal

total nb of indexed vectors

bool verbose

verbosity level

bool is_trained

set if the Index does not require training, or if training is done already

MetricType metric_type

type of metric this index uses for search

float metric_arg

argument of the metric type

struct Index2Layer : public faiss::IndexFlatCodes

#include <Index2Layer.h>

Same as an IndexIVFPQ without the inverted lists: codes are stored sequentially

The class is mainly inteded to store encoded vectors that can be accessed randomly, the search function is not implemented.

Public Types

using component_t = float

using distance_t = float

Public Functions

Index2Layer(Index *quantizer, size_t nlist, int M, int nbit = 8, MetricType metric = METRIC_L2)

Index2Layer()

~Index2Layer()

virtual void train(idx_t n, const float *x) override

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

not implemented

virtual DistanceComputer *get_distance_computer() const override

Get a DistanceComputer (defined in AuxIndexStructures) object for this kind of index.

DistanceComputer is implemented for indexes that support random access of their vectors.

void transfer_to_IVFPQ(IndexIVFPQ &other) const

transfer the flat codes to an IVFPQ index

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

encode a set of vectors

Parameters:

• n – number of vectors

• x – input vectors, size n * d

• bytes – output encoded vectors, size n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

decode a set of vectors

Parameters:

• n – number of vectors

• bytes – input encoded vectors, size n * sa_code_size()

• x – output vectors, size n * d

virtual void add(idx_t n, const float *x) override

default add uses sa_encode

virtual void reset() override

removes all elements from the database.

virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const override

reconstruction using the codec interface

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual size_t sa_code_size() const override

size of the produced codes in bytes

virtual size_t remove_ids(const IDSelector &sel) override

remove some ids. NB that Because of the structure of the indexing structure, the semantics of this operation are different from the usual ones: the new ids are shifted

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const

a FlatCodesDistanceComputer offers a distance_to_code method

virtual void check_compatible_for_merge(const Index &otherIndex) const override

check that the two indexes are compatible (ie, they are trained in the same way and have the same parameters). Otherwise throw.

virtual void merge_from(Index &otherIndex, idx_t add_id = 0) override

moves the entries from another dataset to self. On output, other is empty. add_id is added to all moved ids (for sequential ids, this would be this->ntotal)

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual void reconstruct_batch(idx_t n, const idx_t *keys, float *recons) const

Reconstruct several stored vectors (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• n – number of vectors to reconstruct

• keys – ids of the vectors to reconstruct (size n)

• recons – reconstucted vector (size n * d)

virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons, const SearchParameters *params = nullptr) const

Similar to search, but also reconstructs the stored vectors (or an approximation in the case of lossy coding) for the search results.

If there are not enough results for a query, the resulting arrays is padded with -1s.

Parameters:

recons – reconstructed vectors size (n, k, d)

virtual void compute_residual(const float *x, float *residual, idx_t key) const

Computes a residual vector after indexing encoding.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• x – input vector, size d

• residual – output residual vector, size d

• key – encoded index, as returned by search and assign

virtual void compute_residual_n(idx_t n, const float *xs, float *residuals, const idx_t *keys) const

Computes a residual vector after indexing encoding (batch form). Equivalent to calling compute_residual for each vector.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• n – number of vectors

• xs – input vectors, size (n x d)

• residuals – output residual vectors, size (n x d)

• keys – encoded index, as returned by search and assign

Public Members

Level1Quantizer q1

first level quantizer

ProductQuantizer pq

second level quantizer is always a PQ

size_t code_size_1

size of the code for the first level (ceil(log8(q1.nlist)))

size_t code_size_2

size of the code for the second level

size_t code_size

std::vector<uint8_t> codes

encoded dataset, size ntotal * code_size

int d

vector dimension

idx_t ntotal

total nb of indexed vectors

bool verbose

verbosity level

bool is_trained

set if the Index does not require training, or if training is done already

MetricType metric_type

type of metric this index uses for search

float metric_arg

argument of the metric type

struct IndexAdditiveQuantizer : public faiss::IndexFlatCodes

#include <IndexAdditiveQuantizer.h>

Abstract class for additive quantizers. The search functions are in common.

Subclassed by faiss::IndexLocalSearchQuantizer, faiss::IndexProductLocalSearchQuantizer, faiss::IndexProductResidualQuantizer, faiss::IndexResidualQuantizer

Public Types

using Search_type_t = AdditiveQuantizer::Search_type_t

using component_t = float

using distance_t = float

Public Functions

explicit IndexAdditiveQuantizer(idx_t d, AdditiveQuantizer *aq, MetricType metric = METRIC_L2)

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

query n vectors of dimension d to the index.

return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

• distances – output pairwise distances, size n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

encode a set of vectors

Parameters:

• n – number of vectors

• x – input vectors, size n * d

• bytes – output encoded vectors, size n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

decode a set of vectors

Parameters:

• n – number of vectors

• bytes – input encoded vectors, size n * sa_code_size()

• x – output vectors, size n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

a FlatCodesDistanceComputer offers a distance_to_code method

virtual void add(idx_t n, const float *x) override

default add uses sa_encode

virtual void reset() override

removes all elements from the database.

virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const override

reconstruction using the codec interface

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual size_t sa_code_size() const override

size of the produced codes in bytes

virtual size_t remove_ids(const IDSelector &sel) override

remove some ids. NB that Because of the structure of the indexing structure, the semantics of this operation are different from the usual ones: the new ids are shifted

inline virtual DistanceComputer *get_distance_computer() const override

Get a DistanceComputer (defined in AuxIndexStructures) object for this kind of index.

DistanceComputer is implemented for indexes that support random access of their vectors.

virtual void check_compatible_for_merge(const Index &otherIndex) const override

check that the two indexes are compatible (ie, they are trained in the same way and have the same parameters). Otherwise throw.

virtual void merge_from(Index &otherIndex, idx_t add_id = 0) override

moves the entries from another dataset to self. On output, other is empty. add_id is added to all moved ids (for sequential ids, this would be this->ntotal)

virtual void train(idx_t n, const float *x)

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual void reconstruct_batch(idx_t n, const idx_t *keys, float *recons) const

Reconstruct several stored vectors (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• n – number of vectors to reconstruct

• keys – ids of the vectors to reconstruct (size n)

• recons – reconstucted vector (size n * d)

virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons, const SearchParameters *params = nullptr) const

Similar to search, but also reconstructs the stored vectors (or an approximation in the case of lossy coding) for the search results.

If there are not enough results for a query, the resulting arrays is padded with -1s.

Parameters:

recons – reconstructed vectors size (n, k, d)

virtual void compute_residual(const float *x, float *residual, idx_t key) const

Computes a residual vector after indexing encoding.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• x – input vector, size d

• residual – output residual vector, size d

• key – encoded index, as returned by search and assign

virtual void compute_residual_n(idx_t n, const float *xs, float *residuals, const idx_t *keys) const

Computes a residual vector after indexing encoding (batch form). Equivalent to calling compute_residual for each vector.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• n – number of vectors

• xs – input vectors, size (n x d)

• residuals – output residual vectors, size (n x d)

• keys – encoded index, as returned by search and assign

Public Members

AdditiveQuantizer *aq

size_t code_size

std::vector<uint8_t> codes

encoded dataset, size ntotal * code_size

int d

vector dimension

idx_t ntotal

total nb of indexed vectors

bool verbose

verbosity level

bool is_trained

set if the Index does not require training, or if training is done already

MetricType metric_type

type of metric this index uses for search

float metric_arg

argument of the metric type

struct IndexResidualQuantizer : public faiss::IndexAdditiveQuantizer

#include <IndexAdditiveQuantizer.h>

Index based on a residual quantizer. Stored vectors are approximated by residual quantization codes. Can also be used as a codec

Public Types

using Search_type_t = AdditiveQuantizer::Search_type_t

using component_t = float

using distance_t = float

Public Functions

IndexResidualQuantizer(int d, size_t M, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

Constructor.

Parameters:

• d – dimensionality of the input vectors

• M – number of subquantizers

• nbits – number of bit per subvector index

• d – dimensionality of the input vectors

• M – number of subquantizers

• nbits – number of bit per subvector index

IndexResidualQuantizer(int d, const std::vector<size_t> &nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

IndexResidualQuantizer()

virtual void train(idx_t n, const float *x) override

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

query n vectors of dimension d to the index.

return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

• distances – output pairwise distances, size n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

encode a set of vectors

Parameters:

• n – number of vectors

• x – input vectors, size n * d

• bytes – output encoded vectors, size n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

decode a set of vectors

Parameters:

• n – number of vectors

• bytes – input encoded vectors, size n * sa_code_size()

• x – output vectors, size n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

a FlatCodesDistanceComputer offers a distance_to_code method

virtual void add(idx_t n, const float *x) override

default add uses sa_encode

virtual void reset() override

removes all elements from the database.

virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const override

reconstruction using the codec interface

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual size_t sa_code_size() const override

size of the produced codes in bytes

virtual size_t remove_ids(const IDSelector &sel) override

remove some ids. NB that Because of the structure of the indexing structure, the semantics of this operation are different from the usual ones: the new ids are shifted

inline virtual DistanceComputer *get_distance_computer() const override

Get a DistanceComputer (defined in AuxIndexStructures) object for this kind of index.

DistanceComputer is implemented for indexes that support random access of their vectors.

virtual void check_compatible_for_merge(const Index &otherIndex) const override

check that the two indexes are compatible (ie, they are trained in the same way and have the same parameters). Otherwise throw.

virtual void merge_from(Index &otherIndex, idx_t add_id = 0) override

moves the entries from another dataset to self. On output, other is empty. add_id is added to all moved ids (for sequential ids, this would be this->ntotal)

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual void reconstruct_batch(idx_t n, const idx_t *keys, float *recons) const

Reconstruct several stored vectors (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• n – number of vectors to reconstruct

• keys – ids of the vectors to reconstruct (size n)

• recons – reconstucted vector (size n * d)

virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons, const SearchParameters *params = nullptr) const

Similar to search, but also reconstructs the stored vectors (or an approximation in the case of lossy coding) for the search results.

If there are not enough results for a query, the resulting arrays is padded with -1s.

Parameters:

recons – reconstructed vectors size (n, k, d)

virtual void compute_residual(const float *x, float *residual, idx_t key) const

Computes a residual vector after indexing encoding.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• x – input vector, size d

• residual – output residual vector, size d

• key – encoded index, as returned by search and assign

virtual void compute_residual_n(idx_t n, const float *xs, float *residuals, const idx_t *keys) const

Computes a residual vector after indexing encoding (batch form). Equivalent to calling compute_residual for each vector.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• n – number of vectors

• xs – input vectors, size (n x d)

• residuals – output residual vectors, size (n x d)

• keys – encoded index, as returned by search and assign

Public Members

ResidualQuantizer rq

The residual quantizer used to encode the vectors.

AdditiveQuantizer *aq

size_t code_size

std::vector<uint8_t> codes

encoded dataset, size ntotal * code_size

int d

vector dimension

idx_t ntotal

total nb of indexed vectors

bool verbose

verbosity level

bool is_trained

set if the Index does not require training, or if training is done already

MetricType metric_type

type of metric this index uses for search

float metric_arg

argument of the metric type

struct IndexLocalSearchQuantizer : public faiss::IndexAdditiveQuantizer

Public Types

using Search_type_t = AdditiveQuantizer::Search_type_t

using component_t = float

using distance_t = float

Public Functions

IndexLocalSearchQuantizer(int d, size_t M, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

Constructor.

Parameters:

• d – dimensionality of the input vectors

• M – number of subquantizers

• nbits – number of bit per subvector index

• d – dimensionality of the input vectors

• M – number of subquantizers

• nbits – number of bit per subvector index

IndexLocalSearchQuantizer()

virtual void train(idx_t n, const float *x) override

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

query n vectors of dimension d to the index.

return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

• distances – output pairwise distances, size n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

encode a set of vectors

Parameters:

• n – number of vectors

• x – input vectors, size n * d

• bytes – output encoded vectors, size n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

decode a set of vectors

Parameters:

• n – number of vectors

• bytes – input encoded vectors, size n * sa_code_size()

• x – output vectors, size n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

a FlatCodesDistanceComputer offers a distance_to_code method

virtual void add(idx_t n, const float *x) override

default add uses sa_encode

virtual void reset() override

removes all elements from the database.

virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const override

reconstruction using the codec interface

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual size_t sa_code_size() const override

size of the produced codes in bytes

virtual size_t remove_ids(const IDSelector &sel) override

remove some ids. NB that Because of the structure of the indexing structure, the semantics of this operation are different from the usual ones: the new ids are shifted

inline virtual DistanceComputer *get_distance_computer() const override

Get a DistanceComputer (defined in AuxIndexStructures) object for this kind of index.

DistanceComputer is implemented for indexes that support random access of their vectors.

virtual void check_compatible_for_merge(const Index &otherIndex) const override

check that the two indexes are compatible (ie, they are trained in the same way and have the same parameters). Otherwise throw.

virtual void merge_from(Index &otherIndex, idx_t add_id = 0) override

moves the entries from another dataset to self. On output, other is empty. add_id is added to all moved ids (for sequential ids, this would be this->ntotal)

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual void reconstruct_batch(idx_t n, const idx_t *keys, float *recons) const

Reconstruct several stored vectors (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• n – number of vectors to reconstruct

• keys – ids of the vectors to reconstruct (size n)

• recons – reconstucted vector (size n * d)

virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons, const SearchParameters *params = nullptr) const

Similar to search, but also reconstructs the stored vectors (or an approximation in the case of lossy coding) for the search results.

If there are not enough results for a query, the resulting arrays is padded with -1s.

Parameters:

recons – reconstructed vectors size (n, k, d)

virtual void compute_residual(const float *x, float *residual, idx_t key) const

Computes a residual vector after indexing encoding.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• x – input vector, size d

• residual – output residual vector, size d

• key – encoded index, as returned by search and assign

virtual void compute_residual_n(idx_t n, const float *xs, float *residuals, const idx_t *keys) const

Computes a residual vector after indexing encoding (batch form). Equivalent to calling compute_residual for each vector.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• n – number of vectors

• xs – input vectors, size (n x d)

• residuals – output residual vectors, size (n x d)

• keys – encoded index, as returned by search and assign

Public Members

LocalSearchQuantizer lsq

AdditiveQuantizer *aq

size_t code_size

std::vector<uint8_t> codes

encoded dataset, size ntotal * code_size

int d

vector dimension

idx_t ntotal

total nb of indexed vectors

bool verbose

verbosity level

bool is_trained

set if the Index does not require training, or if training is done already

MetricType metric_type

type of metric this index uses for search

float metric_arg

argument of the metric type

struct IndexProductResidualQuantizer : public faiss::IndexAdditiveQuantizer

#include <IndexAdditiveQuantizer.h>

Index based on a product residual quantizer.

Public Types

using Search_type_t = AdditiveQuantizer::Search_type_t

using component_t = float

using distance_t = float

Public Functions

IndexProductResidualQuantizer(int d, size_t nsplits, size_t Msub, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

Constructor.

Parameters:

• d – dimensionality of the input vectors

• nsplits – number of residual quantizers

• Msub – number of subquantizers per RQ

• nbits – number of bit per subvector index

• d – dimensionality of the input vectors

• nsplits – number of residual quantizers

• Msub – number of subquantizers per RQ

• nbits – number of bit per subvector index

IndexProductResidualQuantizer()

virtual void train(idx_t n, const float *x) override

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

query n vectors of dimension d to the index.

return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

• distances – output pairwise distances, size n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

encode a set of vectors

Parameters:

• n – number of vectors

• x – input vectors, size n * d

• bytes – output encoded vectors, size n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

decode a set of vectors

Parameters:

• n – number of vectors

• bytes – input encoded vectors, size n * sa_code_size()

• x – output vectors, size n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

a FlatCodesDistanceComputer offers a distance_to_code method

virtual void add(idx_t n, const float *x) override

default add uses sa_encode

virtual void reset() override

removes all elements from the database.

virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const override

reconstruction using the codec interface

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual size_t sa_code_size() const override

size of the produced codes in bytes

virtual size_t remove_ids(const IDSelector &sel) override

remove some ids. NB that Because of the structure of the indexing structure, the semantics of this operation are different from the usual ones: the new ids are shifted

inline virtual DistanceComputer *get_distance_computer() const override

Get a DistanceComputer (defined in AuxIndexStructures) object for this kind of index.

DistanceComputer is implemented for indexes that support random access of their vectors.

virtual void check_compatible_for_merge(const Index &otherIndex) const override

check that the two indexes are compatible (ie, they are trained in the same way and have the same parameters). Otherwise throw.

virtual void merge_from(Index &otherIndex, idx_t add_id = 0) override

moves the entries from another dataset to self. On output, other is empty. add_id is added to all moved ids (for sequential ids, this would be this->ntotal)

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual void reconstruct_batch(idx_t n, const idx_t *keys, float *recons) const

Reconstruct several stored vectors (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• n – number of vectors to reconstruct

• keys – ids of the vectors to reconstruct (size n)

• recons – reconstucted vector (size n * d)

virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons, const SearchParameters *params = nullptr) const

Similar to search, but also reconstructs the stored vectors (or an approximation in the case of lossy coding) for the search results.

If there are not enough results for a query, the resulting arrays is padded with -1s.

Parameters:

recons – reconstructed vectors size (n, k, d)

virtual void compute_residual(const float *x, float *residual, idx_t key) const

Computes a residual vector after indexing encoding.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• x – input vector, size d

• residual – output residual vector, size d

• key – encoded index, as returned by search and assign

virtual void compute_residual_n(idx_t n, const float *xs, float *residuals, const idx_t *keys) const

Computes a residual vector after indexing encoding (batch form). Equivalent to calling compute_residual for each vector.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• n – number of vectors

• xs – input vectors, size (n x d)

• residuals – output residual vectors, size (n x d)

• keys – encoded index, as returned by search and assign

Public Members

ProductResidualQuantizer prq

The product residual quantizer used to encode the vectors.

AdditiveQuantizer *aq

size_t code_size

std::vector<uint8_t> codes

encoded dataset, size ntotal * code_size

int d

vector dimension

idx_t ntotal

total nb of indexed vectors

bool verbose

verbosity level

bool is_trained

set if the Index does not require training, or if training is done already

MetricType metric_type

type of metric this index uses for search

float metric_arg

argument of the metric type

struct IndexProductLocalSearchQuantizer : public faiss::IndexAdditiveQuantizer

#include <IndexAdditiveQuantizer.h>

Index based on a product local search quantizer.

Public Types

using Search_type_t = AdditiveQuantizer::Search_type_t

using component_t = float

using distance_t = float

Public Functions

IndexProductLocalSearchQuantizer(int d, size_t nsplits, size_t Msub, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

Constructor.

Parameters:

• d – dimensionality of the input vectors

• nsplits – number of local search quantizers

• Msub – number of subquantizers per LSQ

• nbits – number of bit per subvector index

• d – dimensionality of the input vectors

• nsplits – number of local search quantizers

• Msub – number of subquantizers per LSQ

• nbits – number of bit per subvector index

IndexProductLocalSearchQuantizer()

virtual void train(idx_t n, const float *x) override

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

query n vectors of dimension d to the index.

return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

• distances – output pairwise distances, size n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

encode a set of vectors

Parameters:

• n – number of vectors

• x – input vectors, size n * d

• bytes – output encoded vectors, size n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

decode a set of vectors

Parameters:

• n – number of vectors

• bytes – input encoded vectors, size n * sa_code_size()

• x – output vectors, size n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

a FlatCodesDistanceComputer offers a distance_to_code method

virtual void add(idx_t n, const float *x) override

default add uses sa_encode

virtual void reset() override

removes all elements from the database.

virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const override

reconstruction using the codec interface

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual size_t sa_code_size() const override

size of the produced codes in bytes

virtual size_t remove_ids(const IDSelector &sel) override

remove some ids. NB that Because of the structure of the indexing structure, the semantics of this operation are different from the usual ones: the new ids are shifted

inline virtual DistanceComputer *get_distance_computer() const override

Get a DistanceComputer (defined in AuxIndexStructures) object for this kind of index.

DistanceComputer is implemented for indexes that support random access of their vectors.

virtual void check_compatible_for_merge(const Index &otherIndex) const override

check that the two indexes are compatible (ie, they are trained in the same way and have the same parameters). Otherwise throw.

virtual void merge_from(Index &otherIndex, idx_t add_id = 0) override

moves the entries from another dataset to self. On output, other is empty. add_id is added to all moved ids (for sequential ids, this would be this->ntotal)

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual void reconstruct_batch(idx_t n, const idx_t *keys, float *recons) const

Reconstruct several stored vectors (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• n – number of vectors to reconstruct

• keys – ids of the vectors to reconstruct (size n)

• recons – reconstucted vector (size n * d)

virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons, const SearchParameters *params = nullptr) const

Similar to search, but also reconstructs the stored vectors (or an approximation in the case of lossy coding) for the search results.

If there are not enough results for a query, the resulting arrays is padded with -1s.

Parameters:

recons – reconstructed vectors size (n, k, d)

virtual void compute_residual(const float *x, float *residual, idx_t key) const

Computes a residual vector after indexing encoding.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• x – input vector, size d

• residual – output residual vector, size d

• key – encoded index, as returned by search and assign

virtual void compute_residual_n(idx_t n, const float *xs, float *residuals, const idx_t *keys) const

Computes a residual vector after indexing encoding (batch form). Equivalent to calling compute_residual for each vector.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• n – number of vectors

• xs – input vectors, size (n x d)

• residuals – output residual vectors, size (n x d)

• keys – encoded index, as returned by search and assign

Public Members

ProductLocalSearchQuantizer plsq

The product local search quantizer used to encode the vectors.

AdditiveQuantizer *aq

size_t code_size

std::vector<uint8_t> codes

encoded dataset, size ntotal * code_size

int d

vector dimension

idx_t ntotal

total nb of indexed vectors

bool verbose

verbosity level

bool is_trained

set if the Index does not require training, or if training is done already

MetricType metric_type

type of metric this index uses for search

float metric_arg

argument of the metric type

struct AdditiveCoarseQuantizer : public faiss::Index

#include <IndexAdditiveQuantizer.h>

A “virtual” index where the elements are the residual quantizer centroids.

Intended for use as a coarse quantizer in an IndexIVF.

Subclassed by faiss::LocalSearchCoarseQuantizer, faiss::ResidualCoarseQuantizer

Public Types

using component_t = float

using distance_t = float

Public Functions

explicit AdditiveCoarseQuantizer(idx_t d = 0, AdditiveQuantizer *aq = nullptr, MetricType metric = METRIC_L2)

virtual void add(idx_t n, const float *x) override

N/A.

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

query n vectors of dimension d to the index.

return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

• distances – output pairwise distances, size n*k

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual void train(idx_t n, const float *x) override

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void reset() override

N/A.

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual size_t remove_ids(const IDSelector &sel)

removes IDs from the index. Not supported by all indexes. Returns the number of elements removed.

virtual void reconstruct_batch(idx_t n, const idx_t *keys, float *recons) const

Reconstruct several stored vectors (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• n – number of vectors to reconstruct

• keys – ids of the vectors to reconstruct (size n)

• recons – reconstucted vector (size n * d)

virtual void reconstruct_n(idx_t i0, idx_t ni, float *recons) const

Reconstruct vectors i0 to i0 + ni - 1

this function may not be defined for some indexes

Parameters:

recons – reconstucted vector (size ni * d)

virtual void search_and_reconstruct(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, float *recons, const SearchParameters *params = nullptr) const

Similar to search, but also reconstructs the stored vectors (or an approximation in the case of lossy coding) for the search results.

If there are not enough results for a query, the resulting arrays is padded with -1s.

Parameters:

recons – reconstructed vectors size (n, k, d)

virtual void compute_residual(const float *x, float *residual, idx_t key) const

Computes a residual vector after indexing encoding.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• x – input vector, size d

• residual – output residual vector, size d

• key – encoded index, as returned by search and assign

virtual void compute_residual_n(idx_t n, const float *xs, float *residuals, const idx_t *keys) const

Computes a residual vector after indexing encoding (batch form). Equivalent to calling compute_residual for each vector.

The residual vector is the difference between a vector and the reconstruction that can be decoded from its representation in the index. The residual can be used for multiple-stage indexing methods, like IndexIVF’s methods.

Parameters:

• n – number of vectors

• xs – input vectors, size (n x d)

• residuals – output residual vectors, size (n x d)

• keys – encoded index, as returned by search and assign

virtual DistanceComputer *get_distance_computer() const

Get a DistanceComputer (defined in AuxIndexStructures) object for this kind of index.

DistanceComputer is implemented for indexes that support random access of their vectors.

virtual size_t sa_code_size() const

size of the produced codes in bytes

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const

encode a set of vectors

Parameters:

• n – number of vectors

• x – input vectors, size n * d

• bytes – output encoded vectors, size n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const

decode a set of vectors

Parameters:

• n – number of vectors

• bytes – input encoded vectors, size n * sa_code_size()

• x – output vectors, size n * d

virtual void merge_from(Index &otherIndex, idx_t add_id = 0)

moves the entries from another dataset to self. On output, other is empty. add_id is added to all moved ids (for sequential ids, this would be this->ntotal)

virtual void check_compatible_for_merge(const Index &otherIndex) const

check that the two indexes are compatible (ie, they are trained in the same way and have the same parameters). Otherwise throw.

Public Members

AdditiveQuantizer *aq

std::vector<float> centroid_norms

norms of centroids, useful for knn-search

int d

vector dimension

idx_t ntotal

total nb of indexed vectors

bool verbose

verbosity level

bool is_trained

set if the Index does not require training, or if training is done already

MetricType metric_type

type of metric this index uses for search

float metric_arg

argument of the metric type

struct ResidualCoarseQuantizer : public faiss::AdditiveCoarseQuantizer

#include <IndexAdditiveQuantizer.h>

The ResidualCoarseQuantizer is a bit specialized compared to the default AdditiveCoarseQuantizer because it can use a beam search at search time (slow but may be useful for very large vocabularies)

Public Types

using component_t = float

using distance_t = float

Public Functions

void set_beam_factor(float new_beam_factor)

computes centroid norms if required

ResidualCoarseQuantizer(int d, size_t M, size_t nbits, MetricType metric = METRIC_L2)

Constructor.

Parameters:

• d – dimensionality of the input vectors

• M – number of subquantizers

• nbits – number of bit per subvector index

• d – dimensionality of the input vectors

• M – number of subquantizers

• nbits – number of bit per subvector index

ResidualCoarseQuantizer(int d, const std::vector<size_t> &nbits, MetricType metric = METRIC_L2)

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

query n vectors of dimension d to the index.

return at most k vectors. If there are not enough results for a query, the result array is padded with -1s.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

• distances – output pairwise distances, size n*k

ResidualCoarseQuantizer()

virtual void add(idx_t n, const float *x) override

N/A.

virtual void reconstruct(idx_t key, float *recons) const override

Reconstruct a stored vector (or an approximation if lossy coding)

this function may not be defined for some indexes

Parameters:

• key – id of the vector to reconstruct

• recons – reconstucted vector (size d)

virtual void train(idx_t n, const float *x) override

Perform training on a representative set of vectors

Parameters:

• n – nb of training vectors

• x – training vecors, size n * d

virtual void reset() override

N/A.

virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids)

Same as add, but stores xids instead of sequential ids.

The default implementation fails with an assertion, as it is not supported by all indexes.

Parameters:

xids – if non-null, ids to store for the vectors (size n)

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const

query n vectors of dimension d to the index.

return all vectors with distance < radius. Note that many indexes do not implement the range_search (only the k-NN search is mandatory).

Parameters:

• x – input vectors to search, size n * d

• radius – search radius

• result – result table

virtual void assign(idx_t n, const float *x, idx_t *labels, idx_t k = 1) const

return the indexes of the k vectors closest to the query x.

This function is identical as search but only return labels of neighbors.

Parameters:

• x – input vectors to search, size n * d

• labels – output labels of the NNs, size n*k

virtual size_t remove_ids(const IDSelector &sel)

removes IDs from the index. Not supported by all indexes. Returns the number of elements removed.

virtual void reconstruct_batch(