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

带有存储向量的反向文件。 在这里，反向文件预先选择要搜索的向量，但它们没有以其他方式编码，代码数组只包含原始浮点条目。

由 faiss::IndexIVFFlatDedup 继承

公共函数

IndexIVFFlat(Index *quantizer, size_t d, size_t nlist_, MetricType = METRIC_L2)
virtual void add_core(idx_t n, const float *x, const idx_t *xids, const idx_t *precomputed_idx, void *inverted_list_context = nullptr) override

向量加法的实现，其中向量分配是预先定义的。 默认实现将代码提取传递给 encode_vectors。

参数:

precomputed_idx – 输入向量的量化索引（大小为 n）

virtual void encode_vectors(idx_t n, const float *x, const idx_t *list_nos, uint8_t *codes, bool include_listnos = false) const override

对一组向量进行编码，就像它们出现在倒排列表中一样

参数:

  • list_nos – 量化器返回的倒排列表 ID（大小为 n）。-1s 将被忽略。

  • codes – 输出代码，大小为 n * code_size

  • include_listno – 将列表 ID 包含在代码中（在这种情况下，将 ceil(log8(nlist)) 添加到代码大小）

virtual InvertedListScanner *get_InvertedListScanner(bool store_pairs, const IDSelector *sel) const override

获取此索引的扫描器（store_pairs 表示忽略标签）

默认搜索实现使用它来计算距离

virtual void reconstruct_from_offset(int64_t list_no, int64_t offset, float *recons) const override

给定 (inv list index + inv list offset) 而不是 id 的位置，重建向量。

当不维护 direct_map 并且 inv list offset 由 search_preassigned() 计算且 store_pairs 设置时，可用于重建。

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

解码一组向量

参数:

  • n – 向量的数量

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

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

IndexIVFFlat()
struct IndexIVFFlatDedup : public faiss::IndexIVFFlat

公共函数

IndexIVFFlatDedup(Index *quantizer, size_t d, size_t nlist_, MetricType = METRIC_L2)
virtual void train(idx_t n, const float *x) override

也会对训练集进行去重

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

为所有 IndexIVF* 类实现

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 list 索引 + inv list 偏移量存储在结果的上/下 32 位中，而不是 id（用于重新排序）。

  • params – 用于覆盖对象的搜索参数

  • stats – 要更新的搜索统计信息（可以为 null）

virtual size_t remove_ids(const IDSelector &sel) override

数据集操作函数。

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

未实现

virtual void update_vectors(int nv, const idx_t *idx, const float *v) override

未实现

virtual void reconstruct_from_offset(int64_t list_no, int64_t offset, float *recons) const override

未实现

inline IndexIVFFlatDedup()
virtual void add_core(idx_t n, const float *x, const idx_t *xids, const idx_t *precomputed_idx, void *inverted_list_context = nullptr) override

向量加法的实现，其中向量分配是预先定义的。 默认实现将代码提取传递给 encode_vectors。

参数:

precomputed_idx – 输入向量的量化索引（大小为 n）

virtual void encode_vectors(idx_t n, const float *x, const idx_t *list_nos, uint8_t *codes, bool include_listnos = false) const override

对一组向量进行编码，就像它们出现在倒排列表中一样

参数:

  • list_nos – 量化器返回的倒排列表 ID（大小为 n）。-1s 将被忽略。

  • codes – 输出代码，大小为 n * code_size

  • include_listno – 将列表 ID 包含在代码中（在这种情况下，将 ceil(log8(nlist)) 添加到代码大小）

virtual InvertedListScanner *get_InvertedListScanner(bool store_pairs, const IDSelector *sel) const override

获取此索引的扫描器（store_pairs 表示忽略标签）

默认搜索实现使用它来计算距离

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

解码一组向量

参数:

  • n – 向量的数量

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

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

Public Members

std::unordered_multimap<idx_t, idx_t> instances

将索引中存储的 ID 映射到相同向量的 ID。当一个向量是唯一的时候，它不会出现在 instances 映射中。