文件 IndexAdditiveQuantizer.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 IndexAdditiveQuantizer : public faiss::IndexFlatCodes
#include <IndexAdditiveQuantizer.h>

用于加性量化器的抽象类。 搜索函数是通用的。

由 faiss::IndexLocalSearchQuantizer, faiss::IndexProductLocalSearchQuantizer, faiss::IndexProductResidualQuantizer, faiss::IndexResidualQuantizer 子类化

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t

公共函数

explicit IndexAdditiveQuantizer(idx_t d, AdditiveQuantizer *aq, MetricType metric = METRIC_L2)
virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

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

最多返回 k 个向量。如果查询结果不足，结果数组将用 -1 填充。

参数：

  • n – 向量的数量

  • x – 要搜索的输入向量，大小为 n * d

  • k – 提取的向量数量

  • distances – 输出的成对距离，大小为 n*k

  • labels – 输出的 NN 的标签，大小为 n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

编码一组向量

参数：

  • n – 向量的数量

  • x – 输入向量，大小为 n * d

  • bytes – 输出编码向量，大小为 n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

解码一组向量

参数：

  • n – 向量的数量

  • bytes – 输入编码向量，大小为 n * sa_code_size()

  • x – 输出向量，大小为 n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

FlatCodesDistanceComputer 提供了一个 distance_to_code 方法

默认实现使用 sa_decode 显式解码向量。

公共成员

AdditiveQuantizer *aq
struct IndexResidualQuantizer : public faiss::IndexAdditiveQuantizer
#include <IndexAdditiveQuantizer.h>

基于残差量化器的 Index。存储的向量通过残差量化代码进行近似。也可以用作编解码器

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t

公共函数

IndexResidualQuantizer(int d, size_t M, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

构造函数。

参数：

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

IndexResidualQuantizer(int d, const std::vector<size_t> &nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)
IndexResidualQuantizer()
virtual void train(idx_t n, const float *x) override

对代表性向量集执行训练。

参数：

  • 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

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

最多返回 k 个向量。如果查询结果不足，结果数组将用 -1 填充。

参数：

  • n – 向量的数量

  • x – 要搜索的输入向量，大小为 n * d

  • k – 提取的向量数量

  • distances – 输出的成对距离，大小为 n*k

  • labels – 输出的 NN 的标签，大小为 n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

编码一组向量

参数：

  • n – 向量的数量

  • x – 输入向量，大小为 n * d

  • bytes – 输出编码向量，大小为 n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

解码一组向量

参数：

  • n – 向量的数量

  • bytes – 输入编码向量，大小为 n * sa_code_size()

  • x – 输出向量，大小为 n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

FlatCodesDistanceComputer 提供了一个 distance_to_code 方法

默认实现使用 sa_decode 显式解码向量。

公共成员

ResidualQuantizer rq

用于编码向量的残差量化器。

AdditiveQuantizer *aq
struct IndexLocalSearchQuantizer : public faiss::IndexAdditiveQuantizer

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t

公共函数

IndexLocalSearchQuantizer(int d, size_t M, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

构造函数。

参数：

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

IndexLocalSearchQuantizer()
virtual void train(idx_t n, const float *x) override

对代表性向量集执行训练。

参数：

  • 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

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

最多返回 k 个向量。如果查询结果不足，结果数组将用 -1 填充。

参数：

  • n – 向量的数量

  • x – 要搜索的输入向量，大小为 n * d

  • k – 提取的向量数量

  • distances – 输出的成对距离，大小为 n*k

  • labels – 输出的 NN 的标签，大小为 n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

编码一组向量

参数：

  • n – 向量的数量

  • x – 输入向量，大小为 n * d

  • bytes – 输出编码向量，大小为 n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

解码一组向量

参数：

  • n – 向量的数量

  • bytes – 输入编码向量，大小为 n * sa_code_size()

  • x – 输出向量，大小为 n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

FlatCodesDistanceComputer 提供了一个 distance_to_code 方法

默认实现使用 sa_decode 显式解码向量。

公共成员

LocalSearchQuantizer lsq
AdditiveQuantizer *aq
struct IndexProductResidualQuantizer : public faiss::IndexAdditiveQuantizer
#include <IndexAdditiveQuantizer.h>

基于乘积残差量化器的索引。

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t

公共函数

IndexProductResidualQuantizer(int d, size_t nsplits, size_t Msub, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

构造函数。

参数：

  • d – 输入向量的维度

  • nsplits – 残差量化器的数量

  • Msub – 每个RQ的子量化器的数量

  • nbits – 每个子向量索引的位数

  • d – 输入向量的维度

  • nsplits – 残差量化器的数量

  • Msub – 每个RQ的子量化器的数量

  • nbits – 每个子向量索引的位数

IndexProductResidualQuantizer()
virtual void train(idx_t n, const float *x) override

对代表性向量集执行训练。

参数：

  • 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

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

最多返回 k 个向量。如果查询结果不足，结果数组将用 -1 填充。

参数：

  • n – 向量的数量

  • x – 要搜索的输入向量，大小为 n * d

  • k – 提取的向量数量

  • distances – 输出的成对距离，大小为 n*k

  • labels – 输出的 NN 的标签，大小为 n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

编码一组向量

参数：

  • n – 向量的数量

  • x – 输入向量，大小为 n * d

  • bytes – 输出编码向量，大小为 n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

解码一组向量

参数：

  • n – 向量的数量

  • bytes – 输入编码向量，大小为 n * sa_code_size()

  • x – 输出向量，大小为 n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

FlatCodesDistanceComputer 提供了一个 distance_to_code 方法

默认实现使用 sa_decode 显式解码向量。

公共成员

ProductResidualQuantizer prq

用于编码向量的乘积残差量化器。

AdditiveQuantizer *aq
struct IndexProductLocalSearchQuantizer : public faiss::IndexAdditiveQuantizer
#include <IndexAdditiveQuantizer.h>

基于乘积局部搜索量化器的Index。

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t

公共函数

IndexProductLocalSearchQuantizer(int d, size_t nsplits, size_t Msub, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_decompress)

构造函数。

参数：

  • d – 输入向量的维度

  • nsplits – 局部搜索量化器的数量

  • Msub – 每个 LSQ 的子量化器的数量

  • nbits – 每个子向量索引的位数

  • d – 输入向量的维度

  • nsplits – 局部搜索量化器的数量

  • Msub – 每个 LSQ 的子量化器的数量

  • nbits – 每个子向量索引的位数

IndexProductLocalSearchQuantizer()
virtual void train(idx_t n, const float *x) override

对代表性向量集执行训练。

参数：

  • 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

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

最多返回 k 个向量。如果查询结果不足，结果数组将用 -1 填充。

参数：

  • n – 向量的数量

  • x – 要搜索的输入向量，大小为 n * d

  • k – 提取的向量数量

  • distances – 输出的成对距离，大小为 n*k

  • labels – 输出的 NN 的标签，大小为 n*k

virtual void sa_encode(idx_t n, const float *x, uint8_t *bytes) const override

编码一组向量

参数：

  • n – 向量的数量

  • x – 输入向量，大小为 n * d

  • bytes – 输出编码向量，大小为 n * sa_code_size()

virtual void sa_decode(idx_t n, const uint8_t *bytes, float *x) const override

解码一组向量

参数：

  • n – 向量的数量

  • bytes – 输入编码向量，大小为 n * sa_code_size()

  • x – 输出向量，大小为 n * d

virtual FlatCodesDistanceComputer *get_FlatCodesDistanceComputer() const override

FlatCodesDistanceComputer 提供了一个 distance_to_code 方法

默认实现使用 sa_decode 显式解码向量。

公共成员

ProductLocalSearchQuantizer plsq

用于编码向量的乘积局部搜索量化器。

AdditiveQuantizer *aq
struct AdditiveCoarseQuantizer : public faiss::Index
#include <IndexAdditiveQuantizer.h>

一个“虚拟”索引，其中的元素是残差量化器质心。

旨在用作 IndexIVF 中的粗量化器。

由 faiss::LocalSearchCoarseQuantizer, faiss::ResidualCoarseQuantizer 继承

公共函数

explicit AdditiveCoarseQuantizer(idx_t d = 0, AdditiveQuantizer *aq = nullptr, MetricType metric = METRIC_L2)
virtual void add(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

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

最多返回 k 个向量。如果查询结果不足，结果数组将用 -1 填充。

参数：

  • n – 向量的数量

  • x – 要搜索的输入向量，大小为 n * d

  • k – 提取的向量数量

  • distances – 输出的成对距离，大小为 n*k

  • labels – 输出的 NN 的标签，大小为 n*k

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

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

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

参数：

  • key – 要重建的向量的 ID

  • recons – 重建的向量（大小为 d）

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

对代表性向量集执行训练。

参数：

  • n – 训练向量的数量

  • x – 训练向量，大小为 n * d

virtual void reset() override

不适用。

公共成员

AdditiveQuantizer *aq
std::vector<float> centroid_norms

质心的范数，对于 knn 搜索很有用

struct SearchParametersResidualCoarseQuantizer : public faiss::SearchParameters

公共函数

inline ~SearchParametersResidualCoarseQuantizer()

公共成员

float beam_factor = 4.0f
struct ResidualCoarseQuantizer : public faiss::AdditiveCoarseQuantizer
#include <IndexAdditiveQuantizer.h>

与默认的 AdditiveCoarseQuantizer 相比，ResidualCoarseQuantizer 有点特殊，因为它可以在搜索时使用波束搜索（速度较慢，但对于非常大的词汇表可能很有用）

公共函数

void set_beam_factor(float new_beam_factor)

如果需要，计算质心范数

ResidualCoarseQuantizer(int d, size_t M, size_t nbits, MetricType metric = METRIC_L2)

构造函数。

参数：

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

ResidualCoarseQuantizer(int d, const std::vector<size_t> &nbits, MetricType metric = METRIC_L2)
virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override

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

最多返回 k 个向量。如果查询结果不足，结果数组将用 -1 填充。

参数：

  • n – 向量的数量

  • x – 要搜索的输入向量，大小为 n * d

  • k – 提取的向量数量

  • distances – 输出的成对距离，大小为 n*k

  • labels – 输出的 NN 的标签，大小为 n*k

void initialize_from(const ResidualCoarseQuantizer &other)

从另一个对象复制前 M 个码本级别。用于将 ResidualQuantizer 裁剪为其前 M 个量化器。

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

不适用。

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

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

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

参数：

  • key – 要重建的向量的 ID

  • recons – 重建的向量（大小为 d）

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

对代表性向量集执行训练。

参数：

  • n – 训练向量的数量

  • x – 训练向量，大小为 n * d

virtual void reset() override

不适用。

公共成员

ResidualQuantizer rq

用于编码向量的残差量化器。

float beam_factor = 4.0f

beam size和search k之间的因子。如果为负，则使用精确的搜索到质心。

AdditiveQuantizer *aq
std::vector<float> centroid_norms

质心的范数，对于 knn 搜索很有用

struct LocalSearchCoarseQuantizer : public faiss::AdditiveCoarseQuantizer

公共函数

LocalSearchCoarseQuantizer(int d, size_t M, size_t nbits, MetricType metric = METRIC_L2)

构造函数。

参数：

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

  • d – 输入向量的维度

  • M – 子量化器的数量

  • nbits – 每个子向量索引的位数

LocalSearchCoarseQuantizer()
virtual void add(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

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

最多返回 k 个向量。如果查询结果不足，结果数组将用 -1 填充。

参数：

  • n – 向量的数量

  • x – 要搜索的输入向量，大小为 n * d

  • k – 提取的向量数量

  • distances – 输出的成对距离，大小为 n*k

  • labels – 输出的 NN 的标签，大小为 n*k

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

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

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

参数：

  • key – 要重建的向量的 ID

  • recons – 重建的向量（大小为 d）

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

对代表性向量集执行训练。

参数：

  • n – 训练向量的数量

  • x – 训练向量，大小为 n * d

virtual void reset() override

不适用。

公共成员

LocalSearchQuantizer lsq

用于编码向量的残差量化器。

AdditiveQuantizer *aq
std::vector<float> centroid_norms

质心的范数，对于 knn 搜索很有用