File IndexIVFFastScan.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
定义了一些将转换应用于一组向量的对象。 通常这些是预处理步骤。
变量
- FAISS_API IVFFastScanStats IVFFastScan_stats
-
struct IndexIVFFastScan : public faiss::IndexIVF
- #include <IndexIVFFastScan.h>
IVFPQ 和 IVFAQ 的快速扫描版本。 目前适用于 4 位 PQ/AQ。
倒排列表中的代码不按顺序存储，而是分组为大小为 bbs 的块。 这使得可以使用 SIMD 指令非常快速地计算距离。
实现方式 (implem): 0: 自动选择实现方式 (默认) 1: orig 的搜索，重新实现 2: orig 的搜索，按 invlist 重新排序 10: 优化器 int16 搜索，在堆中收集结果，无 qbs 11: 同上，在水库中收集结果 12: 优化器 int16 搜索，在堆中收集结果，使用 qbs 13: 同上，在水库中收集结果 14: 内部多线程 implem，基于 nq * nprobe 15: 同上，使用水库
对于范围搜索，仅支持 10 和 12。将 100 添加到 implem 以强制单线程扫描（粗量化器可能仍使用多线程）。
被 faiss::IndexIVFAdditiveQuantizerFastScan, faiss::IndexIVFPQFastScan 继承
公共函数
-
IndexIVFFastScan(Index *quantizer, size_t d, size_t nlist, size_t code_size, MetricType metric = METRIC_L2)
-
IndexIVFFastScan()
-
void init_fastscan(size_t M, size_t nbits, size_t nlist, MetricType metric, int bbs)
-
void init_code_packer()
-
~IndexIVFFastScan() override
-
virtual void add_with_ids(idx_t n, const float *x, const idx_t *xids) override
调用 encode_vectors 的默认实现
-
virtual bool lookup_table_is_3d() const = 0
-
virtual void compute_LUT(size_t n, const float *x, const CoarseQuantized &cq, AlignedTable<float> &dis_tables, AlignedTable<float> &biases) const = 0
-
void compute_LUT_uint8(size_t n, const float *x, const CoarseQuantized &cq, AlignedTable<uint8_t> &dis_tables, AlignedTable<uint16_t> &biases, float *normalizers) const
-
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 void search_preassigned(idx_t n, const float *x, idx_t k, const idx_t *assign, const float *centroid_dis, float *distances, idx_t *labels, bool store_pairs, const IVFSearchParameters *params = nullptr, IndexIVFStats *stats = nullptr) const override
搜索一组向量，这些向量已通过 IVF 量化器进行了预量化。 用查询结果填充相应的堆。 默认实现使用 InvertedListScanners 来进行搜索。
- 参数:
n – 要查询的向量数
x – 查询向量，大小为 nx * d
assign – 粗量化索引，大小为 nx * nprobe
centroid_dis – 到粗糙质心的距离，大小为 nx * nprobe
distance – 输出距离，大小为 n * k
labels – 输出标签，大小为 n * k
store_pairs – 将 inv 列表索引 + inv 列表偏移量存储在结果的 upper/lower 32 位中，而不是 IDs (用于重新排序)。
params – 用于覆盖对象的搜索参数
stats – 要更新的搜索统计信息（可以为空）
-
virtual void range_search(idx_t n, const float *x, float radius, RangeSearchResult *result, const SearchParameters *params = nullptr) const override
查询维度为 d 的 n 个向量到索引。
返回所有距离 < 半径的向量。 请注意，许多索引不实现 range_search（只有 k-NN 搜索是强制性的）。
- 参数:
n – 向量数
x – 要搜索的输入向量，大小为 n * d
radius – 搜索半径
result – 结果表
-
void search_dispatch_implem(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const CoarseQuantized &cq, const NormTableScaler *scaler, const IVFSearchParameters *params = nullptr) const
-
范围搜索分发实现
-
模板类
void search_implem_1(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const CoarseQuantized &cq, const NormTableScaler *scaler, const IVFSearchParameters *params = nullptr) const
-
template<class C>
void search_implem_2(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const CoarseQuantized &cq, const NormTableScaler *scaler, const IVFSearchParameters *params = nullptr) const
-
void search_implem_10(idx_t n, const float *x, SIMDResultHandlerToFloat &handler, const CoarseQuantized &cq, size_t *ndis_out, size_t *nlist_out, const NormTableScaler *scaler, const IVFSearchParameters *params = nullptr) const
-
void search_implem_12(idx_t n, const float *x, SIMDResultHandlerToFloat &handler, const CoarseQuantized &cq, size_t *ndis_out, size_t *nlist_out, const NormTableScaler *scaler, const IVFSearchParameters *params = nullptr) const
-
void search_implem_14(idx_t n, const float *x, idx_t k, float *distances, idx_t *labels, const CoarseQuantized &cq, int impl, const NormTableScaler *scaler, const IVFSearchParameters *params = nullptr) const
-
virtual void reconstruct_from_offset(int64_t list_no, int64_t offset, float *recons) const override
根据 (倒排列表索引 + 倒排列表偏移) 而非 ID 重建向量。
当不维护 direct_map 并且通过 search_preassigned() 且设置了
store_pairs来计算倒排列表偏移时，此方法很有用。
-
virtual CodePacker *get_CodePacker() const override
-
void reconstruct_orig_invlists()
公共成员
-
int bbs
-
size_t M
-
size_t nbits
-
size_t ksub
-
size_t M2
-
int implem = 0
-
int skip = 0
-
int qbs = 0
-
size_t qbs2 = 0
-
InvertedLists *orig_invlists = nullptr
原始的倒排列表（用于调试）
-
struct CoarseQuantized
-
IndexIVFFastScan(Index *quantizer, size_t d, size_t nlist, size_t code_size, MetricType metric = METRIC_L2)