更快的搜索

速度太慢了，如何让搜索更快？​

为了加快搜索速度，可以将数据集分成若干小块。通常我们会在 $d$ 维空间中定义 Voronoi（沃罗诺伊）单元格，每一个数据库向量（即要被搜索的数据点）都归属到其中某个单元格。在搜索时，我们只需将待查询向量 $x$ 分到对应的单元格，并只在这个单元格及附近的几个单元格中，与数据库向量 $y$ 进行比较。

这种方法可以通过使用 IndexIVFFlat（倒排文件-扁平索引）结构来实现。此类型索引需要一个训练步骤，你可以用任何和数据库向量分布相同的数据，通常直接用数据库向量自身就可以。

IndexIVFFlat 还依赖于另外一个索引器——量化器（quantizer），它的作用是负责将向量分配到不同的 Voronoi 单元格。每个单元格由一个中心点（centroid）定义，找到某个向量落在哪个单元格，其实就是找其最近的中心点。这个操作通常用一个 IndexFlatL2（L2 距离的扁平索引）来完成。

搜索时有两个关键参数：

• nlist：单元格（cell）数量
• nprobe：每次查询时实际访问的单元格数量（即在所有 nlist 单元格中，被访问参与搜索的单元格数）

搜索的耗时一般会随着 nprobe 增大而增加，但还取决于量化的速度。

Python 示例​

nlist = 100
k = 4
quantizer = faiss.IndexFlatL2(d)  # 这个是量化器（负责分配单元格）
index = faiss.IndexIVFFlat(quantizer, d, nlist)
assert not index.is_trained
index.train(xb)                   # 训练索引，通常用数据库向量
assert index.is_trained

index.add(xb)                     # 添加数据，速度可能略慢
D, I = index.search(xq, k)        # 实际搜索
print(I[-5:])                     # 打印最后5个查询的邻居
index.nprobe = 10                 # 默认 nprobe 是 1，可以试试更大的值
D, I = index.search(xq, k)
print(I[-5:])                     # 再次打印最后5个查询的邻居

C++ 示例​

int nlist = 100;
int k = 4;
faiss::IndexFlatL2 quantizer(d);       // 量化器
faiss::IndexIVFFlat index(&quantizer, d, nlist);
assert(!index.is_trained);
index.train(nb, xb);
assert(index.is_trained);
index.add(nb, xb);
{   // 查询向量 xq
    idx_t *I = new idx_t[k * nq];
    float *D = new float[k * nq];
    index.search(nq, xq, k, D, I);
    printf("I=\n");                    // 打印最后5个查询的邻居
    ...
    index.nprobe = 10;                 // 默认 nprobe 是 1，可以试试更大的值
    index.search(nq, xq, k, D, I);
    printf("I=\n");
    ...
}

运行结果示例​

当 nprobe=1 时，输出类似如下：

[[ 9900 10500 9831 10808] [11055 10812 11321 10260] [11353 10164 10719 11013] [10571 10203 10793 10952] [ 9582 10304 9622 9229]] 这些结果与暴力搜索（即对所有数据点暴力比较）的结果很相似，但不完全一致。这是因为部分正确结果可能没有落在同一个 Voronoi 单元格中，因此漏掉了。

例如，nprobe=10 时：

[[ 9900 10500 9309 9831] [11055 10895 10812 11321] [11353 11103 10164 9787] [10571 10664 10632 9638] [ 9628 9554 10036 9582]] 这时结果就更加正确。特别需要注意，这里之所以能取到完全正确的结果，是因为数据分布很特殊（主要分布在 x 轴），实际使用时不同数据集的表现会不同。

使用场景和注意事项

• 适用于数据量较大、希望加速向量最近邻搜索的场合；
• 需要提前训练，训练数据应具有与实际数据相似的分布；
• nprobe 值影响运行效率和准确性，根据实际应用场景灵活调整；
• 添加数据（add 操作）偶尔也会较慢，主要影响首次大批量添加时。