Faiss 搜索参数设置

Faiss 的索引对象（index）在搜索阶段（search-time）通常可以通过对象字段（如类属性）来设置参数。

不过，有时我们需要为每个查询分别设置不同的参数。例如，对于 IndexIVF 索引结构，一个查询可以设置 nprobe=10，另一个查询设置为 nprobe=20。如果搜索操作发生在不同线程之间，这种做法就会带来问题。

为了支持每次查询单独设置参数，Faiss 提供了 SearchParameter（搜索参数）对象，可以作为 search() 函数的最后一个参数传入。

SearchParameter 实例​

支持搜索参数的索引类型，通常会有对应的子类 SearchParameter 对象。例如，IndexIVFPQ 有一个对应的 SearchParameterIVFPQ 对象。

使用示例：

D, I = index.search(xq, 10, params=faiss.SearchParametersIVFPQ(nprobe=10))

对于 C++，类似如下：

idx_t *I = ...;
float *D = ...;
faiss::SearchParametersIVFPQ params;
params.nprobe = 10;
index.search(nq, xq, 10, D, I, &params);

SearchParameters 支持嵌套设置，例如：

params=faiss.SearchParametersIVFPQ(
    nprobe=10,
    quantizer_params=faiss.SearchParameterHNSW(efSearch=123)
)

这种写法适用于像 IVF1234_HNSW,... 等支持多级量化器索引结构。

更多示例代码可以参考 test_search_params.py。

只在元素子集上进行搜索​

有时我们只想在特定 id 的向量子集中进行搜索。这类似于 remove_ids 方法 的操作方式，子集由 IDSelector（ID选择器）对象定义。

IDSelector::is_member(i) 方法返回 true 时，id 为 i 的向量会被包含在搜索中。

IDSelector 实例可通过 SearchParameters 的 sel 字段传递（前提是该字段不为 null）。

默认情况下，向量的筛选是通过 is_member 方法完成的，不过某些索引类型和 id 选择器组合下，Faiss 做了更进一步的性能优化。下面会介绍内置的 IDSelector 类型。

IDSelectorRange（区间筛选）​

该选择器选定 id 在区间 [imin, imax) 内的项。

特定性能优化​

• 对于 IndexFlat，简单跳过不在 [imin, imax) 范围之外的数据。
• 对于已排序 id 的 IndexIVF，只处理倒排表（inverted lists）中包含所选区间的部分。id 的排序有两种方式：用 add 添加向量，或用 add_with_ids 且 id 按递增顺序添加（不需严格递增）。是否已排序可用 index_ivf.check_sorted_ids() 检查。
• 其它类型的 Flat 索引待支持（TODO）。

IDSelectorArray、IDSelectorBatch 和 IDSelectorBitmap​

三种 IDSelector 都用来封装需要处理的 id 集合，只是实现方式与效率不同。

• IDSelectorArray：直接存储一个 id 数组。简单遍历判断，查找效率一般。但在某些索引（如 IndexFlat）下可以直接挑选数据，速度快。
• IDSelectorBatch：结合哈希表（unordered_set）和 Bloom 过滤器，查找时间为常数级 O(1)，但内存略大。
• IDSelectorBitmap：每个向量 id 对应 1 位(bit)，适用于大规模、连续 id 的子集，比 Batch 更紧凑高效。

IDSelectorNot（取反选择器）​

该选择器会反选另一个 IDSelector，例如：

sel = faiss.IDSelectorNot(faiss.IDSelectorBatch(list_of_ids))

此例会忽略 list_of_ids 中所有 id。

PyCallbackIDSelector（Python函数回调）​

可以定义 Python 回调函数，实现自定义筛选逻辑。函数接收一个整数参数，返回布尔类型（True/False）。

value = 123

def my_condition(i):
    return i % value == 0

sel = faiss.PyCallbackIDSelector(my_condition)

时间复杂度分析​

向量 id 通常不是预先筛选的，而是在倒排表中遍历元素时实时判断。只有当 IDSelectorRange 遇到已排序的 id 时，可以一开始就缩小搜索范围。

• 在已排序 id 的 IndexIVF 上，IDSelectorRange 时间复杂度为 $O(k)$，否则为 $O(n)$；
• 其余类型如下表：

其中 $n$ 为索引总 id 数，$k$ 为筛选后的 id 数。