File InvertedLists.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.

Typedefs

using ConcatenatedInvertedLists = HStackInvertedLists

struct InvertedListsIterator

Public Functions

virtual ~InvertedListsIterator()

virtual bool is_available() const = 0

virtual void next() = 0

virtual std::pair<idx_t, const uint8_t*> get_id_and_codes() = 0

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

enum subset_type_t

Values:

enumerator SUBSET_TYPE_ID_RANGE

enumerator SUBSET_TYPE_ID_MOD

enumerator SUBSET_TYPE_ELEMENT_RANGE

enumerator SUBSET_TYPE_INVLIST_FRACTION

enumerator SUBSET_TYPE_INVLIST

Public Functions

InvertedLists(size_t nlist, size_t code_size)

virtual ~InvertedLists()

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 bool is_empty(size_t list_no, void *inverted_list_context = nullptr) const

check if the list is empty

virtual InvertedListsIterator *get_iterator(size_t list_no, void *inverted_list_context = nullptr) const

get iterable for lists that use_iterator

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code, void *inverted_list_context = nullptr)

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)

size_t copy_subset_to(InvertedLists &other, subset_type_t subset_type, idx_t a1, idx_t a2) const

copy a subset of the entries index to the other index

Returns:

number of entries copied

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

bool use_iterator = false

request to use iterator rather than get_codes / get_ids

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 ArrayInvertedLists : public faiss::InvertedLists

#include <InvertedLists.h>

simple (default) implementation as an array of inverted lists

Public Types

enum subset_type_t

Values:

enumerator SUBSET_TYPE_ID_RANGE

enumerator SUBSET_TYPE_ID_MOD

enumerator SUBSET_TYPE_ELEMENT_RANGE

enumerator SUBSET_TYPE_INVLIST_FRACTION

enumerator SUBSET_TYPE_INVLIST

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

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

void permute_invlists(const idx_t *map)

permute the inverted lists, map maps new_id to old_id

virtual bool is_empty(size_t list_no, void *inverted_list_context = nullptr) const override

check if the list is empty

~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 InvertedListsIterator *get_iterator(size_t list_no, void *inverted_list_context = nullptr) const

get iterable for lists that use_iterator

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code, void *inverted_list_context = nullptr)

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)

size_t copy_subset_to(InvertedLists &other, subset_type_t subset_type, idx_t a1, idx_t a2) const

copy a subset of the entries index to the other index

Returns:

number of entries copied

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

bool use_iterator = false

request to use iterator rather than get_codes / get_ids

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

enum subset_type_t

Values:

enumerator SUBSET_TYPE_ID_RANGE

enumerator SUBSET_TYPE_ID_MOD

enumerator SUBSET_TYPE_ELEMENT_RANGE

enumerator SUBSET_TYPE_INVLIST_FRACTION

enumerator SUBSET_TYPE_INVLIST

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 bool is_empty(size_t list_no, void *inverted_list_context = nullptr) const

check if the list is empty

virtual InvertedListsIterator *get_iterator(size_t list_no, void *inverted_list_context = nullptr) const

get iterable for lists that use_iterator

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code, void *inverted_list_context = nullptr)

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)

size_t copy_subset_to(InvertedLists &other, subset_type_t subset_type, idx_t a1, idx_t a2) const

copy a subset of the entries index to the other index

Returns:

number of entries copied

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

bool use_iterator = false

request to use iterator rather than get_codes / get_ids

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

enum subset_type_t

Values:

enumerator SUBSET_TYPE_ID_RANGE

enumerator SUBSET_TYPE_ID_MOD

enumerator SUBSET_TYPE_ELEMENT_RANGE

enumerator SUBSET_TYPE_INVLIST_FRACTION

enumerator SUBSET_TYPE_INVLIST

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 bool is_empty(size_t list_no, void *inverted_list_context = nullptr) const

check if the list is empty

virtual InvertedListsIterator *get_iterator(size_t list_no, void *inverted_list_context = nullptr) const

get iterable for lists that use_iterator

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code, void *inverted_list_context = nullptr)

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)

size_t copy_subset_to(InvertedLists &other, subset_type_t subset_type, idx_t a1, idx_t a2) const

copy a subset of the entries index to the other index

Returns:

number of entries copied

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

bool use_iterator = false

request to use iterator rather than get_codes / get_ids

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

enum subset_type_t

Values:

enumerator SUBSET_TYPE_ID_RANGE

enumerator SUBSET_TYPE_ID_MOD

enumerator SUBSET_TYPE_ELEMENT_RANGE

enumerator SUBSET_TYPE_INVLIST_FRACTION

enumerator SUBSET_TYPE_INVLIST

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

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 bool is_empty(size_t list_no, void *inverted_list_context = nullptr) const

check if the list is empty

virtual InvertedListsIterator *get_iterator(size_t list_no, void *inverted_list_context = nullptr) const

get iterable for lists that use_iterator

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code, void *inverted_list_context = nullptr)

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)

size_t copy_subset_to(InvertedLists &other, subset_type_t subset_type, idx_t a1, idx_t a2) const

copy a subset of the entries index to the other index

Returns:

number of entries copied

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

bool use_iterator = false

request to use iterator rather than get_codes / get_ids

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

enum subset_type_t

Values:

enumerator SUBSET_TYPE_ID_RANGE

enumerator SUBSET_TYPE_ID_MOD

enumerator SUBSET_TYPE_ELEMENT_RANGE

enumerator SUBSET_TYPE_INVLIST_FRACTION

enumerator SUBSET_TYPE_INVLIST

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 bool is_empty(size_t list_no, void *inverted_list_context = nullptr) const

check if the list is empty

virtual InvertedListsIterator *get_iterator(size_t list_no, void *inverted_list_context = nullptr) const

get iterable for lists that use_iterator

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code, void *inverted_list_context = nullptr)

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)

size_t copy_subset_to(InvertedLists &other, subset_type_t subset_type, idx_t a1, idx_t a2) const

copy a subset of the entries index to the other index

Returns:

number of entries copied

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

bool use_iterator = false

request to use iterator rather than get_codes / get_ids

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

enum subset_type_t

Values:

enumerator SUBSET_TYPE_ID_RANGE

enumerator SUBSET_TYPE_ID_MOD

enumerator SUBSET_TYPE_ELEMENT_RANGE

enumerator SUBSET_TYPE_INVLIST_FRACTION

enumerator SUBSET_TYPE_INVLIST

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 bool is_empty(size_t list_no, void *inverted_list_context = nullptr) const

check if the list is empty

virtual InvertedListsIterator *get_iterator(size_t list_no, void *inverted_list_context = nullptr) const

get iterable for lists that use_iterator

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code, void *inverted_list_context = nullptr)

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)

size_t copy_subset_to(InvertedLists &other, subset_type_t subset_type, idx_t a1, idx_t a2) const

copy a subset of the entries index to the other index

Returns:

number of entries copied

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

bool use_iterator = false

request to use iterator rather than get_codes / get_ids

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

enum subset_type_t

Values:

enumerator SUBSET_TYPE_ID_RANGE

enumerator SUBSET_TYPE_ID_MOD

enumerator SUBSET_TYPE_ELEMENT_RANGE

enumerator SUBSET_TYPE_INVLIST_FRACTION

enumerator SUBSET_TYPE_INVLIST

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 bool is_empty(size_t list_no, void *inverted_list_context = nullptr) const

check if the list is empty

virtual InvertedListsIterator *get_iterator(size_t list_no, void *inverted_list_context = nullptr) const

get iterable for lists that use_iterator

virtual size_t add_entry(size_t list_no, idx_t theid, const uint8_t *code, void *inverted_list_context = nullptr)

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)

size_t copy_subset_to(InvertedLists &other, subset_type_t subset_type, idx_t a1, idx_t a2) const

copy a subset of the entries index to the other index

Returns:

number of entries copied

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

bool use_iterator = false

request to use iterator rather than get_codes / get_ids

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