File IndexNSG.h

namespace faiss

实现了具有多种变体的 k-means 聚类。

版权所有 (c) Facebook, Inc. 及其附属公司。

此源代码已获得 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 IndexNSG : public faiss::Index
#include <IndexNSG.h>

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

由 faiss::IndexNSGFlat、faiss::IndexNSGPQ、faiss::IndexNSGSQ 子类化

公共函数

explicit IndexNSG(int d = 0, int R = 32, MetricType metric = METRIC_L2)
explicit IndexNSG(Index *storage, int R = 32)
~IndexNSG() override
void build(idx_t n, const float *x, idx_t *knn_graph, int GK)
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 reconstruct(idx_t key, float *recons) const override

重构存储的向量 (如果是有损编码，则是近似值)

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

参数:

  • key – 要重构的向量的 ID

  • recons – 重构的向量 (大小为 d)

virtual void reset() override

从数据库中删除所有元素。

void check_knn_graph(const idx_t *knn_graph, idx_t n, int K) const

公共成员

NSG nsg

链接结构

bool own_fields = false

顺序存储

Index *storage = nullptr
bool is_built = false

索引是否已构建。

int GK = 64

用于构建的KNN图的K值。

char build_type = 0

指示如何构建knn图

int nndescent_S = 10

nndescent的参数

int nndescent_R = 100
int nndescent_L
int nndescent_iter = 10
struct IndexNSGFlat : public faiss::IndexNSG
#include <IndexNSG.h>

Flat 索引，顶部带有 NSG 结构，以便更有效地访问元素。

公共函数

IndexNSGFlat()
IndexNSGFlat(int d, int R, MetricType metric = METRIC_L2)
void build(idx_t n, const float *x, idx_t *knn_graph, int GK)
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 reconstruct(idx_t key, float *recons) const override

重构存储的向量 (如果是有损编码，则是近似值)

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

参数:

  • key – 要重构的向量的 ID

  • recons – 重构的向量 (大小为 d)

virtual void reset() override

从数据库中删除所有元素。

void check_knn_graph(const idx_t *knn_graph, idx_t n, int K) const

公共成员

NSG nsg

链接结构

bool own_fields = false

顺序存储

Index *storage = nullptr
bool is_built = false

索引是否已构建。

int GK = 64

用于构建的KNN图的K值。

char build_type = 0

指示如何构建knn图

int nndescent_S = 10

nndescent的参数

int nndescent_R = 100
int nndescent_L
int nndescent_iter = 10
struct IndexNSGPQ : public faiss::IndexNSG
#include <IndexNSG.h>

PQ 索引，顶部带有 NSG 结构，以更高效地访问元素。

公共函数

IndexNSGPQ()
IndexNSGPQ(int d, int pq_m, int M, int pq_nbits = 8)
virtual void train(idx_t n, const float *x) override

如果需要，训练存储。

void build(idx_t n, const float *x, idx_t *knn_graph, int GK)
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 reconstruct(idx_t key, float *recons) const override

重构存储的向量 (如果是有损编码，则是近似值)

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

参数:

  • key – 要重构的向量的 ID

  • recons – 重构的向量 (大小为 d)

virtual void reset() override

从数据库中删除所有元素。

void check_knn_graph(const idx_t *knn_graph, idx_t n, int K) const

公共成员

NSG nsg

链接结构

bool own_fields = false

顺序存储

Index *storage = nullptr
bool is_built = false

索引是否已构建。

int GK = 64

用于构建的KNN图的K值。

char build_type = 0

指示如何构建knn图

int nndescent_S = 10

nndescent的参数

nndescent_R: 默认值为 100。
nndescent_L: 用于 nndescent 的 L 参数。
nndescent_iter: nndescent 的迭代次数，默认值为 10。
IndexNSGSQ: 结构体，继承自 faiss::IndexNSG。
#include <IndexNSG.h>

SQ 索引建立在 NSG 结构之上，以提高元素访问效率。

公共函数

IndexNSGSQ(): 默认构造函数。
IndexNSGSQ(int d, ScalarQuantizer::QuantizerType qtype, int M, MetricType metric = METRIC_L2): 构造函数，指定维度 d，量化类型 qtype，子向量数量 M 和距离计算方式 metric (默认为 L2 距离)。
build(idx_t n, const float *x, idx_t *knn_graph, int GK): 从预先计算的 KNN 图构建索引。 n 是向量的数量，x 是向量数据，knn_graph 是 KNN 图，GK 是每个节点的邻居数。
add(idx_t n, const float *x): 将 n 个向量 x 添加到索引中。

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

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

参数:

  • n – 向量的数量

  • x – 输入矩阵，大小为 n * d

train(idx_t n, const float *x): 使用 n 个向量 x 训练索引。

如果需要，训练存储。

search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const: 搜索 n 个查询向量 x 的最近邻。返回 k 个最近邻的距离 distances 和标签 labels。 可以选择性地传递搜索参数 params。

搜索入口点

reconstruct(idx_t key, float *recons) const: 重建索引中具有给定 key 的向量，并将结果存储在 recons 中。

重构存储的向量 (如果是有损编码，则是近似值)

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

参数:

  • key – 要重构的向量的 ID

  • recons – 重构的向量 (大小为 d)

reset(): 重置索引，删除所有向量。

从数据库中删除所有元素。

void check_knn_graph(const idx_t *knn_graph, idx_t n, int K) const

公共成员

NSG nsg

链接结构

bool own_fields = false

顺序存储

Index *storage = nullptr
bool is_built = false

索引是否已构建。

int GK = 64

用于构建的KNN图的K值。

char build_type = 0

指示如何构建knn图

int nndescent_S = 10

nndescent的参数

int nndescent_R = 100
int nndescent_L
int nndescent_iter = 10