文件 IndexIVFAdditiveQuantizerFastScan.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 IndexIVFAdditiveQuantizerFastScan : public faiss::IndexIVFFastScan 

#include <IndexIVFAdditiveQuantizerFastScan.h>

IVFAQ 的快速扫描版本。目前适用于 4 位 AQ。

倒排列表中的代码不是按顺序存储的，而是按大小为 bbs 的块分组的。这使得可以使用 SIMD 指令非常快速地计算距离。

实现 (implem): 0: 自动选择实现 (默认) 1: orig 的搜索，重新实现 2: orig 的搜索，按 invlist 重新排序 10: 优化器 int16 搜索，在堆中收集结果，无 qbs 11: idem，在保留器中收集结果 12: 优化器 int16 搜索，在堆中收集结果，使用 qbs 13: idem，在保留器中收集结果

被 faiss::IndexIVFLocalSearchQuantizerFastScan, faiss::IndexIVFProductLocalSearchQuantizerFastScan, faiss::IndexIVFProductResidualQuantizerFastScan, faiss::IndexIVFResidualQuantizerFastScan 继承

公共类型

typedef Search_type_t = AdditiveQuantizer::Search_type_t

公共函数

IndexIVFAdditiveQuantizerFastScan(Index * quantizer, AdditiveQuantizer * aq, size_t d, size_t nlist, MetricType metric = METRIC_L2, int bbs = 32)

void init(AdditiveQuantizer * aq, size_t nlist, MetricType metric, int bbs)

IndexIVFAdditiveQuantizerFastScan()

~IndexIVFAdditiveQuantizerFastScan() override

explicit IndexIVFAdditiveQuantizerFastScan(const IndexIVFAdditiveQuantizer & orig, int bbs = 32)

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

训练向量的编码器。

如果 by_residual 为真，则使用残差和相应的 assign 数组调用它，否则 x 是原始训练向量，assign=nullptr

virtual idx_t train_encoder_num_vectors() const override: 可以被子类重新定义以指示它们需要多少个训练向量

void estimate_norm_scale(idx_t n, const float * x)

virtual void encode_vectors(idx_t n, const float * x, const idx_t * list_nos, uint8_t * codes, bool include_listno = false) const override: 与常规 IVFAQ 编码器相同。代码此时不会按块重组

virtual void search(idx_t n, const float * x, idx_t k, float * distances, idx_t * labels, const SearchParameters * params = nullptr) const override: 分配向量，然后调用 search_preassign

virtual bool lookup_table_is_3d() const override

virtual void compute_LUT(size_t n, const float *x, const CoarseQuantized &cq, AlignedTable<float> &dis_tables, AlignedTable<float> &biases) const override

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

解码一组向量

参数:

n – 向量的数量
bytes – 输入编码向量，大小为 n * sa_code_size()
x – 输出向量，大小为 n * d

公共成员

AdditiveQuantizer *aq

bool rescale_norm = false

int norm_scale = 1

size_t max_train_points

struct IndexIVFLocalSearchQuantizerFastScan : public faiss::IndexIVFAdditiveQuantizerFastScan 

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t 

公共函数

IndexIVFLocalSearchQuantizerFastScan(Index *quantizer, size_t d, size_t nlist, size_t M, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_norm_lsq2x4, int bbs = 32)

IndexIVFLocalSearchQuantizerFastScan()

void init(AdditiveQuantizer *aq, size_t nlist, MetricType metric, int bbs)

训练编码器

训练向量的编码器。

如果 by_residual 为真，则使用残差和相应的 assign 数组调用它，否则 x 是原始训练向量，assign=nullptr

训练编码器的向量数量: 可以被子类重新定义以指示它们需要多少个训练向量

void estimate_norm_scale(idx_t n, const float *x)

virtual void encode_vectors(idx_t n, const float *x, const idx_t *list_nos, uint8_t *codes, bool include_listno = false) const override: 与常规 IVFAQ 编码器相同。代码此时不会按块重组

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override: 分配向量，然后调用 search_preassign

virtual bool lookup_table_is_3d() const override

virtual void compute_LUT(size_t n, const float *x, const CoarseQuantized &cq, AlignedTable<float> &dis_tables, AlignedTable<float> &biases) const override

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

解码一组向量

参数:

n – 向量的数量
bytes – 输入编码向量，大小为 n * sa_code_size()
x – 输出向量，大小为 n * d

公共成员

LocalSearchQuantizer lsq

AdditiveQuantizer *aq

bool rescale_norm = false

int norm_scale = 1

size_t max_train_points

struct IndexIVFResidualQuantizerFastScan : public faiss::IndexIVFAdditiveQuantizerFastScan 

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t 

公共函数

IndexIVFResidualQuantizerFastScan(Index *quantizer, size_t d, size_t nlist, size_t M, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_norm_lsq2x4, int bbs = 32)

IndexIVFResidualQuantizerFastScan()

void init(AdditiveQuantizer *aq, size_t nlist, MetricType metric, int bbs)

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

训练向量的编码器。

如果 by_residual 为真，则使用残差和相应的 assign 数组调用它，否则 x 是原始训练向量，assign=nullptr

virtual idx_t train_encoder_num_vectors() const override: 可以被子类重新定义以指示它们需要多少个训练向量

void estimate_norm_scale(idx_t n, const float *x)

virtual void encode_vectors(idx_t n, const float *x, const idx_t *list_nos, uint8_t *codes, bool include_listno = false) const override: 与常规 IVFAQ 编码器相同。代码此时不会按块重组

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override: 分配向量，然后调用 search_preassign

virtual bool lookup_table_is_3d() const override

virtual void compute_LUT(size_t n, const float *x, const CoarseQuantized &cq, AlignedTable<float> &dis_tables, AlignedTable<float> &biases) const override

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

解码一组向量

参数:

n – 向量的数量
bytes – 输入编码向量，大小为 n * sa_code_size()
x – 输出向量，大小为 n * d

公共成员

ResidualQuantizer rq

AdditiveQuantizer *aq

bool rescale_norm = false

int norm_scale = 1

size_t max_train_points

struct IndexIVFProductLocalSearchQuantizerFastScan : public faiss::IndexIVFAdditiveQuantizerFastScan 

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t 

公共函数

IndexIVFProductLocalSearchQuantizerFastScan(Index *quantizer, size_t d, size_t nlist, size_t nsplits, size_t Msub, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_norm_lsq2x4, int bbs = 32)

IndexIVFProductLocalSearchQuantizerFastScan()

void init(AdditiveQuantizer *aq, size_t nlist, MetricType metric, int bbs)

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

训练向量的编码器。

如果 by_residual 为真，则使用残差和相应的 assign 数组调用它，否则 x 是原始训练向量，assign=nullptr

virtual idx_t train_encoder_num_vectors() const override: 可以被子类重新定义以指示它们需要多少个训练向量

void estimate_norm_scale(idx_t n, const float *x)

virtual void encode_vectors(idx_t n, const float *x, const idx_t *list_nos, uint8_t *codes, bool include_listno = false) const override: 与常规 IVFAQ 编码器相同。代码此时不会按块重组

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override: 分配向量，然后调用 search_preassign

virtual bool lookup_table_is_3d() const override

virtual void compute_LUT(size_t n, const float *x, const CoarseQuantized &cq, AlignedTable<float> &dis_tables, AlignedTable<float> &biases) const override

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

解码一组向量

参数:

n – 向量的数量
bytes – 输入编码向量，大小为 n * sa_code_size()
x – 输出向量，大小为 n * d

公共成员

ProductLocalSearchQuantizer plsq

AdditiveQuantizer *aq

bool rescale_norm = false

int norm_scale = 1

size_t max_train_points

struct IndexIVFProductResidualQuantizerFastScan : public faiss::IndexIVFAdditiveQuantizerFastScan 

公共类型

using Search_type_t = AdditiveQuantizer::Search_type_t 

公共函数

IndexIVFProductResidualQuantizerFastScan(Index *quantizer, size_t d, size_t nlist, size_t nsplits, size_t Msub, size_t nbits, MetricType metric = METRIC_L2, Search_type_t search_type = AdditiveQuantizer::ST_norm_lsq2x4, int bbs = 32)

IndexIVFProductResidualQuantizerFastScan()

void init(AdditiveQuantizer *aq, size_t nlist, MetricType metric, int bbs)

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

训练向量的编码器。

如果 by_residual 为真，则使用残差和相应的 assign 数组调用它，否则 x 是原始训练向量，assign=nullptr

virtual idx_t train_encoder_num_vectors() const override: 可以被子类重新定义以指示它们需要多少个训练向量

void estimate_norm_scale(idx_t n, const float *x)

virtual void encode_vectors(idx_t n, const float *x, const idx_t *list_nos, uint8_t *codes, bool include_listno = false) const override: 与常规 IVFAQ 编码器相同。代码此时不会按块重组

virtual void search(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const SearchParameters *params = nullptr) const override: 分配向量，然后调用 search_preassign

virtual bool lookup_table_is_3d() const override

virtual void compute_LUT(size_t n, const float *x, const CoarseQuantized &cq, AlignedTable<float> &dis_tables, AlignedTable<float> &biases) const override

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

解码一组向量

参数:

n – 向量的数量
bytes – 输入编码向量，大小为 n * sa_code_size()
x – 输出向量，大小为 n * d

公共成员

ProductResidualQuantizer prq

AdditiveQuantizer *aq

bool rescale_norm = false

int norm_scale = 1

size_t max_train_points