本页面为百万级（约100万）向量数据集的索引建议及实验结果。

指南（部分内容已过时）​

当数据集规模达到约100万时，使用穷举索引（exhaustive index）速度会变得非常慢，这时可以选择 IndexIVFFlat 作为替代。该索引类型依然可以返回准确的距离，但由于不是穷举搜索，偶尔可能会遗漏邻居。

2018年相关实验

以下是在1百万规模数据上，采用不同索引方法的实验。这里主要关注以下权衡：

• 速度：测试平台为 "Intel(R) Xeon(R) CPU E5-2680 v2 @ 2.80GHz"，启用20线程。耗时以批量模式测量（即所有查询向量一起处理），单位为毫秒（ms）。
• 准确率：采用 1-NN recall@R 指标（R取1、10或100），即实际最近邻在前R个结果中的查询比重。

注意

注意：本实验设置较为理想。若用单线程，速度大约会慢10倍；若逐条查询，则再慢2-3倍（参见下文 sift_1M 的计时结果）。

实验所用索引类型以 index_factory 创建时的索引 key 命名。

所有测试均返回每个查询的前100个结果。

CNN 激活图（Activation Maps）​

数据采用从1百万张图片中提取的4096维描述符（descriptor），查询向量也同理。之后用主成分分析（PCA）将4096维降为256维（PCA转换耗时未计入结果）。对此场景，推荐索引如下：

对于高准确率需求，IVF（倒排文件索引）更有优势，而IMI（乘积量化多索引）适合于较低准确率场景。

备注

IVF16384取得略优于IVF4096的效果，但后者在训练（train）和添加（add）数据时的成本显著更低（该成本未计入图中）。

若内存有限，可选择压缩向量（如 IndexIVFPQ，倒排文件乘积量化索引）。

图中 IVF4096,Flat 仅作参考。

举例：OPQ32_128,IVF4096,PQ32，每个向量的存储为编码32字节 + id 8字节 = 40字节，每百万数据仅需约40MB，但还会有查找表、内存分配等额外开销。

此外，还实验了用resnet-34（在Imagenet上预训练）计算的512维激活特征，来源为Flickr100M数据集的头100万张图片（去除了最高两层）。其表现与上面类似：

SIFT 1M​

这是研究中常用的标准数据集，由图片块提取的128维SIFT描述符组成。

整体结论类似于CNN数据。

本实验还评估了线程数与批处理方式的影响：

• nt1：批量，单线程处理
• nobatch / nobatch_nt1：逐条提交查询
• parallelqueries：批量并行，每条查询单独处理，循环不作批量

由此可见，单线程处理比多线程慢5~12倍；单条查询时线程利用率并不高。

备注

此图报告的是每秒查询数（QPS），横坐标是10-准确率@10（inter@10），方便与 nmslib 做比较。nmslib是此基准下表现最好的库（见参考资料）。

由于硬件平台不同，与上述基准对比并不完全公平。直接对比nmslib结果显示，nmslib速度更快，但内存消耗更多。Faiss的构建时间是次线性的，内存使用则与数据线性相关。

索引类型	搜索耗时	1-R@1	索引大小	构建索引时间
Flat-CPU	9.100 s	1.0000	512 MB	0 s
nmslib (hnsw)	0.081 s	0.8195	512 + 796 MB	173 s
IVF16384,Flat	0.538 s	0.8980	512 + 8 MB	240 s
IVF16384,Flat (Titan X)	0.059 s	0.8145	512 + 8 MB	5 s
Flat-GPU (Titan X)	0.753 s	0.9935	512 MB	0 s

• 第一行为Faiss的精确搜索结果。
• 后两行为GPU（Titan X）上的测试结果。
• Flat类型索引为暴力穷举，返回完全精确结果（除非出现分数相同或浮点误差）。

Twitter Glove​

该数据集常用于Annoy库的基准测试，其评估方式为找到的10个最近邻与真实10个最近邻的交集数量。

IVFPQ结合校验步骤可略提升准确率。

随机数据​

这里数据是均匀采样到128维单位球面上的向量。由于向量之间分布无规律，任何索引方法都难以提高性能。

以 recall@100 为评估指标。多数情况下，暴力穷举反而是最优选择。

HNSW 基准

在Faiss中，HNSW（分层小世界图索引，Hierarchical Navigable Small World）有多种应用场景：

• 标准HNSW索引用于原始向量
• 对量化后（SQ，标量量化）向量操作
• 作为IVF（倒排索引）的量化器
• 作为kmeans分配器

不同场景的评测可通过 benchs/bench_hnsw.py 脚本在SIFT1M数据集上完成，开启20线程。典型输出如下：

  testing HNSW Flat
  efSearch 16        0.011 ms per query, R@1 0.8740
  efSearch 32        0.020 ms per query, R@1 0.9492
  efSearch 64        0.033 ms per query, R@1 0.9779
  efSearch 128       0.059 ms per query, R@1 0.9887
  efSearch 256       0.104 ms per query, R@1 0.9920

  testing HNSW with a scalar quantizer
  efSearch 16        0.005 ms per query, R@1 0.7281
  efSearch 32        0.008 ms per query, R@1 0.8506
  efSearch 64        0.011 ms per query, R@1 0.9242
  efSearch 128       0.020 ms per query, R@1 0.9566
  efSearch 256       0.039 ms per query, R@1 0.9716

  testing IVF Flat (baseline)
  nprobe 1           0.076 ms per query, R@1 0.4085
  nprobe 4           0.067 ms per query, R@1 0.6331
  nprobe 16          0.078 ms per query, R@1 0.8263
  nprobe 64          0.141 ms per query, R@1 0.9470
  nprobe 256         0.344 ms per query, R@1 0.9861

  testing IVF Flat with HNSW quantizer
  nprobe 1           0.007 ms per query, R@1 0.4058
  nprobe 4           0.010 ms per query, R@1 0.6305
  nprobe 16          0.021 ms per query, R@1 0.8247
  nprobe 64          0.063 ms per query, R@1 0.9462
  nprobe 256         0.220 ms per query, R@1 0.9842

对比结果说明：

• HNSW 在速度/准确率取舍上优于IVFFlat（如：以 0.020 ms/查询达到 0.9 以上的 recall@1，明显快于IVF）。
• 带标量量化（Scalar Quantizer）的HNSW优于传统HNSW（注意SIFT1M本身就是字节编码格式）。
• 将HNSW作为IVF的量化器，既提高速度，又可保持平衡的簇分配（与IMI类似，但聚类更平衡）。
• kmeans聚类实验：

  performing kmeans on the sift1M vectors (baseline)
  Clustering 1000000 points in 128D to 16384 clusters, redo 1 times, 10 iterations
    Preprocessing in 0.17 s
    Iteration 9 (612.53 s, search 612.18 s): objective=3.85228e+10 imbalance=1.235 nsplit=0

  performing kmeans on the sift1M using HNSW assignment
  Clustering 1000000 points in 128D to 16384 clusters, redo 1 times, 10 iterations
    Preprocessing in 0.17 s
    Iteration 9 (74.63 s, search 73.46 s): objective=3.85232e+10 imbalance=1.234 nsplit=0

即采用HNSW分配可实现8.2倍加速，并不影响目标函数值、簇不均衡（imbalance）和空簇数（nsplit），聚类质量有保障。

4位乘积量化（PQ）: 与SCANN的对比

Faiss中有高效的4位PQ实现。下文对比Faiss快速扫描（fast-scan）实现与Google的 SCANN 1.1.1版本。

Faiss的4位PQ实现深受SCANN启发，数据结构优化以适配AVX指令，详见 simulate_kernels_PQ4.ipynb。

详细比较

测试时搜索线程数设置为1。图中x轴为准确率指标，y轴为每秒查询数（QPS），右上角越优。全部测试在2.2 GHz Xeon E5-2698（80核）标准化平台上执行。

四组1M大小的数据集：

• SIFT1M：128维经典SIFT描述符
• Deep1M：96维L2归一化深度特征
• glove-100：ANN-benchmarks中用于cosine距离（即 faiss.INNER_PRODUCT）的词向量数据集
• music-100：Morozov & Babenko, NIPS'18提出，用于最大内积搜索的数据

所有数据集均采用SCANN推荐设置，在Faiss中相当于 IVF2000,PQ{dim/2}x4fs,RFlat（测试时也有不带RFlat重排序的版本）。默认每个查询返回10个结果，若加入重排序则先查100条再用精确距离校验。

SIFT1M结果​

不加重排序时，Faiss在所有工作点均快且更准；加重排序后大部分情况下Faiss仍有优势。

Deep1M结果​

与SIFT1M实验结论一致。

glove-100结果​

此处采用ANN基准的准确率定义（inter@10），而非前述1-recall@10。

glove向量因训练方式有特殊分布，SCANN利用各向异性量化（参考论文）获得了额外准确率。不过加重排序后，二者差距缩小，Faiss部分场景更优。因此，目前并不急需在Faiss中实现各向异性量化。

music-100结果​

Faiss在Music-100上的提升更大，表明SCANN的各向异性量化并非所有最大内积应用都适用。

综上，Faiss的实现至少与SCANN持平，常常更好。

基准测试

所有基准图的x轴为准确率（accuracy），y轴为QPS（每秒查询数），右上角表现最佳。平台为2.2 GHz Xeon E5-2698（80核），推荐配置为32核。

检索参数（如nprobe，表示每个查询访问的量化器单元数）会显著影响性能。参数配置采用 Faiss自动调参功能，以选取Pareto最优的设定。

预备实验：IVF编码方案对比​

首先，在SIFT1M上，比较fast-scan版PQ、常用PQ8和标量量化（scalar quantizer）。先用IVF1024划分数据集。

IVF1024 -- 向量编码方案结果图

各曲线标签指明每个存储向量占用字节数。数据量不大时影响不大，在大规模下则尤为关键。

主要结论：

• 在低准确率场景， PQ4 fast-scan 性能最佳。
• 要高准确率时，HNSW最佳。
• PQ64x4fs方案准确率上限低于PQ64x4无fs，因为后者可用残差编码及float32查表（虽然速度远逊）。
• PQ64x4fsr速度略慢，但准确率顶点更高（因编码了残差向量，词汇量提升时效果更明显）。

预备实验：IVF重排序（Re-ranking）​

接下来，进一步研究对候选集用精确或近似距离重排序的性能影响：

（内容未完，详见下一部分……）

IVF1024 -- 重排序（reranking）

观察与说明​

• 使用重排序（reranking）方法，在性能方面比 HNSW（层次化小世界图，Hierarchical Navigable Small World）更优。
• 重排序增加了一个检索时的参数：k_factor_rf。因此，重排序方法的调优更难，且曲线表现更加不规则。
• 重排序阶段采用的编码方式对检索速度影响较小，对检索准确率有轻微影响。每个向量存储的编码长度可以明显减小，而召回率基本保持不变。

SIFT1M 与 Deep1M 实验结果​

我们在这两个公开数据集上做了大量实验。为了让结果更清晰，图表分为“小规模（每个向量编码<64字节）”和“大规模（每个向量编码较大）”两类。

小规模设置（每个向量小于64字节）​

SIFT1M（小规模）

Deep1M（小规模）

观察与说明​

• 最优的检索准确率依赖于编码长度（压缩比例）。
• PQ（乘积量化，Product Quantization）快速扫描（fast-scan）选项除了在最靠近准确端点外，通常优于其他 PQ 和 SQ（缩放量化，Scalar Quantization）变体。
• 带有细化（refinement）操作的算法在高准确率区间尤为有效。

大规模设置​

SIFT1M（大规模）

Deep1M（大规模）

观察与说明​

• 最有效的方法往往加入了 refinement（细化）阶段，且 Refine(SQfp16，FP16精度的缩放量化）是一个不错的选择。
• 粗量化器（coarse quantizer，如 IVF1024 或 IVF4096_HNSW32）的参数对最终效果影响较小。

GloVe 及 music-100 实验结果​

GloVe 和 music-100 数据集都属于最大内积（Maximum Inner Product Search, MIPS）问题，向量维度为100。以下实验均未进行 OPQ（正交乘积量化，Optimized Product Quantization）预处理。

GloVe

Music-100

观察与说明​

• 带 refinement（细化）的索引方案能获得最优性能。
• PQ（乘积量化）各变体整体表现不佳，竞争力不足。
• HNSW 在 Music-100 的高准确率区间有较强竞争力。