文件 IndexHNSW.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

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

struct IndexHNSW : public faiss::Index 

#include <IndexHNSW.h>

HNSW 索引是一个普通的随机访问索引，顶部构建了一个 HNSW 链接结构

由 faiss::IndexHNSW2Level、faiss::IndexHNSWCagra、faiss::IndexHNSWFlat、faiss::IndexHNSWPQ、faiss::IndexHNSWSQ 继承

公共类型

typedef HNSW::storage_idx_t storage_idx_t

公共函数

explicit IndexHNSW ( int d = 0, int M = 32, MetricType metric = METRIC_L2 ) 

explicit IndexHNSW ( Index * storage, int M = 32 ) 

~IndexHNSW ( ) override 

virtual void add ( idx_t n, const float * x ) override 

将维度为 d 的 n 个向量添加到索引中。

向量被隐式分配标签 ntotal .. ntotal + n - 1。此函数将输入向量切片成小于 blocksize_add 的块，并调用 add_core。

参数：

n – 向量的数量
x – 输入矩阵，大小为 n * d

virtual void train ( idx_t n, const float * x ) override : 如果需要，训练存储。

virtual void search ( idx_t n, const float * x, idx_t k, float * distances, idx_t * labels, const SearchParameters * params = nullptr ) const override : 搜索的入口点

virtual void range_search ( idx_t n, const float * x, float radius, RangeSearchResult * result, const SearchParameters * params = nullptr ) const override 

查询维度为 d 的 n 个向量到索引。

返回所有距离 < radius 的向量。请注意，许多索引不实现 range_search（只有 k-NN 搜索是强制性的）。

参数：

n – 向量的数量
x – 搜索的输入向量，大小为 n * d
radius – 搜索半径
result – 结果表

virtual void reconstruct(idx_t key, float *recons) const override

重建一个存储的向量（如果是有损编码，则为近似值）

此函数可能未针对某些索引定义

参数：

key – 要重建的向量的id
recons – 重建后的向量（大小为 d）

virtual void reset() override: 从数据库中移除所有元素。

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1, const SearchParameters *params = nullptr) const

仅在第0层执行搜索，给定每个顶点的起始点。

参数：: search_type – 1: 对每个nprobe执行一次搜索, 2: 将所有入口点排队

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I): 替代图构建

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests): 替代图构建

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

virtual DistanceComputer *get_distance_computer() const override

获取一个 DistanceComputer (在 AuxIndexStructures 中定义) 对象，用于这种类型的索引。

DistanceComputer 针对支持随机访问其向量的索引实现。

公共成员

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

bool init_level0 = true

bool keep_max_size_level0 = false

struct IndexHNSWFlat : public faiss::IndexHNSW 

#include <IndexHNSW.h>

使用 HNSW 结构构建的 Flat 索引，可以更高效地访问元素。

公共类型

typedef HNSW::storage_idx_t storage_idx_t

公共函数

IndexHNSWFlat()

IndexHNSWFlat(int d, int M, MetricType metric = METRIC_L2)

virtual void add(idx_t n, const float *x) override

将维度为 d 的 n 个向量添加到索引中。

向量被隐式分配标签 ntotal .. ntotal + n - 1。此函数将输入向量切片成小于 blocksize_add 的块，并调用 add_core。

参数：

n – 向量的数量
x – 输入矩阵，大小为 n * d

virtual void train(idx_t n, const float *x) override: 如果需要，训练存储。

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override: 搜索的入口点

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const override

查询维度为 d 的 n 个向量到索引。

返回所有距离 < radius 的向量。请注意，许多索引不实现 range_search（只有 k-NN 搜索是强制性的）。

参数：

n – 向量的数量
x – 搜索的输入向量，大小为 n * d
radius – 搜索半径
result – 结果表

virtual void reconstruct(idx_t key, float *recons) const override

重建一个存储的向量（如果是有损编码，则为近似值）

此函数可能未针对某些索引定义

参数：

key – 要重建的向量的id
recons – 重建后的向量（大小为 d）

virtual void reset() override: 从数据库中移除所有元素。

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1, const SearchParameters *params = nullptr) const

仅在第0层执行搜索，给定每个顶点的起始点。

参数：: search_type – 1: 对每个nprobe执行一次搜索, 2: 将所有入口点排队

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I): 替代图构建

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests): 替代图构建

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

virtual DistanceComputer *get_distance_computer() const override

获取一个 DistanceComputer (在 AuxIndexStructures 中定义) 对象，用于这种类型的索引。

DistanceComputer 针对支持随机访问其向量的索引实现。

公共成员

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

bool init_level0 = true

bool keep_max_size_level0 = false

struct IndexHNSWPQ : public faiss::IndexHNSW 

#include <IndexHNSW.h>

PQ索引，顶部是 HNSW 结构，以便更高效地访问元素。

公共类型

typedef HNSW::storage_idx_t storage_idx_t

公共函数

IndexHNSWPQ()

IndexHNSWPQ(int d, int pq_m, int M, int pq_nbits = 8, MetricType metric = METRIC_L2)

virtual void train(idx_t n, const float *x) override: 如果需要，训练存储。

virtual void add(idx_t n, const float *x) override

将维度为 d 的 n 个向量添加到索引中。

向量被隐式分配标签 ntotal .. ntotal + n - 1。此函数将输入向量切片成小于 blocksize_add 的块，并调用 add_core。

参数：

n – 向量的数量
x – 输入矩阵，大小为 n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override: 搜索的入口点

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const override

查询维度为 d 的 n 个向量到索引。

返回所有距离 < radius 的向量。请注意，许多索引不实现 range_search（只有 k-NN 搜索是强制性的）。

参数：

n – 向量的数量
x – 搜索的输入向量，大小为 n * d
radius – 搜索半径
result – 结果表

virtual void reconstruct(idx_t key, float *recons) const override

重建一个存储的向量（如果是有损编码，则为近似值）

此函数可能未针对某些索引定义

参数：

key – 要重建的向量的id
recons – 重建后的向量（大小为 d）

virtual void reset() override: 从数据库中移除所有元素。

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1, const SearchParameters *params = nullptr) const

仅在第0层执行搜索，给定每个顶点的起始点。

参数：: search_type – 1: 对每个nprobe执行一次搜索, 2: 将所有入口点排队

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I): 替代图构建

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests): 替代图构建

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

virtual DistanceComputer *get_distance_computer() const override

获取一个 DistanceComputer (在 AuxIndexStructures 中定义) 对象，用于这种类型的索引。

DistanceComputer 针对支持随机访问其向量的索引实现。

公共成员

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

bool init_level0 = true

bool keep_max_size_level0 = false

struct IndexHNSWSQ : public faiss::IndexHNSW

#include <IndexHNSW.h>

带有SQ索引，顶部带有 HNSW 结构，以更有效地访问元素。

公共类型

storage_idx_t 类型定义。

公共函数

默认构造函数。

构造函数，使用指定的维度 d、量化类型 qtype、量化器大小 M 和距离度量 metric。

添加 n 个向量到索引中。x 是向量数据的指针。

将维度为 d 的 n 个向量添加到索引中。

向量被隐式分配标签 ntotal .. ntotal + n - 1。此函数将输入向量切片成小于 blocksize_add 的块，并调用 add_core。

参数：

n – 向量的数量
x – 输入矩阵，大小为 n * d

使用 n 个向量训练索引。x 是训练数据的指针。: 如果需要，训练存储。

搜索 n 个查询向量，找到每个查询向量的 k 个最近邻。x 是查询向量数据的指针，distances 是存储距离的指针，labels 是存储最近邻标签的指针，params 是可选的搜索参数。: 搜索的入口点

搜索 n 个查询向量，找到每个查询向量在指定半径 radius 内的近邻。x 是查询向量数据的指针，result 是存储搜索结果的 RangeSearchResult 对象，params 是可选的搜索参数。

查询维度为 d 的 n 个向量到索引。

返回所有距离 < radius 的向量。请注意，许多索引不实现 range_search（只有 k-NN 搜索是强制性的）。

参数：

n – 向量的数量
x – 搜索的输入向量，大小为 n * d
radius – 搜索半径
result – 结果表

根据给定的键 key 重构向量，并将结果存储在 recons 中。

重建一个存储的向量（如果是有损编码，则为近似值）

此函数可能未针对某些索引定义

参数：

key – 要重建的向量的id
recons – 重建后的向量（大小为 d）

重置索引，移除所有已添加的向量。: 从数据库中移除所有元素。

缩小第 0 层邻居的大小到 size。

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1, const SearchParameters *params = nullptr) const

仅在第0层执行搜索，给定每个顶点的起始点。

参数：: search_type – 1: 对每个nprobe执行一次搜索, 2: 将所有入口点排队

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I): 替代图构建

void init_level_0_from_entry_points(int npt, const storage_idx_t *points, const storage_idx_t *nearests): 替代图构建

void reorder_links()

void link_singletons()

void permute_entries(const idx_t *perm)

virtual DistanceComputer *get_distance_computer() const override

获取一个 DistanceComputer (在 AuxIndexStructures 中定义) 对象，用于这种类型的索引。

DistanceComputer 针对支持随机访问其向量的索引实现。

公共成员

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

bool init_level0 = true

bool keep_max_size_level0 = false

struct IndexHNSW2Level : public faiss::IndexHNSW

#include <IndexHNSW.h>

具有快速随机访问的2层代码结构

公共类型

typedef HNSW::storage_idx_t storage_idx_t

公共函数

IndexHNSW2Level()

IndexHNSW2Level(Index *quantizer, size_t nlist, int m_pq, int M)

void flip_to_ivf()

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override: 搜索的入口点

virtual void add(idx_t n, const float *x) override

将维度为 d 的 n 个向量添加到索引中。

向量被隐式分配标签 ntotal .. ntotal + n - 1。此函数将输入向量切片成小于 blocksize_add 的块，并调用 add_core。

参数：

n – 向量的数量
x – 输入矩阵，大小为 n * d

virtual void train(idx_t n, const float *x) override: 如果需要，训练存储。

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const override

查询维度为 d 的 n 个向量到索引。

返回所有距离 < radius 的向量。请注意，许多索引不实现 range_search（只有 k-NN 搜索是强制性的）。

参数：

n – 向量的数量
x – 搜索的输入向量，大小为 n * d
radius – 搜索半径
result – 结果表

virtual void reconstruct(idx_t key, float *recons) const override

重建一个存储的向量（如果是有损编码，则为近似值）

此函数可能未针对某些索引定义

参数：

key – 要重建的向量的id
recons – 重建后的向量（大小为 d）

virtual void reset() override: 从数据库中移除所有元素。

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1, const SearchParameters *params = nullptr) const

仅在第0层执行搜索，给定每个顶点的起始点。

参数：: search_type – 1: 对每个nprobe执行一次搜索, 2: 将所有入口点排队

初始化级别 0 来自 KNN 图: 替代图构建

从入口点初始化级别 0: 替代图构建

重新排序链接

链接单例

排列条目

virtual DistanceComputer *get_distance_computer() const override

获取一个 DistanceComputer (在 AuxIndexStructures 中定义) 对象，用于这种类型的索引。

DistanceComputer 针对支持随机访问其向量的索引实现。

公共成员

HNSW hnsw

bool own_fields = false

Index *storage = nullptr

bool init_level0 = true

bool keep_max_size_level0 = false

struct IndexHNSWCagra : public faiss::IndexHNSW 

公共类型

typedef HNSW::storage_idx_t storage_idx_t

公共函数

IndexHNSWCagra()

IndexHNSWCagra(int d, int M, MetricType metric = METRIC_L2)

virtual void add(idx_t n, const float *x) override

将维度为 d 的 n 个向量添加到索引中。

向量被隐式分配标签 ntotal .. ntotal + n - 1。此函数将输入向量切片成小于 blocksize_add 的块，并调用 add_core。

参数：

n – 向量的数量
x – 输入矩阵，大小为 n * d

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override: 搜索的入口点

virtual void train(idx_t n, const float *x) override: 如果需要，训练存储。

virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const override

查询维度为 d 的 n 个向量到索引。

返回所有距离 < radius 的向量。请注意，许多索引不实现 range_search（只有 k-NN 搜索是强制性的）。

参数：

n – 向量的数量
x – 搜索的输入向量，大小为 n * d
radius – 搜索半径
result – 结果表

virtual void reconstruct(idx_t key, float *recons) const override

重建一个存储的向量（如果是有损编码，则为近似值）

此函数可能未针对某些索引定义

参数：

key – 要重建的向量的id
recons – 重建后的向量（大小为 d）

virtual void reset() override: 从数据库中移除所有元素。

void shrink_level_0_neighbors(int size)

void search_level_0(idx_t n, const float *x, idx_t k, const storage_idx_t *nearest, const float *nearest_d, float *distances, idx_t *labels, int nprobe = 1, int search_type = 1, const SearchParameters *params = nullptr) const

仅在第0层执行搜索，给定每个顶点的起始点。

参数：: search_type – 1: 对每个nprobe执行一次搜索, 2: 将所有入口点排队

void init_level_0_from_knngraph(int k, const float *D, const idx_t *I): 替代图构建

从入口点初始化第0层。: 替代图构建

重新排序链接。

链接单例。

排列条目。

获取距离计算器。

获取一个 DistanceComputer (在 AuxIndexStructures 中定义) 对象，用于这种类型的索引。

DistanceComputer 针对支持随机访问其向量的索引实现。

公共成员

是否仅限基本级别。: 当设置为 true 时，索引是不可变的。此选项用于将 knn 图从 GpuIndexCagra 复制到 IndexHNSWCagra 的基本级别，而不添加上层级别。这样做可以搜索 HNSW 索引，但会删除添加向量的功能。

基本级别搜索入口点数量。: 当 base_level_only 设置为 True 时，搜索函数仅搜索 HNSW 索引的基本级别 knn 图。此参数通过随机选择一些点并使用最佳点来选择入口点。

HNSW。

是否拥有字段。

存储。

是否初始化第0层。

是否保持第0层的最大尺寸。