结构体 faiss::HNSW
-
struct HNSW
公共类型
-
using storage_idx_t = int32_t
向量的内部存储（32 位：这很昂贵）
-
using C = CMax<float, int64_t>
-
typedef std::pair<float, storage_idx_t> Node
公共函数
-
void set_default_probas(int M, float levelMult)
初始化 assign_probas 和 cum_nneighbor_per_level，使其在第 0 层具有 2*M 个链接，在 > 0 层具有 M 个链接
-
void set_nb_neighbors(int level_no, int n)
设置此级别的邻居数（在添加任何内容之前）
-
int nb_neighbors(int layer_no) const
此级别的邻居数
-
int cum_nb_neighbors(int layer_no) const
直到（但不包括）此级别的累积数量
-
void neighbor_range(idx_t no, int layer_no, size_t *begin, size_t *end) const
顶点 no 在 layer_no 层的邻居表中的条目范围
-
explicit HNSW(int M = 32)
唯一强制性参数：邻居数
-
int random_level()
为新点选择一个随机级别
-
void fill_with_random_links(size_t n)
向表中添加 n 个随机级别（用于调试...）
-
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, bool keep_max_size_level0 = false)
-
void add_with_locks(DistanceComputer &ptdis, int pt_level, int pt_id, std::vector<omp_lock_t> &locks, VisitedTable &vt, bool keep_max_size_level0 = false)
在所有 <= pt_level 的级别上添加点 pt_id，并为它们构建链接结构。
-
HNSWStats search(DistanceComputer &qdis, ResultHandler<C> &res, VisitedTable &vt, const SearchParametersHNSW *params = nullptr) const
单点单线程搜索接口
-
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 SearchParametersHNSW *params = nullptr) const
仅在给定顶点从level 0搜索
-
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)
公共成员
-
std::vector<double> assign_probas
每层的分配概率 (总和=1)
-
std::vector<int> cum_nneighbor_per_level
每层存储的邻居数量（累积），首次添加后不应更改
-
std::vector<int> levels
每个向量的层级 (基础层级 = 1), 大小 = ntotal
-
std::vector<size_t> offsets
offsets[i] 是存储向量 i 的邻居数组中的偏移量，大小为 ntotal + 1
-
std::vector<storage_idx_t> neighbors
neighbors[offsets[i]:offsets[i+1]] 是向量 i 在所有层级的邻居列表。 这是所有存储的地方。
-
storage_idx_t entry_point = -1
搜索结构中的入口点（具有最大层级的点之一）
-
faiss::RandomGenerator rng
-
int max_level = -1
最大层级
-
int efConstruction = 40
构建时的扩展因子
-
int efSearch = 16
搜索时的扩展因子
-
bool check_relative_distance = true
在搜索期间：我们是否检查下一个最佳距离是否足够好？
-
bool search_bounded_queue = true
在探索期间使用有界队列
公共静态函数
-
static void shrink_neighbor_list(DistanceComputer &qdis, std::priority_queue<NodeDistFarther> &input, std::vector<NodeDistFarther> &output, int max_size, bool keep_max_size_level0 = false)
-
struct MinimaxHeap
允许快速操作的堆结构
公共类型
-
typedef faiss::CMax<float, storage_idx_t> HC
公共函数
-
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)
-
typedef faiss::CMax<float, storage_idx_t> HC
-
struct NodeDistCloser
用于按从最近到最远的顺序（或相反顺序）对 (id, 距离) 对进行排序
公共成员
-
float d
-
int id
-
float d
-
struct NodeDistFarther
公共函数
-
inline NodeDistFarther(float d, int id)
-
inline bool operator<(const NodeDistFarther &obj1) const
公共成员
-
float d
-
int id
-
inline NodeDistFarther(float d, int id)
-
using storage_idx_t = int32_t