Struct faiss::HNSW

struct HNSW

Public Types

using storage_idx_t = int32_t

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

using C = CMax<float, int64_t>

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, ResultHandler<C> &res, VisitedTable &vt, const SearchParametersHNSW *params = nullptr) const

search interface for 1 point, single thread

void search_level_0(DistanceComputer &qdis, ResultHandler<C> &res, 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

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

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