平日我们都邑在肯定的内存资本下在速度和精准度之间衡量。Faiss 专注于紧缩原始向量的办法，因为这是扩大到数十亿向量数据集的不二之选：当兵须索引十亿个向量的时刻，每个向量 32 字节，就会消费很大年夜的内存。

很多索引类库实用于百万阁下向量的小范围数据集，比如 nmslib 就包含了一些适于这种范围数据的异常高效的算法，这比 Faiss 快很多，但须要消费更多的存储。

基于 10 亿向量的评估

因为工程界并没有针对这种大年夜小数据集的公认基准，所以我们就基于研究结不雅来评估。

假设有一张建筑物的图片——比如某个你不记得名字的中等范围城市的市政大年夜厅——然后你想在图片集中查找所有该建筑物的图片。因为不记得城市的名字，此时传统 SQL 中常用的 key/value 萌芽就帮不膳绫铅了。

评估精度基于 Deep1B，这是一个包含 10 亿图片的数据集。每张图片已经由过程 CNN 处理，CNN 激活图之一用于图片描述。比较这些向量之间的欧氏距离，就能量化图片的类似程度。

Deep1B 还带有一个较小的萌芽图片集，以及由暴力算法产生的┞锋实类似性搜刮结不雅。是以，如不雅运行一个搜刮算法，就能评估结不雅中的 1-recall@1。

选择索引

为了评估，我们把内存限制在 30G 以内。这个内存束缚是我们选择索引办法和参数的根据。Faiss 中的索引办法表示为一个字符串，在本例中叫做 OPQ20_80,IMI2x14,PQ20。

该字符串包含的信罕见，感化到向量上的预处理步调(OPQ20_80)，一个选择机制(IMI2x14)注解数据库若何分区，以及一个编码组件(PQ20)表示向量编码时应用一个产品量化器(PQ)来生成一个 20 字节的编码。所以在内存应用上，包含其他开销，累计少于 30G。

这听起来技巧性较强，所以 Faiss 文档供给了应用指南，来解释若何选择知足需求的最佳索引。

选好了索引类型，就可以开端履行索引过程了。Faiss 中的算法实现会处理 10 亿向量并把它们置于一个索引库中。索引会存在磁盘上或急速应用，检索和增长 / 移除索引的操作可以穿插进行。

萌芽索引

当索引预备好今后，一系列搜刮时光参数就会被设置来调剂算法。为便利评估，这里应用单线程搜刮。因为内存消费是受限并固定的，所以须要在精确度和搜刮时光之间衡量优化。举例说来，这表示为了获取 40% 的 1-recall@1，可以设置参数以花费尽可能短的搜刮时光。

荣幸的是，Faiss 带有一个主动调优机制，能扫描参数空间并收集供给最佳操作点的参数;也就是说，最可能的搜刮时光对应某个精确度，反之亦然，最优的精确度对应某个搜刮时光。Deep1B 中操作点被可视化为如下图示：

本图中我们可以看到，达到 40% 的 1-recall@1，请求每次萌芽耗时必须小于 2ms，或者能优化到耗时 0.5ms 的话，就可以达到 30% 的 1-recall@1。一次萌芽耗时 2ms 表示单核 500 QPS 的处理才能。

这个结不雅根本上能媲美今朝业内最新研究结不雅了，即 Babenko 和 Lempitsky 在 CVPR 2016 揭橥的论文“Efficient Indexing of Billion-Scale Datasets of Deep Descriptors”，这篇论文介绍了 Deep1B 数据集，他们达到 45% 的 1-recall@1 须要耗时 20ms。

10 亿级数据集的 GPU

我们把 roofline model 作为指南，它指出应当尽量让内存带宽或浮点运算单位满载。Faiss 的 GPU 实如今单 GPU 上的机能要比对应的 CPU 实现快 5 到 10 倍，像英伟达 P100 如许的新型 Pascal 架构硬件甚至会快 20 倍以上。

一些机能关键数字：

• 对于近似的索引，应用 YFCC100M 数据集中的 9500 万张图片，一个基于 128D CNN 描述符的暴力 k 近邻图(k=10)，只需 4 个 Maxwell Titan X GPU 就能在 35 分钟内构建完成，包含索引构建时光。
• 十亿级向量的 k 近邻图如今触手可及。基于 Deep1B 数据集，可以构建一个暴力 k-NN 图(k=10)，达到 0.65 的 10-intersection，须要应用 4 个 Maxwell Titan X GPU 花费不到 12 小时，或者达到 0.8，应用 8 个 Pascal P100-PCIe GPU 消费不到 12 小时。Titan X 设备可以在不到 5 小时生成低质量的图。
• 其他组件也表示出了骄人的机能。比如，构建上述 Deep1B 索引须要应用 k 均值聚类 6701 万个 120 维的向量到 262,144 个簇，对于 25 E-M 迭代须要在 4 个 Titan X GPU(12.6 tflop/s)上花 139 分钟，或者在 8 个 P100 GPU(40 tflop/s)上花 43.8 分钟。留意聚类的练习数据集并不须要放在 GPU 内存中，因为数据可以在须要时流到 GPU 而没有额外的机能影响。

底层实现

Facebook AI 研究团队 2015 年就开端开辟 Faiss，这建立在很多研究结不雅和大年夜量工程实践的基本之上。对于 Faiss 类库，我们选择聚焦在一些基本技巧方面的优化，特别是在 CPU 方面，我们重度应用了：

• 采取多线程来应用多核资本，并在多个 GPU 上履行并行检索。
• 应用 BLAS 类库经由过程矩阵和矩阵乘法来高效精准地完成距离计算。一个不采取 BLAS 的暴力实现很难达到最优。BLAS/LAPACK 是 Faiss 独一强迫依附的软件。
• 采取机械 SIMD 向量化和 popcount 加快自力向量的距离计算。

关于 GPU

对于前述类似性搜刮的 GPU 实现，k-selection(查找 k 个最小或最大年夜元素)有一个机能问题，因为传统 CPU 算法(比如堆查找算法)对 GPU 并不友爱。针对 Faiss GPU，我们设计了文献中已知的最快轻量 k-selection 算法(k<=1024)。所有的中心状况全部保存在存放器，便利高速读写。可以对输入数据一次性完成 k-select，运行至高达 55% 的理论峰值机能，作为输出的峰值 GPU 内存带宽。因为其状况零丁保存在存放器文件中，所以与其他内核很轻易集成，使它成为极速的精准和近似检索算法。

大年夜量的精力投在了为高效策略做铺垫，以及近似搜刮的内核实现。经由过程数据分片或数据副本可以供给对多核 GPU 支撑，而不会受限于单 GPU 的可用显存大年夜小;还供给了对半精度浮点数的支撑(float16)，可在支撑的 GPU 上做完全 float16 运算，以及早期架构上供给的中心 float16 存储。我们发明以 float16 编码向量技巧可以做到精度无损加快。

　　推荐阅读

　　从概念走向实操 区块链的“风”真要来了

Tech Neo技巧沙龙 | 11月25号，九州云/ZStack与您一路商量云时代收集界线治理实践 按照区块链监管的请求，国内>>>详细阅读

本文标题：Facebook开源相似性搜索类库Faiss，超越已知最快算法8.5倍

地址：http://www.17bianji.com/lsqh/38866.html

 1/2    1