向量数据库与Faiss库

什么是FAISS

FAISS(Facebook AI Similarity Search)是由Meta的基础人工智能研究团队开发的一个用于高效处理大规模密集向量相似度搜索聚类任务的开源库。Faiss用C++编写,并支持Python接口。除此以外,对一些核心算法提供了GPU实现。

Faiss工作机制

Faiss的工作机制简单来说就是把我们自己的候选向量集封装成一个index数据库,并提供一个计算相似性的度量函数进行搜索,它可以加速我们检索相似向量TopK的过程,其中有些索引还支持GPU构建,可谓是强上加强。

其工作分两个过程: 构建数据、查询数据。

其中Faiss训练指的是对向量进行聚类,是构建数据中的一个重要步骤。在实际应用时,使用到的三个对象:向量维度索引类型度量方法。在构建数据的时候需要选定向量的维度以及索引类型,进行数据训练以及存储;在查询数据的时候需要选定度量方法计算相似度。

索引类型/算法

Faiss中的索引类型表示的是算法。一种索引类型即一种算法,当我们选择了一种索引类型之后,Faiss会按照算法定义好的数据结构存储向量数据。举个例子我们熟悉的es索引,它使用倒排索引的结构即单词-文档矩阵来存储数据,以便更加快速的进行全文搜索。FAISS 支持多种索引类型,这些索引类型根据不同的需求和数据集特点进行了优化。以下是一些常见的 FAISS 索引类型:

  1. Flat 索引:
    • IndexFlatL2: 使用 L2 距离(欧氏距离)的扁平索引。
    • IndexFlatIP: 使用内积的扁平索引。
  2. 量化索引:
    • IndexIVFFlat: 倒排文件(IVF)索引,与扁平索引结合使用。
    • IndexIVFPQ: 结合了倒排文件和乘积量化(PQ)的索引。
    • IndexIVFFaiss: 使用 FAISS 方法优化的 IVF 索引。
    • IndexIVFHNSW: 结合了倒排文件和分层导航小世界(HNSW)的索引。
  3. 乘积量化索引:
    • IndexPQ: 乘积量化索引,使用 PQ 进行向量压缩。
    • Index2Layer: 两层 PQ 索引,为了更好的压缩和搜索性能。
  4. 树结构索引:
    • IndexLSH: 局部敏感哈希(LSH)索引,适用于大规模数据集。
    • IndexPQ: 使用 PQ 进行向量压缩的索引。
  5. 图索引:
    • IndexHNSWFlat: 使用扁平索引和 HNSW 图结构的索引。
    • IndexHNSWPQ: 结合了 PQ 量化和 HNSW 图结构的索引。
  6. 复合索引:
    • IndexPreTransform: 允许在搜索之前对向量应用一个或多个变换(如 PCA、白化等)。
    • IndexIDMap: 允许在索引中存储额外的 ID 信息,通常与其他索引类型结合使用。
  7. 其他索引:
    • IndexScalarQuantizer: 标量量化索引,对每个向量维度使用不同的量化方法。
    • IndexBinaryFlat: 用于二进制向量的扁平索引。
    • IndexBinaryIVF: 用于二进制向量的倒排索引。

每种索引类型都有其特定的适用场景和性能特征。例如,扁平索引(Flat)提供精确的最近邻搜索,但不适合大规模数据集。而倒排文件(IVF)索引适合大规模数据集,但提供的是近似最近邻搜索。乘积量化(PQ)索引和图索引(如 HNSW)旨在提供更高效的搜索和更好的空间压缩。

Faiss 几种常用的索引类型

IndexFlatL2 暴力查询

faiss 中最简单的索引,它会尽职尽责的和所有数据进行比对,所以它是所有索引类型中最慢的一种,但是也是最简单最准确的索引类型,同时,因为类型简单,也是内存占用量最低的类型。

  • 优点:该方法是Faiss所有index中最准确的,召回率最高的方法,没有之一;
  • 缺点:速度慢,占内存大。

IndexIVFFlat 查询优化

更快的查询速度, 在向量数据库中,对于“向量检索”最简单的性能优化方案,便是对索引数据进行分区优化,将数据通过“沃罗诺伊图单元”(也被叫做泰森多边形)来进行切割(类似传统数据库分库分表)。

  • 优点:IVF主要利用倒排的思想,在文档检索场景下的倒排技术是指,一个kw后面挂上很多个包含该词的doc,由于kw数量远远小于doc,因此会大大减少了检索的时间。在向量中如何使用倒排呢?可以拿出每个聚类中心下的向量ID,每个中心ID后面挂上一堆非中心向量,每次查询向量的时候找到最近的几个中心ID,分别搜索这几个中心下的非中心向量。通过减小搜索范围,提升搜索效率。
  • 缺点:速度也还不是很快。存储很大

IndexPQ 存储优化

是海量数据、以及数据快速增长的场景中,业务所使用的服务器资源的内存完全装不下我们的向量数据。无法支撑我们采用分区索引或者平面索引这种相对精确的相似性检索,我们需要想办法大幅降低内存占用。

  • 优点:利用乘积量化的方法,改进了普通检索,将一个向量的维度切成x段,每段分别进行检索,每段向量的检索结果取交集后得出最后的TopK。因此速度很快,而且占用内存较小,召回率也相对较高。
  • 缺点:召回率相较于暴力检索,下降较多。

IndexIVFPQ 查询存储优化

  • 优点:工业界大量使用此方法,各项指标都均可以接受,利用乘积量化的方法,改进了IVF的k-means,将一个向量的维度切成x段,每段分别进行k-means再检索。
  • 缺点:集百家之长,自然也集百家之短

使用情况:一般来说,各方面没啥特殊的极端要求的话,最推荐使用该方法!

IndexLSH 局部敏感哈希

原理:哈希对大家再熟悉不过,向量也可以采用哈希来加速查找,我们这里说的哈希指的是局部敏感哈希(Locality Sensitive Hashing,LSH),不同于传统哈希尽量不产生碰撞,局部敏感哈希依赖碰撞来查找近邻。高维空间的两点若距离很近,那么设计一种哈希函数对这两点进行哈希计算后分桶,使得他们哈希分桶值有很大的概率是一样的,若两点之间的距离较远,则他们哈希分桶值相同的概率会很小。

  • 优点:训练非常快,支持分批导入,index占内存很小,检索也比较快
  • 缺点:召回率非常拉垮。

使用情况:候选向量库非常大,离线检索,内存资源比较稀缺的情况

IndexHNSWFlat 图索引

  • 优点:该方法为基于图检索的改进方法,检索速度极快,10亿级别秒出检索结果,而且召回率几乎可以媲美Flat,最高能达到惊人的97%。检索的时间复杂度为loglogn,几乎可以无视候选向量的量级了。并且支持分批导入,极其适合线上任务,毫秒级别体验。
  • 缺点:构建索引极慢,占用内存极大(是Faiss中最大的,大于原向量占用的内存大小)

参数:HNSWx中的x为构建图时每个点最多连接多少个节点,x越大,构图越复杂,查询越精确,当然构建index时间也就越慢,x取4~64中的任何一个整数。

使用情况:不在乎内存,并且有充裕的时间来构建index

扩展阅读

Faiss 向量检索引擎
Meta向量数据库Faiss介绍
Faiss入门及应用经验记录
一文入门Faiss:10亿级向量相似度查询

此处评论已关闭