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.

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. IDSelector is intended to define a subset of vectors to handle (for removal or as subset to search)

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. PQ4 SIMD packing and accumulation functions

The basic kernel accumulates nq query vectors with bbs = nb * 2 * 16 vectors and produces an output matrix for that. It is interesting for nq * nb <= 4, otherwise register spilling becomes too large.

The implementation of these functions is spread over 3 cpp files to reduce parallel compile times. Templates are instantiated explicitly.

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. This file contains callbacks for kernels that compute distances.

The SIMDResultHandler object is intended to be templated and inlined. Methods:

• handle(): called when 32 distances are computed and provided in two simd16uint16. (q, b) indicate which entry it is in the block.

• set_block_origin(): set the sub-matrix that is being computed

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

enumerator METRIC_Jaccard

defined as: sum_i(min(a_i, b_i)) / sum_i(max(a_i, b_i)) where a_i, b_i > 0

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

template<typename PQDecoderT>
inline float distance_single_code_generic(const size_t M, const size_t nbits, const float *sim_table, const uint8_t *code)

Returns the distance to a single code.

template<typename PQDecoderT> inline void distance_four_codes_generic (const size_t M, const size_t nbits, const float *sim_table, const uint8_t *__restrict code0, const uint8_t *__restrict code1, const uint8_t *__restrict code2, const uint8_t *__restrict code3, float &result0, float &result1, float &result2, float &result3)

Combines 4 operations of distance_single_code() General-purpose version.

template<typename PQDecoderT>
inline float distance_single_code(const size_t M, const size_t nbits, const float *sim_table, const uint8_t *code)

template<typename PQDecoderT> inline void distance_four_codes (const size_t M, const size_t nbits, const float *sim_table, const uint8_t *__restrict code0, const uint8_t *__restrict code1, const uint8_t *__restrict code2, const uint8_t *__restrict code3, float &result0, float &result1, float &result2, float &result3)

void handleExceptions(std::vector<std::pair<int, std::exception_ptr>> &exceptions)

Handle multiple exceptions from worker threads, throwing an appropriate exception that aggregates the information The pair int is the thread that generated the exception

std::string demangle_cpp_symbol(const char *name)

make typeids more readable

uint32_t fourcc(const char sx[4])

cast a 4-character string to a uint32_t that can be written and read easily

uint32_t fourcc(const std::string &sx)

void fourcc_inv(uint32_t x, char str[5])

std::string fourcc_inv(uint32_t x)

std::string fourcc_inv_printable(uint32_t x)

void smawk(const idx_t nrows, const idx_t ncols, const float *x, idx_t *argmins)

SMAWK algorithm. Find the row minima of a monotone matrix.

Expose this for testing.

Parameters:

• nrows – number of rows

• ncols – number of columns

• x – input matrix, size (nrows, ncols)

• argmins – argmin of each row

double kmeans1d(const float *x, size_t n, size_t nclusters, float *centroids)

Exact 1D K-Means by dynamic programming

From “Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D” Allan Grønlund, Kasper Green Larsen, Alexander Mathiasen, Jesper Sindahl Nielsen, Stefan Schneider, Mingzhou Song, ArXiV’17

Section 2.2

https://arxiv.org/abs/1701.07204

Parameters:

• x – input 1D array

• n – input array length

• nclusters – number of clusters

• centroids – output centroids, size nclusters

Returns:

imbalancce factor

void pq4_pack_codes(const uint8_t *codes, size_t ntotal, size_t M, size_t nb, size_t bbs, size_t nsq, uint8_t *blocks)

Pack codes for consumption by the SIMD kernels. The unused bytes are set to 0.

Parameters:

• codes – input codes, size (ntotal, ceil(M / 2))

• ntotal – number of input codes

• nb – output number of codes (ntotal rounded up to a multiple of bbs)

• nsq – number of sub-quantizers (=M rounded up to a muliple of 2)

• bbs – size of database blocks (multiple of 32)

• blocks – output array, size nb * nsq / 2.

void pq4_pack_codes_range(const uint8_t *codes, size_t M, size_t i0, size_t i1, size_t bbs, size_t nsq, uint8_t *blocks)

Same as pack_codes but write in a given range of the output, leaving the rest untouched. Assumes allocated entries are 0 on input.

Parameters:

• codes – input codes, size (i1 - i0, ceil(M / 2))

• i0 – first output code to write

• i1 – last output code to write

• blocks – output array, size at least ceil(i1 / bbs) * bbs * nsq / 2

uint8_t pq4_get_packed_element(const uint8_t *data, size_t bbs, size_t nsq, size_t vector_id, size_t sq)

get a single element from a packed codes table

Parameters:

• vector_id – vector id

• sq – subquantizer (< nsq)

void pq4_set_packed_element(uint8_t *data, uint8_t code, size_t bbs, size_t nsq, size_t vector_id, size_t sq)

set a single element “code” into a packed codes table

Parameters:

• vector_id – vector id

• sq – subquantizer (< nsq)

void pq4_pack_LUT(int nq, int nsq, const uint8_t *src, uint8_t *dest)

Pack Look-up table for consumption by the kernel.

Parameters:

• nq – number of queries

• nsq – number of sub-quantizers (muliple of 2)

• src – input array, size (nq, 16)

• dest – output array, size (nq, 16)

template<class ResultHandler, class Scaler>
void pq4_accumulate_loop(int nq, size_t nb, int bbs, int nsq, const uint8_t *codes, const uint8_t *LUT, ResultHandler &res, const Scaler &scaler)

Loop over database elements and accumulate results into result handler

Parameters:

• nq – number of queries

• nb – number of database elements

• bbs – size of database blocks (multiple of 32)

• nsq – number of sub-quantizers (muliple of 2)

• codes – packed codes array

• LUT – packed look-up table

• scaler – scaler to scale the encoded norm

int pq4_qbs_to_nq(int qbs)

int pq4_preferred_qbs(int nq)

return the preferred decomposition in blocks for a nb of queries.

int pq4_pack_LUT_qbs(int fqbs, int nsq, const uint8_t *src, uint8_t *dest)

Pack Look-up table for consumption by the kernel.

Parameters:

• qbs – 4-bit encoded number of query blocks, the total number of queries handled (nq) is deduced from it

• nsq – number of sub-quantizers (muliple of 2)

• src – input array, size (nq, 16)

• dest – output array, size (nq, 16)

Returns:

nq

int pq4_pack_LUT_qbs_q_map(int qbs, int nsq, const uint8_t *src, const int *q_map, uint8_t *dest)

Same as pq4_pack_LUT_qbs, except the source vectors are remapped with q_map

template<class ResultHandler, class Scaler>
void pq4_accumulate_loop_qbs(int qbs, size_t nb, int nsq, const uint8_t *codes, const uint8_t *LUT, ResultHandler &res, const Scaler &scaler)

Run accumulation loop.

Parameters:

• qbs – 4-bit encoded number of queries

• nb – number of database codes (mutliple of bbs)

• nsq – number of sub-quantizers

• codes – encoded database vectors (packed)

• LUT – look-up table (packed)

• res – call-back for the resutls

• scaler – scaler to scale the encoded norm

void beam_search_encode_step(size_t d, size_t K, const float *cent, size_t n, size_t beam_size, const float *residuals, size_t m, const int32_t *codes, size_t new_beam_size, int32_t *new_codes, float *new_residuals, float *new_distances, Index *assign_index = nullptr, ApproxTopK_mode_t approx_topk = ApproxTopK_mode_t::EXACT_TOPK)

Encode a residual by sampling from a centroid table.

This is a single encoding step the residual quantizer. It allows low-level access to the encoding function, exposed mainly for unit tests.

Parameters:

• n – number of vectors to hanlde

• residuals – vectors to encode, size (n, beam_size, d)

• cent – centroids, size (K, d)

• beam_size – input beam size

• m – size of the codes for the previous encoding steps

• codes – code array for the previous steps of the beam (n, beam_size, m)

• new_beam_size – output beam size (should be <= K * beam_size)

• new_codes – output codes, size (n, new_beam_size, m + 1)

• new_residuals – output residuals, size (n, new_beam_size, d)

• new_distances – output distances, size (n, new_beam_size)

• assign_index – if non-NULL, will be used to perform assignment

void beam_search_encode_step_tab(size_t K, size_t n, size_t beam_size, const float *codebook_cross_norms, size_t ldc, const uint64_t *codebook_offsets, const float *query_cp, size_t ldqc, const float *cent_norms_i, size_t m, const int32_t *codes, const float *distances, size_t new_beam_size, int32_t *new_codes, float *new_distances, ApproxTopK_mode_t approx_topk = ApproxTopK_mode_t::EXACT_TOPK)

Encode a set of vectors using their dot products with the codebooks

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 by_residual, 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)

constexpr bool is_similarity_metric(MetricType metric_type)

this function is used to distinguish between min and max indexes since we need to support similarity and dis-similarity metrics in a flexible way

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 fvec_inner_product_batch_4(const float *x, const float *y0, const float *y1, const float *y2, const float *y3, const size_t d, float &dis0, float &dis1, float &dis2, float &dis3)

Special version of inner product that computes 4 distances between x and yi, which is performance oriented.

void fvec_L2sqr_batch_4(const float *x, const float *y0, const float *y1, const float *y2, const float *y3, const size_t d, float &dis0, float &dis1, float &dis2, float &dis3)

Special version of L2sqr that computes 4 distances between x and yi, which is performance oriented.

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)

void fvec_L2sqr_ny_transposed(float *dis, const float *x, const float *y, const float *y_sqlen, size_t d, size_t d_offset, 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)

template<class C>
void knn_extra_metrics(const float *x, const float *y, size_t d, size_t nx, size_t ny, MetricType mt, float metric_arg, HeapArray<C> *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)

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])

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, ApproxTopK_mode_t approx_topk_mode = ApproxTopK_mode_t::EXACT_TOPK)

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)

• approx_topk_mode – allows to use approximate top-k facilities to speedup heap

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)

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

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)

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)

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)

inline int popcount32(uint32_t x)

inline int popcount64(uint64_t x)

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<class idx_t, class C>
void merge_knn_results(size_t n, size_t k, typename C::TI nshard, const typename C::T *all_distances, const idx_t *all_labels, typename C::T *distances, idx_t *labels)

Merge result tables from several shards. The per-shard results are assumed to be sorted. Note that the C comparator is reversed w.r.t. the usual top-k element heap because we want the best (ie. lowest for L2) result to be on top, not the worst. Also, it needs to hold an index of a shard id (ie. usually int32 is more than enough).

Parameters:

• all_distances – size (nshard, n, k)

• all_labels – size (nshard, n, k)

• distances – output distances, size (n, k)

• labels – output labels, size (n, k)

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 simd16uint16 hadd(const simd16uint16 &a, const simd16uint16 &b)

inline void cmplt_min_max_fast(const simd16uint16 candidateValues, const simd16uint16 candidateIndices, const simd16uint16 currentValues, const simd16uint16 currentIndices, simd16uint16 &minValues, simd16uint16 &minIndices, simd16uint16 &maxValues, simd16uint16 &maxIndices)

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 void cmplt_min_max_fast(const simd8uint32 candidateValues, const simd8uint32 candidateIndices, const simd8uint32 currentValues, const simd8uint32 currentIndices, simd8uint32 &minValues, simd8uint32 &minIndices, simd8uint32 &maxValues, simd8uint32 &maxIndices)

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 void cmplt_min_max_fast(const simd8float32 candidateValues, const simd8uint32 candidateIndices, const simd8float32 currentValues, const simd8uint32 currentIndices, simd8float32 &minValues, simd8uint32 &minIndices, simd8float32 &maxValues, simd8uint32 &maxIndices)

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)

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

same with int64 elements

void hashtable_int64_to_int64_init(int log2_capacity, int64_t *tab)

Hashtable implementation for int64 -> int64 with external storage implemented for fast batch add and lookup.

tab is of size 2 * (1 << log2_capacity) n is the number of elements to add or search

adding several values in a same batch: an arbitrary one gets added in different batches: the newer batch overwrites. raises an exception if capacity is exhausted.

void hashtable_int64_to_int64_add(int log2_capacity, int64_t *tab, size_t n, const int64_t *keys, const int64_t *vals)

void hashtable_int64_to_int64_lookup(int log2_capacity, const int64_t *tab, size_t n, const int64_t *keys, int64_t *vals)

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

uint64_t ivec_checksum(size_t n, const int32_t *a)

compute a checksum on a table.

uint64_t bvec_checksum(size_t n, const uint8_t *a)

compute a checksum on a table.

void bvecs_checksum(size_t n, size_t d, const uint8_t *a, uint64_t *cs)

compute checksums for the rows of a matrix

Parameters:

• n – number of rows

• d – size per row

• a – matrix to handle, size n * d

• cs – output checksums, size n

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 HNSWStats hnsw_stats

FAISS_API int product_quantizer_compute_codes_bs

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

FAISS_API size_t hamming_batch_size

static constexpr uint8_t hamdis_tab_ham_bytes[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}

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 AdditiveQuantizer : public faiss::Quantizer

#include <AdditiveQuantizer.h>

Abstract structure for additive quantizers

Different from the product quantizer in which the decoded vector is the concatenation of M sub-vectors, additive quantizers sum M sub-vectors to get the decoded vector.

Subclassed by faiss::LocalSearchQuantizer, faiss::ProductAdditiveQuantizer, faiss::ResidualQuantizer

Public Types

enum Search_type_t

Encodes how search is performed and how vectors are encoded.

Values:

enumerator ST_decompress

decompress database vector

enumerator ST_LUT_nonorm

use a LUT, don’t include norms (OK for IP or normalized vectors)

enumerator ST_norm_from_LUT

compute the norms from the look-up tables (cost is in O(M^2))

enumerator ST_norm_float

use a LUT, and store float32 norm with the vectors

enumerator ST_norm_qint8

use a LUT, and store 8bit-quantized norm

enumerator ST_norm_qint4

enumerator ST_norm_cqint8

use a LUT, and store non-uniform quantized norm

enumerator ST_norm_cqint4

enumerator ST_norm_lsq2x4

use a 2x4 bits lsq as norm quantizer (for fast scan)

enumerator ST_norm_rq2x4

use a 2x4 bits rq as norm quantizer (for fast scan)

Public Functions

uint64_t encode_norm(float norm) const

encode a norm into norm_bits bits

uint32_t encode_qcint(float x) const

encode norm by non-uniform scalar quantization

float decode_qcint(uint32_t c) const

decode norm by non-uniform scalar quantization

AdditiveQuantizer(size_t d, const std::vector<size_t> &nbits, Search_type_t search_type = ST_decompress)

AdditiveQuantizer()

compute derived values when d, M and nbits have been set

void set_derived_values()

Train the norm quantizer.

void train_norm(size_t n, const float *norms)

inline virtual void compute_codes(const float *x, uint8_t *codes, size_t n) const override

Quantize a set of vectors

Parameters:

• x – input vectors, size n * d

• codes – output codes, size n * code_size

virtual void compute_codes_add_centroids(const float *x, uint8_t *codes, size_t n, const float *centroids = nullptr) const = 0

Encode a set of vectors

Parameters:

• x – vectors to encode, size n * d

• codes – output codes, size n * code_size

• centroids – centroids to be added to x, size n * d

void pack_codes(size_t n, const int32_t *codes, uint8_t *packed_codes, int64_t ld_codes = -1, const float *norms = nullptr, const float *centroids = nullptr) const

pack a series of code to bit-compact format

Parameters:

• codes – codes to be packed, size n * code_size

• packed_codes – output bit-compact codes

• ld_codes – leading dimension of codes

• norms – norms of the vectors (size n). Will be computed if needed but not provided

• centroids – centroids to be added to x, size n * d

virtual void decode(const uint8_t *codes, float *x, size_t n) const override

Decode a set of vectors

Parameters:

• codes – codes to decode, size n * code_size

• x – output vectors, size n * d

virtual void decode_unpacked(const int32_t *codes, float *x, size_t n, int64_t ld_codes = -1) const

Decode a set of vectors in non-packed format

Parameters:

• codes – codes to decode, size n * ld_codes

• x – output vectors, size n * d

template<bool is_IP, Search_type_t effective_search_type>
float compute_1_distance_LUT(const uint8_t *codes, const float *LUT) const

void decode_64bit(idx_t n, float *x) const

decoding function for a code in a 64-bit word

virtual void compute_LUT(size_t n, const float *xq, float *LUT, float alpha = 1.0f, long ld_lut = -1) const

Compute inner-product look-up tables. Used in the centroid search functions.

Parameters:

• xq – query vector, size (n, d)

• LUT – look-up table, size (n, total_codebook_size)

• alpha – compute alpha * inner-product

• ld_lut – leading dimension of LUT

void knn_centroids_inner_product(idx_t n, const float *xq, idx_t k, float *distances, idx_t *labels) const

exact IP search

void compute_centroid_norms(float *norms) const

For L2 search we need the L2 norms of the centroids

Parameters:

norms – output norms table, size total_codebook_size

void knn_centroids_L2(idx_t n, const float *xq, idx_t k, float *distances, idx_t *labels, const float *centroid_norms) const

Exact L2 search, with precomputed norms

virtual ~AdditiveQuantizer()

virtual void train(size_t n, const float *x) = 0

Train the quantizer

Parameters:

x – training vectors, size n * d

Public Members

size_t M

number of codebooks

std::vector<size_t> nbits

bits for each step

std::vector<float> codebooks

codebooks

std::vector<uint64_t> codebook_offsets

size_t tot_bits = 0

total number of bits (indexes + norms)

size_t norm_bits = 0

bits allocated for the norms

size_t total_codebook_size = 0

size of the codebook in vectors

bool only_8bit = false

are all nbits = 8 (use faster decoder)

bool verbose = false

verbose during training?

bool is_trained = false

is trained or not

IndexFlat1D qnorm

store and search norms

std::vector<float> norm_tabs

store norms of codebook entries for 4-bit fastscan search

size_t max_mem_distances = 5 * (size_t(1) << 30)

norms and distance matrixes with beam search can get large, so use this to control for the amount of memory that can be allocated

Search_type_t search_type

Also determines what’s in the codes.

float norm_min = NAN

min/max for quantization of norms

float norm_max = NAN

size_t d

size of the input vectors

size_t code_size

bytes per indexed vector

struct RangeSearchResult

#include <AuxIndexStructures.h>

The objective is to have a simple result structure while minimizing the number of mem copies in the result. The method do_allocation can be overloaded to allocate the result tables in the matrix type of a scripting language like Lua or Python.

Public Functions

explicit RangeSearchResult(size_t nq, bool alloc_lims = true)

lims must be allocated on input to range_search.

virtual void do_allocation()

called when lims contains the nb of elements result entries for each query

virtual ~RangeSearchResult()

Public Members

size_t nq

nb of queries

size_t *lims

size (nq + 1)

idx_t *labels

result for query i is labels[lims[i]:lims[i+1]]

float *distances

corresponding distances (not sorted)

size_t buffer_size

size of the result buffers used

struct BufferList

#include <AuxIndexStructures.h>

List of temporary buffers used to store results before they are copied to the RangeSearchResult object.

Subclassed by faiss::RangeSearchPartialResult

Public Functions

explicit BufferList(size_t buffer_size)

~BufferList()

void append_buffer()

create a new buffer

void add(idx_t id, float dis)

add one result, possibly appending a new buffer if needed

void copy_range(size_t ofs, size_t n, idx_t *dest_ids, float *dest_dis)

copy elemnts ofs:ofs+n-1 seen as linear data in the buffers to tables dest_ids, dest_dis

Public Members

size_t buffer_size

std::vector<Buffer> buffers

size_t wp

write pointer in the last buffer.

struct Buffer

Public Members

idx_t *ids

float *dis

struct RangeQueryResult

#include <AuxIndexStructures.h>

result structure for a single query

Public Functions

void add(float dis, idx_t id)

called by search function to report a new result

Public Members

idx_t qno

size_t nres

RangeSearchPartialResult *pres

struct RangeSearchPartialResult : public faiss::BufferList

#include <AuxIndexStructures.h>

the entries in the buffers are split per query

Public Functions

explicit RangeSearchPartialResult(RangeSearchResult *res_in)

eventually the result will be stored in res_in

RangeQueryResult &new_result(idx_t qno)

begin a new result

void finalize()

void set_lims()

called by range_search before do_allocation

void copy_result(bool incremental = false)

called by range_search after do_allocation

void append_buffer()

create a new buffer

void add(idx_t id, float dis)

add one result, possibly appending a new buffer if needed

void copy_range(size_t ofs, size_t n, idx_t *dest_ids, float *dest_dis)

copy elemnts ofs:ofs+n-1 seen as linear data in the buffers to tables dest_ids, dest_dis

Public Members

RangeSearchResult *res

std::vector<RangeQueryResult> queries

query ids + nb of results per query.

size_t buffer_size

std::vector<Buffer> buffers

size_t wp

write pointer in the last buffer.

Public Static Functions

static void merge(std::vector<RangeSearchPartialResult*> &partial_results, bool do_delete = true)

merge a set of PartialResult’s into one RangeSearchResult on ouptut the partialresults are empty!

struct InterruptCallback

Public Functions

virtual bool want_interrupt() = 0

inline virtual ~InterruptCallback()

Public Static Functions

static void clear_instance()

static void check()

check if:

• an interrupt callback is set

• the callback returns true if this is the case, then throw an exception. Should not be called from multiple threads.

static bool is_interrupted()

same as check() but return true if is interrupted instead of throwing. Can be called from multiple threads.

static size_t get_period_hint(size_t flops)

assuming each iteration takes a certain number of flops, what is a reasonable interval to check for interrupts?

Public Static Attributes

static std::mutex lock

static std::unique_ptr<InterruptCallback> instance

struct VisitedTable

#include <AuxIndexStructures.h>

set implementation optimized for fast access.

Public Functions

inline explicit VisitedTable(int size)

inline void set(int no)

set flag #no to true

inline bool get(int no) const

get flag #no

inline void advance()

reset all flags to false

Public Members

std::vector<uint8_t> visited

uint8_t visno

struct CodePacker

#include <CodePacker.h>

Packing consists in combining a fixed number of codes of constant size (code_size) into a block of data where they may (or may not) be interleaved for efficient consumption by distance computation kernels. This exists for the “fast_scan” indexes on CPU and for some GPU kernels.

Subclassed by faiss::CodePackerFlat, faiss::CodePackerPQ4

Public Functions

virtual void pack_1(const uint8_t *flat_code, size_t offset, uint8_t *block) const = 0

virtual void unpack_1(const uint8_t *block, size_t offset, uint8_t *flat_code) const = 0

virtual void pack_all(const uint8_t *flat_codes, uint8_t *block) const

virtual void unpack_all(const uint8_t *block, uint8_t *flat_codes) const

inline virtual ~CodePacker()

Public Members

size_t code_size

size_t nvec

size_t block_size

struct CodePackerFlat : public faiss::CodePacker

#include <CodePacker.h>

Trivial code packer where codes are stored one by one

Public Functions

explicit CodePackerFlat(size_t code_size)

virtual void pack_1(const uint8_t *flat_code, size_t offset, uint8_t *block) const final

virtual void unpack_1(const uint8_t *block, size_t offset, uint8_t *flat_code) const final

virtual void pack_all(const uint8_t *flat_codes, uint8_t *block) const final

virtual void unpack_all(const uint8_t *block, uint8_t *flat_codes) const final

Public Members

size_t code_size

size_t nvec

size_t block_size

struct DistanceComputer

Subclassed by faiss::FlatCodesDistanceComputer

Public Functions

virtual void set_query(const float *x) = 0

called before computing distances. Pointer x should remain valid while operator () is called

virtual float operator()(idx_t i) = 0

compute distance of vector i to current query

inline virtual void distances_batch_4(const idx_t idx0, const idx_t idx1, const idx_t idx2, const idx_t idx3, float &dis0, float &dis1, float &dis2, float &dis3)

compute distances of current query to 4 stored vectors. certain DistanceComputer implementations may benefit heavily from this.

virtual float symmetric_dis(idx_t i, idx_t j) = 0

compute distance between two stored vectors

inline virtual ~DistanceComputer()

struct FlatCodesDistanceComputer : public faiss::DistanceComputer

Subclassed by faiss::ScalarQuantizer::SQDistanceComputer

Public Functions

inline FlatCodesDistanceComputer(const uint8_t *codes, size_t code_size)

inline FlatCodesDistanceComputer()

inline virtual float operator()(idx_t i) override

compute distance of vector i to current query

virtual float distance_to_code(const uint8_t *code) = 0

compute distance of current query to an encoded vector

inline virtual ~FlatCodesDistanceComputer()

virtual void set_query(const float *x) = 0

called before computing distances. Pointer x should remain valid while operator () is called

inline virtual void distances_batch_4(const idx_t idx0, const idx_t idx1, const idx_t idx2, const idx_t idx3, float &dis0, float &dis1, float &dis2, float &dis3)

compute distances of current query to 4 stored vectors. certain DistanceComputer implementations may benefit heavily from this.

virtual float symmetric_dis(idx_t i, idx_t j) = 0

compute distance between two stored vectors

Public Members

const uint8_t *codes

size_t code_size

class FaissException : public std::exception

#include <FaissException.h>

Base class for Faiss exceptions.

Public Functions

explicit FaissException(const std::string &msg)

FaissException(const std::string &msg, const char *funcName, const char *file, int line)

const char *what() const noexcept override

from std::exception

Public Members

std::string msg

template<class T>
struct ScopeDeleter

#include <FaissException.h>

bare-bones unique_ptr this one deletes with delete []

Public Functions

inline explicit ScopeDeleter(const T *ptr = nullptr)

inline void release()

inline void set(const T *ptr_in)

inline void swap(ScopeDeleter<T> &other)

inline ~ScopeDeleter()

Public Members

const T *ptr

template<class T>
struct ScopeDeleter1

#include <FaissException.h>

same but deletes with the simple delete (least common case)

Public Functions

inline explicit ScopeDeleter1(const T *ptr = nullptr)

inline void release()

inline void set(const T *ptr_in)

inline void swap(ScopeDeleter1<T> &other)

inline ~ScopeDeleter1()

Public Members

const T *ptr

struct TransformedVectors

#include <FaissException.h>

RAII object for a set of possibly transformed vectors (deallocated only if they are indeed transformed)

Public Functions

inline TransformedVectors(const float *x_orig, const float *x)

inline ~TransformedVectors()

Public Members

const float *x

bool own_x

struct SearchParametersHNSW : public faiss::SearchParameters

Public Functions

inline ~SearchParametersHNSW()

Public Members

int efSearch = 16

bool check_relative_distance = true

IDSelector *sel = nullptr

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

struct HNSW

Public Types

using storage_idx_t = int32_t

internal storage of vectors (32 bits: this is expensive)

typedef std::pair<float, storage_idx_t> Node

Public Functions

void set_default_probas(int M, float levelMult)

initialize the assign_probas and cum_nneighbor_per_level to have 2*M links on level 0 and M links on levels > 0

void set_nb_neighbors(int level_no, int n)

set nb of neighbors for this level (before adding anything)

int nb_neighbors(int layer_no) const

nb of neighbors for this level

int cum_nb_neighbors(int layer_no) const

cumumlative nb up to (and excluding) this level

void neighbor_range(idx_t no, int layer_no, size_t *begin, size_t *end) const

range of entries in the neighbors table of vertex no at layer_no

explicit HNSW(int M = 32)

only mandatory parameter: nb of neighbors

int random_level()

pick a random level for a new point

void fill_with_random_links(size_t n)

add n random levels to table (for debugging…)

void add_links_starting_from(DistanceComputer &ptdis, storage_idx_t pt_id, storage_idx_t nearest, float d_nearest, int level, omp_lock_t *locks, VisitedTable &vt)

void add_with_locks(DistanceComputer &ptdis, int pt_level, int pt_id, std::vector<omp_lock_t> &locks, VisitedTable &vt)

add point pt_id on all levels <= pt_level and build the link structure for them.

HNSWStats search(DistanceComputer &qdis, int k, idx_t *I, float *D, VisitedTable &vt, const SearchParametersHNSW *params = nullptr) const

search interface for 1 point, single thread

void search_level_0(DistanceComputer &qdis, int k, idx_t *idxi, float *simi, idx_t nprobe, const storage_idx_t *nearest_i, const float *nearest_d, int search_type, HNSWStats &search_stats, VisitedTable &vt) const

search only in level 0 from a given vertex

void reset()

void clear_neighbor_tables(int level)

void print_neighbor_stats(int level) const

int prepare_level_tab(size_t n, bool preset_levels = false)

void permute_entries(const idx_t *map)

Public Members

std::vector<double> assign_probas

assignment probability to each layer (sum=1)

std::vector<int> cum_nneighbor_per_level

number of neighbors stored per layer (cumulative), should not be changed after first add

std::vector<int> levels

level of each vector (base level = 1), size = ntotal

std::vector<size_t> offsets

offsets[i] is the offset in the neighbors array where vector i is stored size ntotal + 1

std::vector<storage_idx_t> neighbors

neighbors[offsets[i]:offsets[i+1]] is the list of neighbors of vector i for all levels. this is where all storage goes.

storage_idx_t entry_point = -1

entry point in the search structure (one of the points with maximum level

faiss::RandomGenerator rng

int max_level = -1

maximum level

int efConstruction = 40

expansion factor at construction time

int efSearch = 16

expansion factor at search time

bool check_relative_distance = true

during search: do we check whether the next best distance is good enough?

int upper_beam = 1

number of entry points in levels > 0.

bool search_bounded_queue = true

use bounded queue during exploration

Public Static Functions

static void shrink_neighbor_list(DistanceComputer &qdis, std::priority_queue<NodeDistFarther> &input, std::vector<NodeDistFarther> &output, int max_size)

struct MinimaxHeap

#include <HNSW.h>

Heap structure that allows fast

Public Types

typedef faiss::CMax<float, storage_idx_t> HC

Public Functions

inline explicit MinimaxHeap(int n)

void push(storage_idx_t i, float v)

float max() const

int size() const

void clear()

int pop_min(float *vmin_out = nullptr)

int count_below(float thresh)

Public Members

int n

int k

int nvalid

std::vector<storage_idx_t> ids

std::vector<float> dis

struct NodeDistCloser

#include <HNSW.h>

to sort pairs of (id, distance) from nearest to fathest or the reverse

Public Functions

inline NodeDistCloser(float d, int id)

inline bool operator<(const NodeDistCloser &obj1) const

Public Members

float d

int id

struct NodeDistFarther

Public Functions

inline NodeDistFarther(float d, int id)

inline bool operator<(const NodeDistFarther &obj1) const

Public Members

float d

int id

struct HNSWStats

Public Functions

inline HNSWStats(size_t n1 = 0, size_t n2 = 0, size_t n3 = 0, size_t ndis = 0, size_t nreorder = 0)

inline void reset()

inline void combine(const HNSWStats &other)

Public Members

size_t n1

size_t n2

size_t n3

size_t ndis

size_t nreorder

struct IDSelector

#include <IDSelector.h>

Encapsulates a set of ids to handle.

Subclassed by PyCallbackIDSelector, faiss::IDSelectorAll, faiss::IDSelectorAnd, faiss::IDSelectorArray, faiss::IDSelectorBatch, faiss::IDSelectorBitmap, faiss::IDSelectorNot, faiss::IDSelectorOr, faiss::IDSelectorRange, faiss::IDSelectorTranslated, faiss::IDSelectorXOr

Public Functions

virtual bool is_member(idx_t id) const = 0

inline virtual ~IDSelector()

struct IDSelectorRange : public faiss::IDSelector

#include <IDSelector.h>

ids between [imin, imax)

Public Functions

IDSelectorRange(idx_t imin, idx_t imax, bool assume_sorted = false)

virtual bool is_member(idx_t id) const final

void find_sorted_ids_bounds(size_t list_size, const idx_t *ids, size_t *jmin, size_t *jmax) const

for sorted ids, find the range of list indices where the valid ids are stored

inline ~IDSelectorRange() override

Public Members

idx_t imin

idx_t imax

bool assume_sorted

Assume that the ids to handle are sorted. In some cases this can speed up processing

struct IDSelectorArray : public faiss::IDSelector

#include <IDSelector.h>

Simple array of elements

is_member calls are very inefficient, but some operations can use the ids directly.

Public Functions

IDSelectorArray(size_t n, const idx_t *ids)

Construct with an array of ids to process

Parameters:

• n – number of ids to store

• ids – elements to store. The pointer should remain valid during IDSelectorArray’s lifetime

virtual bool is_member(idx_t id) const final

inline ~IDSelectorArray() override

Public Members

size_t n

const idx_t *ids

struct IDSelectorBatch : public faiss::IDSelector

#include <IDSelector.h>

Ids from a set.

Repetitions of ids in the indices set passed to the constructor does not hurt performance.

The hash function used for the bloom filter and GCC’s implementation of unordered_set are just the least significant bits of the id. This works fine for random ids or ids in sequences but will produce many hash collisions if lsb’s are always the same

Public Functions

IDSelectorBatch(size_t n, const idx_t *indices)

Construct with an array of ids to process

Parameters:

• n – number of ids to store

• ids – elements to store. The pointer can be released after construction

virtual bool is_member(idx_t id) const final

inline ~IDSelectorBatch() override

Public Members

std::unordered_set<idx_t> set

std::vector<uint8_t> bloom

int nbits

idx_t mask

struct IDSelectorBitmap : public faiss::IDSelector

#include <IDSelector.h>

One bit per element. Constructed with a bitmap, size ceil(n / 8).

Public Functions

IDSelectorBitmap(size_t n, const uint8_t *bitmap)

Construct with a binary mask

Parameters:

• n – size of the bitmap array

• bitmap – id will be selected iff id / 8 < n and bit number (i%8) of bitmap[floor(i / 8)] is 1.

virtual bool is_member(idx_t id) const final

inline ~IDSelectorBitmap() override

Public Members

size_t n

const uint8_t *bitmap

struct IDSelectorNot : public faiss::IDSelector

#include <IDSelector.h>

reverts the membership test of another selector

Public Functions

inline IDSelectorNot(const IDSelector *sel)

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorNot()

Public Members

const IDSelector *sel

struct IDSelectorAll : public faiss::IDSelector

#include <IDSelector.h>

selects all entries (useful for benchmarking)

Public Functions

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorAll()

struct IDSelectorAnd : public faiss::IDSelector

#include <IDSelector.h>

does an AND operation on the the two given IDSelector’s is_membership results.

Public Functions

inline IDSelectorAnd(const IDSelector *lhs, const IDSelector *rhs)

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorAnd()

Public Members

const IDSelector *lhs

const IDSelector *rhs

struct IDSelectorOr : public faiss::IDSelector

#include <IDSelector.h>

does an OR operation on the the two given IDSelector’s is_membership results.

Public Functions

inline IDSelectorOr(const IDSelector *lhs, const IDSelector *rhs)

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorOr()

Public Members

const IDSelector *lhs

const IDSelector *rhs

struct IDSelectorXOr : public faiss::IDSelector

#include <IDSelector.h>

does an XOR operation on the the two given IDSelector’s is_membership results.

Public Functions

inline IDSelectorXOr(const IDSelector *lhs, const IDSelector *rhs)

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorXOr()

Public Members

const IDSelector *lhs

const IDSelector *rhs

struct IOReader

Subclassed by PyCallbackIOReader, faiss::BufferedIOReader, faiss::FileIOReader, faiss::VectorIOReader

Public Functions

virtual size_t operator()(void *ptr, size_t size, size_t nitems) = 0

virtual int fileno()

inline virtual ~IOReader()

Public Members

std::string name

struct IOWriter

Subclassed by PyCallbackIOWriter, faiss::BufferedIOWriter, faiss::FileIOWriter, faiss::VectorIOWriter

Public Functions

virtual size_t operator()(const void *ptr, size_t size, size_t nitems) = 0

virtual int fileno()

inline virtual ~IOWriter() noexcept(false)

Public Members

std::string name

struct VectorIOReader : public faiss::IOReader

Public Functions

virtual size_t operator()(void *ptr, size_t size, size_t nitems) override

virtual int fileno()

Public Members

std::vector<uint8_t> data

size_t rp = 0

std::string name

struct VectorIOWriter : public faiss::IOWriter

Public Functions

virtual size_t operator()(const void *ptr, size_t size, size_t nitems) override

virtual int fileno()

Public Members

std::vector<uint8_t> data

std::string name

struct FileIOReader : public faiss::IOReader

Public Functions

FileIOReader(FILE *rf)

FileIOReader(const char *fname)

~FileIOReader() override

virtual size_t operator()(void *ptr, size_t size, size_t nitems) override

virtual int fileno() override

Public Members

FILE *f = nullptr

bool need_close = false

std::string name

struct FileIOWriter : public faiss::IOWriter

Public Functions

FileIOWriter(FILE *wf)

FileIOWriter(const char *fname)

~FileIOWriter() override

virtual size_t operator()(const void *ptr, size_t size, size_t nitems) override

virtual int fileno() override

Public Members

FILE *f = nullptr

bool need_close = false

std::string name

struct BufferedIOReader : public faiss::IOReader

#include <io.h>

wraps an ioreader to make buffered reads to avoid too small reads

Public Functions

explicit BufferedIOReader(IOReader *reader, size_t bsz = 1024 * 1024)

Parameters:

bsz – buffer size (bytes). Reads will be done by batched of this size

virtual size_t operator()(void *ptr, size_t size, size_t nitems) override

virtual int fileno()

Public Members

IOReader *reader

size_t bsz

size_t ofs

offset in input stream

size_t ofs2

number of bytes returned to caller

size_t b0

size_t b1

range of available bytes in the buffer

std::vector<char> buffer

std::string name

struct BufferedIOWriter : public faiss::IOWriter

Public Functions

explicit BufferedIOWriter(IOWriter *writer, size_t bsz = 1024 * 1024)

virtual size_t operator()(const void *ptr, size_t size, size_t nitems) override

~BufferedIOWriter() override

virtual int fileno()

Public Members

IOWriter *writer

size_t bsz

size_t ofs

size_t ofs2

number of bytes received from caller

size_t b0

amount of data in buffer

std::vector<char> buffer