10 亿图片仅需 17.7微秒:Facebook AI 实验室开源图像搜索工具Faiss

Facebook的 FAIR 最新开源了一个用于有效的相似性搜索和稠密矢量聚类的库,名为 Faiss,在10亿图像数据集上的一次查询仅需17.7 微秒,比此前的方法准确度略高,而且快 8.5 倍。


Faiss 是由 Facebook AI Research(FAIR)开发的一个用于有效的相似性搜索(similarity search)和稠密矢量聚类(clustering of dense vectors)的库。它包含了在任何大小的向量集合里进行搜索的算法,向量集合的大小甚至可以达到装不进 RAM。它还包含了用于评估和参数调优的支持代码。Faiss 是用 C ++编写的,带有 Python / numpy 的完整包装。其中最有用的一些算法是在 GPU 上实现的。


我们比较了 Wieschollek et al. 在 Sift1B 数据集的10 亿 SIFT 图像特征,其中 nq = 104。我们比较了相同内存使用情况下的搜索效果,以得到类似的精确度(更精确的方法可能需要更多搜索时间或更大的内存使用)。在单个 GPU 上,每个向量大小是 m= 8 bytes,我们的结果是 R@10 = 0.376,每个查询向量需 17.7 µs。而在作比较的研究中,R@10 = 0.35,每个查询向量需 150 µs。也就是说,我们的实现准确度更高,而且速度是它的 8.5 倍。


介绍


Faiss 包含了几种用于相似性搜索的方法。它假定示例可以被表示为向量,以及可以通过整数识别,并且这些向量可以与 L2 位距或点积进行比较。与一个查询向量(query vector)相似的向量是具有最低 L2 位距或最高点积的查询向量。Faiss 还支持余弦相似性(cosine similarity),因为这是在标准化向量上的点积。


大多数方法,例如基于二元向量和紧凑量化代码的方法,仅使用向量的压缩表征,并不需要保留原始向量。这通常会导致搜索的准确度降低,但是这些方法可以再单个服务器上的主存储器中扩展到数十亿个向量。


GPU 上的实现可以接受来自 CPU 或 GPU 存储器的输入。在装有 GPU 的服务器上,GPU 索引可以被用作 CPU 索引的插入替换(例如,使用 GpuIndexFlatL2 替换 IndexFlatL2),并且可以自动处理发往/来自 GPU 存储器的副本。


构建


这个库基本上是用 C++ 实现的,带有可选的通过 CUDA 提供的 GPU 支持,以及一个可选的 Python 接口。使用 Makefile 进行编译。详细信息可参见INSTALL:https://github.com/facebookresearch/faiss/blob/master/INSTALL


Faiss 如何工作


Faiss 是围绕存储了一个向量集的索引类型(index type)构建的,并且提供利用 L2 和/或点积向量比较在其中进行搜索的函数。有些索引类型是简单的基线,例如精确搜索。大多数可用的索引结构都对应了一下的几点权衡:


  • 搜索时间

  • 搜索质量

  • 每个索引向量使用的内存大小

  • 训练时间

  • 无监督训练对外部数据的需求

获取 Faiss 的完整文档


论文地址:https://arxiv.org/pdf/1702.08734.pdf

开源地址:https://github.com/facebookresearch/faiss


via  新智元



魔多,专注VR/AR和AI,有料更有趣


// share