File InvertedLists.h

namespace faiss

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

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

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

x[ i * d + j ]

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

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

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

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

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

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

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

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

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

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

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

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

Typedefs

using ConcatenatedInvertedLists = HStackInvertedLists
struct ArrayInvertedLists : public faiss::InvertedLists
#include <InvertedLists.h>

simple (default) implementation as an array of inverted lists

Public Types

typedef Index::idx_t idx_t

Public Functions

ArrayInvertedLists(size_t nlist, size_t code_size)
virtual size_t list_size(size_t list_no) const override

get the size of a list

virtual const uint8_t *get_codes(size_t list_no) const override

get the codes for an inverted list must be released by release_codes

Returns

codes size list_size * code_size

virtual const idx_t *get_ids(size_t list_no) const override

get the ids for an inverted list must be released by release_ids

Returns

ids size list_size

size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) override
void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void resize(size_t list_no, size_t new_size) override
~ArrayInvertedLists() override
virtual void release_codes(size_t list_no, const uint8_t *codes) const

release codes returned by get_codes (default implementation is nop

virtual void release_ids(size_t list_no, const idx_t *ids) const

release ids returned by get_ids

virtual idx_t get_single_id(size_t list_no, size_t offset) const
Returns

a single id in an inverted list

virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const
Returns

a single code in an inverted list (should be deallocated with release_codes)

virtual void prefetch_lists(const idx_t *list_nos, int nlist) const

prepare the following lists (default does nothing) a list can be -1 hence the signed long

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)

add one entry to an inverted list

virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) = 0
virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) = 0
virtual void reset()
void merge_from(InvertedLists *oivf, size_t add_id)

move all entries from oivf (empty on output)

double imbalance_factor() const

1= perfectly balanced, >1: imbalanced

void print_stats() const

display some stats about the inverted lists

size_t compute_ntotal() const

sum up list sizes

Public Members

std::vector<std::vector<uint8_t>> codes
std::vector<std::vector<idx_t>> ids

Inverted lists for indexes.

size_t nlist

number of possible key values

size_t code_size

code size per vector in bytes

Public Static Attributes

static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)

used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless

struct HStackInvertedLists : public faiss::ReadOnlyInvertedLists
#include <InvertedLists.h>

Horizontal stack of inverted lists.

Public Types

typedef Index::idx_t idx_t

Public Functions

HStackInvertedLists(int nil, const InvertedLists **ils)

build InvertedLists by concatenating nil of them

virtual size_t list_size(size_t list_no) const override

get the size of a list

virtual const uint8_t *get_codes(size_t list_no) const override

get the codes for an inverted list must be released by release_codes

Returns

codes size list_size * code_size

virtual const idx_t *get_ids(size_t list_no) const override

get the ids for an inverted list must be released by release_ids

Returns

ids size list_size

virtual void prefetch_lists(const idx_t *list_nos, int nlist) const override

prepare the following lists (default does nothing) a list can be -1 hence the signed long

virtual void release_codes(size_t list_no, const uint8_t *codes) const override

release codes returned by get_codes (default implementation is nop

virtual void release_ids(size_t list_no, const idx_t *ids) const override

release ids returned by get_ids

virtual idx_t get_single_id(size_t list_no, size_t offset) const override
Returns

a single id in an inverted list

virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const override
Returns

a single code in an inverted list (should be deallocated with release_codes)

virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void resize(size_t list_no, size_t new_size) override
virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)

add one entry to an inverted list

virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
virtual void reset()
void merge_from(InvertedLists *oivf, size_t add_id)

move all entries from oivf (empty on output)

double imbalance_factor() const

1= perfectly balanced, >1: imbalanced

void print_stats() const

display some stats about the inverted lists

size_t compute_ntotal() const

sum up list sizes

Public Members

std::vector<const InvertedLists*> ils
size_t nlist

number of possible key values

size_t code_size

code size per vector in bytes

Public Static Attributes

static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)

used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless

struct InvertedLists
#include <InvertedLists.h>

Table of inverted lists multithreading rules:

  • concurrent read accesses are allowed

  • concurrent update accesses are allowed

  • for resize and add_entries, only concurrent access to different lists are allowed

Subclassed by faiss::ArrayInvertedLists, faiss::BlockInvertedLists, faiss::OnDiskInvertedLists, faiss::ReadOnlyInvertedLists

Public Types

typedef Index::idx_t idx_t

Public Functions

InvertedLists(size_t nlist, size_t code_size)
virtual size_t list_size(size_t list_no) const = 0

get the size of a list

virtual const uint8_t *get_codes(size_t list_no) const = 0

get the codes for an inverted list must be released by release_codes

Returns

codes size list_size * code_size

virtual const idx_t *get_ids(size_t list_no) const = 0

get the ids for an inverted list must be released by release_ids

Returns

ids size list_size

virtual void release_codes(size_t list_no, const uint8_t *codes) const

release codes returned by get_codes (default implementation is nop

virtual void release_ids(size_t list_no, const idx_t *ids) const

release ids returned by get_ids

virtual idx_t get_single_id(size_t list_no, size_t offset) const
Returns

a single id in an inverted list

virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const
Returns

a single code in an inverted list (should be deallocated with release_codes)

virtual void prefetch_lists(const idx_t *list_nos, int nlist) const

prepare the following lists (default does nothing) a list can be -1 hence the signed long

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)

add one entry to an inverted list

virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) = 0
virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) = 0
virtual void resize(size_t list_no, size_t new_size) = 0
virtual void reset()
void merge_from(InvertedLists *oivf, size_t add_id)

move all entries from oivf (empty on output)

virtual ~InvertedLists()
double imbalance_factor() const

1= perfectly balanced, >1: imbalanced

void print_stats() const

display some stats about the inverted lists

size_t compute_ntotal() const

sum up list sizes

Public Members

size_t nlist

number of possible key values

size_t code_size

code size per vector in bytes

Public Static Attributes

static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)

used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless

struct ScopedCodes

Public Functions

inline ScopedCodes(const InvertedLists *il, size_t list_no)
inline ScopedCodes(const InvertedLists *il, size_t list_no, size_t offset)
inline const uint8_t *get()
inline ~ScopedCodes()

Public Members

const InvertedLists *il
const uint8_t *codes
size_t list_no
struct ScopedIds

Public Functions

inline ScopedIds(const InvertedLists *il, size_t list_no)
inline const idx_t *get()
inline idx_t operator[](size_t i) const
inline ~ScopedIds()

Public Members

const InvertedLists *il
const idx_t *ids
size_t list_no
struct MaskedInvertedLists : public faiss::ReadOnlyInvertedLists
#include <InvertedLists.h>

use the first inverted lists if they are non-empty otherwise use the second

This is useful if il1 has a few inverted lists that are too long, and that il0 has replacement lists for those, with empty lists for the others.

Public Types

typedef Index::idx_t idx_t

Public Functions

MaskedInvertedLists(const InvertedLists *il0, const InvertedLists *il1)
virtual size_t list_size(size_t list_no) const override

get the size of a list

virtual const uint8_t *get_codes(size_t list_no) const override

get the codes for an inverted list must be released by release_codes

Returns

codes size list_size * code_size

virtual const idx_t *get_ids(size_t list_no) const override

get the ids for an inverted list must be released by release_ids

Returns

ids size list_size

virtual void release_codes(size_t list_no, const uint8_t *codes) const override

release codes returned by get_codes (default implementation is nop

virtual void release_ids(size_t list_no, const idx_t *ids) const override

release ids returned by get_ids

virtual idx_t get_single_id(size_t list_no, size_t offset) const override
Returns

a single id in an inverted list

virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const override
Returns

a single code in an inverted list (should be deallocated with release_codes)

virtual void prefetch_lists(const idx_t *list_nos, int nlist) const override

prepare the following lists (default does nothing) a list can be -1 hence the signed long

virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void resize(size_t list_no, size_t new_size) override
virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)

add one entry to an inverted list

virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
virtual void reset()
void merge_from(InvertedLists *oivf, size_t add_id)

move all entries from oivf (empty on output)

double imbalance_factor() const

1= perfectly balanced, >1: imbalanced

void print_stats() const

display some stats about the inverted lists

size_t compute_ntotal() const

sum up list sizes

Public Members

const InvertedLists *il0
const InvertedLists *il1
size_t nlist

number of possible key values

size_t code_size

code size per vector in bytes

Public Static Attributes

static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)

used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless

struct ReadOnlyInvertedLists : public faiss::InvertedLists
#include <InvertedLists.h>

invlists that fail for all write functions

Subclassed by faiss::HStackInvertedLists, faiss::MaskedInvertedLists, faiss::SliceInvertedLists, faiss::StopWordsInvertedLists, faiss::VStackInvertedLists

Public Types

typedef Index::idx_t idx_t

Public Functions

inline ReadOnlyInvertedLists(size_t nlist, size_t code_size)
virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void resize(size_t list_no, size_t new_size) override
virtual size_t list_size(size_t list_no) const = 0

get the size of a list

virtual const uint8_t *get_codes(size_t list_no) const = 0

get the codes for an inverted list must be released by release_codes

Returns

codes size list_size * code_size

virtual const idx_t *get_ids(size_t list_no) const = 0

get the ids for an inverted list must be released by release_ids

Returns

ids size list_size

virtual void release_codes(size_t list_no, const uint8_t *codes) const

release codes returned by get_codes (default implementation is nop

virtual void release_ids(size_t list_no, const idx_t *ids) const

release ids returned by get_ids

virtual idx_t get_single_id(size_t list_no, size_t offset) const
Returns

a single id in an inverted list

virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const
Returns

a single code in an inverted list (should be deallocated with release_codes)

virtual void prefetch_lists(const idx_t *list_nos, int nlist) const

prepare the following lists (default does nothing) a list can be -1 hence the signed long

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)

add one entry to an inverted list

virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
virtual void reset()
void merge_from(InvertedLists *oivf, size_t add_id)

move all entries from oivf (empty on output)

double imbalance_factor() const

1= perfectly balanced, >1: imbalanced

void print_stats() const

display some stats about the inverted lists

size_t compute_ntotal() const

sum up list sizes

Public Members

size_t nlist

number of possible key values

size_t code_size

code size per vector in bytes

Public Static Attributes

static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)

used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless

struct SliceInvertedLists : public faiss::ReadOnlyInvertedLists
#include <InvertedLists.h>

vertical slice of indexes in another InvertedLists

Public Types

typedef Index::idx_t idx_t

Public Functions

SliceInvertedLists(const InvertedLists *il, idx_t i0, idx_t i1)
virtual size_t list_size(size_t list_no) const override

get the size of a list

virtual const uint8_t *get_codes(size_t list_no) const override

get the codes for an inverted list must be released by release_codes

Returns

codes size list_size * code_size

virtual const idx_t *get_ids(size_t list_no) const override

get the ids for an inverted list must be released by release_ids

Returns

ids size list_size

virtual void release_codes(size_t list_no, const uint8_t *codes) const override

release codes returned by get_codes (default implementation is nop

void release_ids(size_t list_no, const idx_t *ids) const override
virtual idx_t get_single_id(size_t list_no, size_t offset) const override
Returns

a single id in an inverted list

virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const override
Returns

a single code in an inverted list (should be deallocated with release_codes)

void prefetch_lists(const idx_t *list_nos, int nlist) const override
virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void resize(size_t list_no, size_t new_size) override
virtual void release_ids(size_t list_no, const idx_t *ids) const

release ids returned by get_ids

virtual void prefetch_lists(const idx_t *list_nos, int nlist) const

prepare the following lists (default does nothing) a list can be -1 hence the signed long

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)

add one entry to an inverted list

virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
virtual void reset()
void merge_from(InvertedLists *oivf, size_t add_id)

move all entries from oivf (empty on output)

double imbalance_factor() const

1= perfectly balanced, >1: imbalanced

void print_stats() const

display some stats about the inverted lists

size_t compute_ntotal() const

sum up list sizes

Public Members

const InvertedLists *il
idx_t i0
idx_t i1
size_t nlist

number of possible key values

size_t code_size

code size per vector in bytes

Public Static Attributes

static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)

used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless

struct StopWordsInvertedLists : public faiss::ReadOnlyInvertedLists
#include <InvertedLists.h>

if the inverted list in il is smaller than maxsize then return it, otherwise return an empty invlist

Public Types

typedef Index::idx_t idx_t

Public Functions

StopWordsInvertedLists(const InvertedLists *il, size_t maxsize)
virtual size_t list_size(size_t list_no) const override

get the size of a list

virtual const uint8_t *get_codes(size_t list_no) const override

get the codes for an inverted list must be released by release_codes

Returns

codes size list_size * code_size

virtual const idx_t *get_ids(size_t list_no) const override

get the ids for an inverted list must be released by release_ids

Returns

ids size list_size

virtual void release_codes(size_t list_no, const uint8_t *codes) const override

release codes returned by get_codes (default implementation is nop

virtual void release_ids(size_t list_no, const idx_t *ids) const override

release ids returned by get_ids

virtual idx_t get_single_id(size_t list_no, size_t offset) const override
Returns

a single id in an inverted list

virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const override
Returns

a single code in an inverted list (should be deallocated with release_codes)

virtual void prefetch_lists(const idx_t *list_nos, int nlist) const override

prepare the following lists (default does nothing) a list can be -1 hence the signed long

virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void resize(size_t list_no, size_t new_size) override
virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)

add one entry to an inverted list

virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
virtual void reset()
void merge_from(InvertedLists *oivf, size_t add_id)

move all entries from oivf (empty on output)

double imbalance_factor() const

1= perfectly balanced, >1: imbalanced

void print_stats() const

display some stats about the inverted lists

size_t compute_ntotal() const

sum up list sizes

Public Members

const InvertedLists *il0
size_t maxsize
size_t nlist

number of possible key values

size_t code_size

code size per vector in bytes

Public Static Attributes

static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)

used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless

struct VStackInvertedLists : public faiss::ReadOnlyInvertedLists

Public Types

typedef Index::idx_t idx_t

Public Functions

VStackInvertedLists(int nil, const InvertedLists **ils)

build InvertedLists by concatenating nil of them

virtual size_t list_size(size_t list_no) const override

get the size of a list

virtual const uint8_t *get_codes(size_t list_no) const override

get the codes for an inverted list must be released by release_codes

Returns

codes size list_size * code_size

virtual const idx_t *get_ids(size_t list_no) const override

get the ids for an inverted list must be released by release_ids

Returns

ids size list_size

virtual void release_codes(size_t list_no, const uint8_t *codes) const override

release codes returned by get_codes (default implementation is nop

virtual void release_ids(size_t list_no, const idx_t *ids) const override

release ids returned by get_ids

virtual idx_t get_single_id(size_t list_no, size_t offset) const override
Returns

a single id in an inverted list

virtual const uint8_t *get_single_code(size_t list_no, size_t offset) const override
Returns

a single code in an inverted list (should be deallocated with release_codes)

virtual void prefetch_lists(const idx_t *list_nos, int nlist) const override

prepare the following lists (default does nothing) a list can be -1 hence the signed long

virtual size_t add_entries(size_t list_no, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void update_entries(size_t list_no, size_t offset, size_t n_entry, const idx_t *ids, const uint8_t *code) override
virtual void resize(size_t list_no, size_t new_size) override
virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code)

add one entry to an inverted list

virtual void update_entry(size_t list_no, size_t offset, idx_t id, const uint8_t *code)
virtual void reset()
void merge_from(InvertedLists *oivf, size_t add_id)

move all entries from oivf (empty on output)

double imbalance_factor() const

1= perfectly balanced, >1: imbalanced

void print_stats() const

display some stats about the inverted lists

size_t compute_ntotal() const

sum up list sizes

Public Members

std::vector<const InvertedLists*> ils
std::vector<idx_t> cumsz
size_t nlist

number of possible key values

size_t code_size

code size per vector in bytes

Public Static Attributes

static const size_t INVALID_CODE_SIZE = static_cast<size_t>(-1)

used for BlockInvertedLists, where the codes are packed into groups and the individual code size is meaningless