File AuxIndexStructures.h

namespace faiss

Implementation of k-means clustering with many variants.

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)

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.

This file contains callbacks for kernels that compute distances.

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.

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.

Definition of inverted lists + a few common classes that implement the interface.

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.

In this file are the implementations of extra metrics beyond L2 and inner product

Implements a few neural net layers, mainly to support QINCo

Defines a few objects that apply transformations to a set of vectors Often these are pre-processing steps.

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 output the partialresults are empty!

struct InterruptCallback

Subclassed by faiss::TimeoutCallback

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 TimeoutCallback : public faiss::InterruptCallback

Public Functions

virtual bool want_interrupt() override
void set_timeout(double timeout_in_seconds)

Public Members

std::chrono::time_point<std::chrono::steady_clock> start
double timeout

Public Static Functions

static void reset(double timeout_in_seconds)
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