如果我们愿意牺牲一部分精确度，相似性搜索的速度可以提高几个数量级，但是会偏离参考结果。例如，将图像相似性搜索的第一和第二个结果交换，可能没有什么太大影响，因为它们都是给定查询的正确结果。加速搜索涉及一些数据集合的预处理，我们将这项操作称之为“索引”。

　　这使我们确定了三个感兴趣的研究指标：

速度：在整个数据库中寻找 10 个（或其他数字）最相近的矢量需要花费多长时间？最好的情况是比暴力算法耗时短，否则索引就没有任何意义了。

内存用量：这个方法需要多少 RAM？比传统矢量多还是少？Faiss 仅支持在 RAM 搜索，因为磁盘数据库的数量级要慢一些，即使是 SSD。

准确度：返回的结果列表和暴力搜索结果的匹配度如何？准确度可以通过对结果列表中优先返回最邻近单位的检索数量进行评估，或者是通过衡量 10 个最先返回的最邻近单位的平均分数来评估（这种方法被称为“10－intersection”）。

　　我们通常会评估固定内存使用速度和精度之间的关联。Faiss 采用的是压缩原始矢量的方法，因为这是扩展到十亿级矢量数据库的唯一方法：以每个矢量占用 32 字节计，当规模达到 10 亿矢量后，这些矢量会占据大量的存储空间。

　　大部分索引库包含约 100 万个矢量，我们认为这个规模很小。比如说，nmslib拥有非常有效的算法，速度比 Faiss 快，但同时需要更多的存储空间。

　　评估十亿个矢量

　　工程界中对于这种规模的数据集并没有一个完善的标准，我们比较了一些研究结果，并进行评估。

　　Deep1B是一个有 10 亿张照片的图像库，我们在这上面评估精度。每张照片都被卷积神经网络（CNN）处理过，atv，且 CNN 中的一个激活图（activation map）会被当作图像描述符（deor）。这些矢量可以和欧氏距离进行比较，以量化图像之间的相似度。

　　Deep1B 有一个小的图像检索库，且处理了这些图像的暴力算法提供了一个真实的相似性搜索结果。因此，如果我们运行搜索算法，我们可以评估结果中的 1-recall@1。

　　选择索引

　　为了评估，我们把内存空间大小限定为 30GB RAM。这个内存空间约束我们选择索引方法和参数。在 Faiss 中，索引方法具体表现为一个字符串，如：OPQ20_80,IMI2x14,PQ20。

　　这个字符串指示了用于矢量预处理的具体步骤（OPQ20_80），一个指示数据库应该如何被分割的选择机制（IMI2x14），以及一个指示产品量化编码矢量的编码组件（PQ20），这个编码组件会产生成 20 字节的代码。因此，内存使用（包括间接使用）低于 30 GB RAM。

　　我们知道这听起来有点“太技术”，因此 Faiss 的开发文件会提供相应的指导，即如何根据你的需求来提供最合适的索引类型。

　　一旦确定了索引类型，检索就开始了。这个算法会处理 10 亿个矢量，并将这些矢量置于所一个索引中。索引可以存储在磁盘上，或者立即使用，同时索引中的搜索、添加/删除可以交叉输入。

　　在索引中检索

　　索引就绪后，可以设置一组搜索事件参数来调整检索方法。为了评估，我们使用单线程进行搜索。由于内存使用量已经被固定，我们需要优化精确度和搜索时间之间的权衡。这也意味着，我们要能在尽可能少的时间内，使 1-recall@1 达到 40%。

　　幸好，Faiss 有一个自动调节机制，可以扫描参数空间，并收集提供最佳操作点的空间，也就是在给定精度的情况下最好的潜在搜索时间，反之亦然。在 Deep1B 中，操作点可以进行可视化，如下图所示：

　　在这个量化表中，我们可以看到，使 1-recall@1 达到 40％ 的查询时间少于 2 微秒/矢量，或者将时间限定为 0.5 微秒，我们可以达到 30%。2 微秒的检索时间意味着在一个单核上每秒查询 500 次（500 QPS）。

　　这个结果可以和这个领域中最先进的研究结果进行比较。Babenko 和 Lempitsky 于 2016 年撰写了一篇名为 “Efficient Indexing of Billion-Scale Datasets of Deep Deors” 的论文，论文中提到，使用 Deep1B 时，他们需要花费 20 微秒来使 1-recall@1 达到 45%。

　　用 GPU（图形处理器）处理十亿级数据集