文件 HNSW.h

namespace faiss

使用多种变体实现的 k-means 聚类。

此源代码根据 MIT 许可证获得许可，该许可证位于此源代码树的根目录中的 LICENSE 文件中。

IDSelector 旨在定义要处理的向量子集（用于删除或作为搜索子集）

PQ4 SIMD 打包和累加函数

基本内核使用 bbs = nb * 2 * 16 向量累加 nq 查询向量，并生成该输出矩阵。这对于 nq * nb <= 4 很有用，否则寄存器溢出变得太大。

这些函数的实现分布在 3 个 cpp 文件中，以减少并行编译时间。模板是显式实例化的。

此文件包含用于计算距离的内核的回调。

在整个库中，向量以 float * 指针的形式提供。当批量处理（添加/搜索）多个向量时，大多数算法可以得到优化。在这种情况下，它们以矩阵的形式传递。当大小为 d 的 n 个向量以 float * x 的形式提供时，向量 i 的分量 j 是

x[ i * d + j ]

其中 0 <= i < n 并且 0 <= j < d。换句话说，矩阵始终是紧凑的。当指定矩阵的大小时，我们称之为 n*d 矩阵，这意味着行优先存储。

I/O 函数可以读取/写入到文件名、文件句柄或抽象介质的对象。

读取函数返回应该使用 delete 释放的对象。这些对象中的所有引用都归该对象所有。

反向列表的定义 + 一些实现该接口的常见类。

由于 IVF（反向文件）索引对于大规模用例非常有用，因此我们将与它们相关的一些函数分组到这个小库中。大多数函数都可以在 IndexIVF 和嵌入在 IndexPreTransform 中的 IndexIVF 上工作。

此文件中实现了 L2 和内积之外的额外度量标准

实现了一些神经网络层，主要用于支持 QINCo

定义一些对一组向量应用转换的对象。通常这些是预处理步骤。

函数

int search_from_candidates(const HNSW &hnsw, DistanceComputer &qdis, ResultHandler<HNSW::C> &res, HNSW::MinimaxHeap &candidates, VisitedTable &vt, HNSWStats &stats, int level, int nres_in = 0, const SearchParametersHNSW *params = nullptr)

HNSWStats greedy_update_nearest(const HNSW &hnsw, DistanceComputer &qdis, int level, HNSW::storage_idx_t &nearest, float &d_nearest)

std::priority_queue<HNSW::Node> search_from_candidate_unbounded(const HNSW &hnsw, const HNSW::Node &node, DistanceComputer &qdis, int ef, VisitedTable *vt, HNSWStats &stats)

void search_neighbors_to_add(HNSW &hnsw, DistanceComputer &qdis, std::priority_queue<HNSW::NodeDistCloser> &results, int entry_point, float d_entry_point, int level, VisitedTable &vt, bool reference_version = false)

变量

FAISS_API HNSWStats hnsw_stats

struct SearchParametersHNSW : public faiss::SearchParameters 

公共函数

inline ~SearchParametersHNSW()

公共成员

int efSearch = 16

bool check_relative_distance = true

bool bounded_queue = true

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: 仅从给定的顶点在第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

#include <HNSW.h>

堆结构，允许快速

公共类型

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

公共成员

int n

int k

int nvalid

std::vector<storage_idx_t> ids

std::vector<float> dis

struct NodeDistCloser

#include <HNSW.h>

用于将 (id, 距离) 对从最近到最远或反向排序

公共函数

inline NodeDistCloser(float d, int id)

inline bool operator<(const NodeDistCloser &obj1) const

公共成员

float d

int id

struct NodeDistFarther

公共函数

inline NodeDistFarther(float d, int id)

inline bool operator<(const NodeDistFarther &obj1) const

公共成员

float d

int id

struct HNSWStats

公共函数

inline void reset(): 跳数，即遍历的边数

inline void combine(const HNSWStats &other)

公共成员

size_t n1 = 0

size_t n2 = 0: 搜索的向量数

size_t ndis = 0: 候选列表耗尽的查询数

size_t nhops = 0: 计算的距离数