文件 IDSelector.h

namespace faiss

实现 k-means 聚类，具有许多变体。

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

此源代码根据 LICENSE 文件中的 MIT 许可证获得许可，该文件位于此源树的根目录中。

IDSelector 旨在定义要处理的向量子集（用于删除或作为搜索的子集）

PQ4 SIMD 打包和累积函数

基本内核将 nq 查询向量与 bbs = nb * 2 * 16 向量累积，并生成该向量的输出矩阵。 对于 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 IDSelector

#include <IDSelector.h>

封装一组要处理的 id。

由 PyCallbackIDSelector, faiss::IDSelectorAll, faiss::IDSelectorAnd, faiss::IDSelectorArray, faiss::IDSelectorBatch, faiss::IDSelectorBitmap, faiss::IDSelectorNot, faiss::IDSelectorOr, faiss::IDSelectorRange, faiss::IDSelectorTranslated, faiss::IDSelectorXOr 继承

公共函数

virtual bool is_member(idx_t id) const = 0

inline virtual ~IDSelector()

struct IDSelectorRange : public faiss::IDSelector

#include <IDSelector.h>

位于 [imin, imax) 之间的 ID

公共函数

IDSelectorRange(idx_t imin, idx_t imax, bool assume_sorted = false)

virtual bool is_member(idx_t id) const final

void find_sorted_ids_bounds(size_t list_size, const idx_t *ids, size_t *jmin, size_t *jmax) const

对于已排序的 ID，找到存储有效 ID 的列表索引范围

inline ~IDSelectorRange() override

公共成员

idx_t imin

idx_t imax

bool assume_sorted

假设要处理的 ID 已排序。在某些情况下，这可以加快处理速度

struct IDSelectorArray : public faiss::IDSelector

#include <IDSelector.h>

简单的元素数组

is_member 调用效率非常低，但某些操作可以直接使用 ID。

公共函数

IDSelectorArray(size_t n, const idx_t *ids)

使用要处理的 ID 数组构造

参数:

• n – 要存储的 ID 数量

• ids – 要存储的元素。在 IDSelectorArray 的生命周期内，指针应保持有效

virtual bool is_member(idx_t id) const final

inline ~IDSelectorArray() override

公共成员

size_t n

const idx_t *ids

struct IDSelectorBatch : public faiss::IDSelector

#include <IDSelector.h>

来自集合的 ID。

在传递给构造函数的索引集中重复 ID 不会损害性能。

用于布隆过滤器和 GCC 实现的 unordered_set 的哈希函数只是 ID 的最低有效位。 这对于随机 ID 或序列中的 ID 效果很好，但如果 lsb 始终相同，则会产生许多哈希冲突

公共函数

IDSelectorBatch(size_t n, const idx_t *indices)

使用要处理的 ID 数组构造

参数:

• n – 要存储的 ID 数量

• ids – 要存储的元素。构造后可以释放指针

virtual bool is_member(idx_t id) const final

inline ~IDSelectorBatch() override

公共成员

std::unordered_set<idx_t> set

std::vector<uint8_t> bloom

int nbits

idx_t mask

struct IDSelectorBitmap : public faiss::IDSelector

#include <IDSelector.h>

每个元素一位。 使用位图构造，大小为 ceil(n / 8)。

公共函数

IDSelectorBitmap(size_t n, const uint8_t *bitmap)

使用二进制掩码构造

参数:

• n – 位图数组的大小

• bitmap – 当且仅当 id / 8 < n 并且 bitmap[floor(i / 8)] 的位编号 (i%8) 为 1 时，才会选择 id。

virtual bool is_member(idx_t id) const final

inline ~IDSelectorBitmap() override

公共成员

size_t n

const uint8_t *bitmap

struct IDSelectorNot : public faiss::IDSelector

#include <IDSelector.h>

反转另一个选择器的成员资格测试

公共函数

inline IDSelectorNot(const IDSelector *sel)

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorNot()

公共成员

const IDSelector *sel

struct IDSelectorAll : public faiss::IDSelector

#include <IDSelector.h>

选择所有条目（对基准测试有用）

公共函数

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorAll()

struct IDSelectorAnd : public faiss::IDSelector

#include <IDSelector.h>

对两个给定的IDSelector的 is_membership 结果执行 AND 操作。

公共函数

inline IDSelectorAnd(const IDSelector *lhs, const IDSelector *rhs)

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorAnd()

公共成员

const IDSelector *lhs

const IDSelector *rhs

struct IDSelectorOr : public faiss::IDSelector

#include <IDSelector.h>

对两个给定的IDSelector的 is_membership 结果执行 OR 操作。

公共函数

inline IDSelectorOr(const IDSelector *lhs, const IDSelector *rhs)

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorOr()

公共成员

const IDSelector *lhs

const IDSelector *rhs

struct IDSelectorXOr : public faiss::IDSelector

#include <IDSelector.h>

对给定的两个 IDSelector 的 is_membership 结果执行 XOR 操作。

公共函数

inline IDSelectorXOr(const IDSelector *lhs, const IDSelector *rhs)

inline virtual bool is_member(idx_t id) const final

inline virtual ~IDSelectorXOr()

公共成员

const IDSelector *lhs

const IDSelector *rhs