向量数据库介绍_hnswx

向量数据库Faiss

基本信息

博客创建者

徐宁
符号定义：

$S$: 基站信号强度（待预测的目标值）。
$X=(x_1,x_2,\dots ,x_n)$: 特征向量，其中 $x_i$ 表示第 $i$ 个特征。
$Y$: 位置坐标（或区域标识）。
$D=(X_1,Y_1),(X_2,Y_2),\dots ,(X_m,Y_m)$: 样本集，其中每个样本包含特征向量和对应的位置坐标。

$S_{\text{known}}$: 已知区域的基站信号强度。
$D_{\text{known}}$: 已知区域的距离。
$S_{\text{unknown}}$: 未知区域的基站信号强度（待预测的目标值）。
$D_{\text{unknown}}$: 未知区域的距离。
$F$: 预测模型。

Faiss简介

  Faiss的全称是Facebook AI Similarity Search，是FaceBook的AI团队针对大规模相似度检索问题开发的一个工具，使用C++编写，有python接口，对10亿量级的索引可以做到毫秒级检索的性能。
  Faiss实际是一个向量检索库，其目标是将我们自己的候选向量集封装成index数据库，在查询时它可以加速我们检索相似向量TopK的过程。但并不具有存储数据的能力，所有的检索都在内存中实现，数据需要存储在本地。

Faiss工作流程

1.获取用户向量库。
2.使用Faiss构建index，并将向量添加到index中创建index到向量的链接。
3.使用faiss index进行检索。

Faiss常用index优缺点及使用场景

  Faiss检索速度更快是因为使用的检索方式是模糊检索而不是精确检索。虽然更快了，但是召回率肯定低于精确检索。
  对于Faiss索引的构建，一般采用faiss.index_factory，基本所有的index都支持这种构建索引方法。

dim, measure = 64, faiss.METRIC_L2
param = 'Flat'
index = faiss.index_factory(dim, param, measure)
1
2
3

• 三个参数中，dim表示向量维数
• param参数表示传入index的参数，代表需要构建什么类型的索引，这也是最重要的参数。
• measure为度量方法，即查询向量要和向量库内的向量比较时所选择的方法，目前共有八种度量方式：
  • METRIC_INNER_PRODUCT（内积），若要计算余弦相似度，只需要将向量归一化之后再内积即可。
  • METRIC_L1（曼哈顿距离）
  • METRIC_L2（欧氏距离）
  • METRIC_Linf（无穷范数）
  • METRIC_Lp（p范数）
  • METRIC_BrayCurtis（BC相异度）
  • METRIC_Canberra（兰氏距离/堪培拉距离）
  • METRIC_JensenShannon（JS散度）

index构建方法

Flat ：暴力检索

param = ‘Flat’

• 每个向量对应一个索引
• 优点：该方法是Faiss所有index中最准确的，召回率最高的方法，没有之一；
• 缺点：速度慢，占内存大。
• 使用情况：向量候选集很少，在50万以内，并且内存不紧张。

IVFx Flat ：倒排暴力检索

param = ‘IVFx,Flat’

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

• 倒排举例：
  -假设有一组文档如下：
  文档1： “This is a cat.”
  文档2： “The cat is black.”
  文档3： “A black cat is cute.”

  倒排索引之后：
  单词 “This” : 文档1
  单词 “is” : 文档1, 文档2, 文档3
  单词 “a” : 文档1, 文档3
  单词 “cat” : 文档1, 文档2, 文档3
  单词 “The” : 文档2
  单词 “black” : 文档2, 文档3
  单词 “cute” : 文档3

• 缺点：速度也还不是很快。

• 使用情况：相比Flat会大大增加检索的速度，建议百万级别向量可以使用。

• 参数：IVFx中的x是k-means聚类中心的个数

PQx ：乘积量化

param = ‘PQx’

PQ（Product Quantization）是一种向量量化方法，用于在高维向量空间中压缩向量并构建索引。PQ索引是一种高效的索引结构，适用于大规模高维向量库的相似性搜索。

方法：

• PQ量化：将每个高维向量划分为x个子向量（段）。然后对每个子向量进行独立的向量量化，例如使用k-means聚类等方法，得到PQx编码。

• 搜索：在搜索阶段，查询向量也被划分为x个子向量，并且对每个子向量进行独立的向量量化，得到查询的PQx编码。

• 每段向量的检索结果：接下来，对于每个查询的子向量，系统会在索引中分别检索与查询子向量相似的向量。这个过程得到了每个子向量的检索结果，每个结果包含一组最相似的向量（可能存在重叠）。

• 取交集：最后，对于每个子向量的检索结果，将它们的相似向量取交集。交集中的向量就是整个查询向量的最终Top-K结果。

• 优点：速度很快，而且占用内存较小，召回率也相对较高。

• 缺点：召回率相较于暴力检索，下降较多。

• 使用情况：内存及其稀缺，并且需要较快的检索速度，不那么在意召回率，这个过程能够加速搜索，但也可能会因为取交集而降低召回率，需要权衡速度和准确性。选择合适的x值将影响搜索的性能和结果。

IVFxPQy 倒排乘积量化

param = ‘IVFx,PQy’

方法：在IVFxPQy中，向量库中的每个向量先被乘积量化为多个子向量，形成PQy编码，然后建立倒排索引，将PQy编码与对应的向量ID关联起来。在搜索阶段，查询向量也进行乘积量化得到PQy编码，然后在倒排索引中查找与查询编码相似的向量，最后取交集得出最终的TopK。

• 优点：工业界大量使用此方法，各项指标都均可以接受。
• 缺点：同上
• 使用情况：IVFxPQy相对于PQx可能在速度和召回率上有更好的表现，但也会占用更多的内存资源，综合性能较好。

LSH 局部敏感哈希

param：‘LSH’

方法：

• 将高维向量划分为多个局部区域（临近区域），对每个局部区域使用不同的哈希函数进行哈希。

• 哈希函数的设计使得在高维空间中距离较近的向量在局部区域内有很大的概率被映射到相同的哈希桶中。

• 当进行相似性搜索时，将查询向量通过相同的哈希函数映射到相应的局部区域，并在对应的局部区域内搜索相似的向量。

• 优点：

  • 训练速度快：LSH的训练过程简单，主要是设计和选择合适的哈希函数。
  • 支持分批导入：LSH可以在数据导入时进行分批处理，方便处理大规模的向量库。
  • 占用内存较小：由于LSH使用哈希函数映射，存储的数据量较小

• 缺点：

  • 召回率较低：LSH是一种近似算法，召回率（recall）通常较低，即可能会漏掉一些相关向量，特别是对于较近的向量，可能无法完全检索到。
  • 精度较低：由于LSH是一种近似方法，搜索结果可能会包含一些不相关的向量，从而影响搜索的精度。

• 使用情况：候选向量库非常大（百万级），离线检索，内存资源比较稀缺的情况

HNSWx

param = ‘HNSWx’

方法:

• 初始化：首先，为向量库中的每个向量随机生成一个较短的向量（这些向量称为入口点），用于构建图的第一层。

• 构建图层：从第一层开始，逐层构建图。对于每个向量，使用局部敏感哈希（LSH）或其他相似性度量方法，找到在当前层与之距离较近的向量，并将它们添加到当前向量的邻居列表中。

• 添加连接：对于每个向量，将其与其邻居在当前层中进行连接。连接操作意味着两个向量在图上产生一条边，使得它们在搜索时可以相互访问。

• 层次化：重复步骤2和步骤3，依次构建更高层的图。每一层的向量数量会逐渐减少，从而形成一个层次化的结构。

• 设置入口点：选择每一层中的若干个向量作为入口点，这些入口点用于加速搜索。入口点应该是相对于其他向量更具代表性和区分性的向量。

• 图结构优化：对构建完成的图进行优化，例如移除冗余连接、平衡各层向量的数量等，以提高索引的性能。

• 保存索引：将构建完成的HNSWx索引保存起来，用于后续的相似性搜索。

• 优点：该方法为基于图检索的改进方法，检索速度极快，10亿级别秒出检索结果，而且召回率几乎可以媲美Flat，最高能达到惊人的97%。检索的时间复杂度为loglogn，几乎可以无视候选向量的量级了。并且支持分批导入，极其适合线上任务，毫秒级别体验。

• 缺点：构建索引极慢，占用内存极大（是Faiss中最大的，大于原向量占用的内存大小）

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

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