相似性搜索工具-Faiss

Faiss

背景

目标：在千万规模的数据上，高效计算内积/相似性，返回top-K个结果

文章：Billion-scale similarity search with GPUs

代码：https://github.com/facebookresearch/faiss

简介：

• 时间、质量和训练速度的权衡。
• Faiss 是一个用于有效的相似性搜索和密集向量聚类的库。其包含了在任何大小（甚至可以大到装不进 RAM）的向量集中进行搜索的算法。其也包含用于评估和参数调整的支持性代码。
• Faiss 是围绕一种存储了一个向量集的索引类型（index type）而构建的，并且提供了一个使用 L2 或点积向量比较在其中进行搜索的函数。

方法：提出了一种用于 k-selection 的设计，其可以以高达理论峰值性能 55% 的速度进行运算，从而实现了比之前最佳的 GPU 方法快 8.5 倍的最近邻KNN搜索。另外，基于积量化（product quantization）的暴力计算、近似和压缩域搜索（compressed-domain search）提出优化过的设计，从而将其应用到了不同的相似性搜索场景中。

效果： 35 分钟内从 Yfcc100M 数据集的 9500 万张图像上构建一个高准确度的 k-NN 图（graph），也可以在 12 个小时内在 4 个 Maxwell Titan X GPU 上构建一个连接了 10 亿个向量的图。

实现细节：

• WarpSelect：文中提出的 k-selection 的设计，完全在寄存器（register）中维持状态，且仅需要在数据上进行单次通过，从而避免了 cross-warp synchronization，使用merge-odd 和 sort-odd 作为原语。

  WarpSelect的整体流程如下：

  

• 针对特定lane j的流程如下：

使用方法

• 安装：pip install faiss-cpu

• 使用示例：https://github.com/facebookresearch/faiss/wiki/Getting-started

  • 准备数据
  • 构建索引：可以选择的索引格式为https://github.com/facebookresearch/faiss/wiki/Faiss-indexes
  • 搜索查询：search(query, top-k)

• 加速搜索的一些技巧：https://github.com/facebookresearch/faiss/wiki/Faster-search

  • 使用复合的索引：https://github.com/facebookresearch/faiss/wiki/Faiss-indexes-(composite)
  • IndexFlatL2 和 IndexIVFFlat都要存储所有的向量数据，对于大型数据集是不现实的, Faiss基于PQ提供了变体IndexIVFPQ来压缩数据向量（一定的精度损耗）

参考资料

• Faiss教程：入门

• Faiss的基础使用：https://waltyou.github.io/Faiss-Introduce/

• Faiss Indexs 的进一步了解：https://waltyou.github.io/Faiss-Indexs/

• 向量检索在闲鱼视频去重的实践：https://zhuanlan.zhihu.com/p/43972326

• 阿里BE引擎深度集成开源的KNN库–FAISS
  改造定制使其支持向量索引的分布式构建和查询，实现多种基于量化的方法如粗量化、积量化以及粗量化 + 积量化的组合等方法，并且在线查询的延时、索引构建的性能都很优秀。