笔记。

背景

大数据领域检索分两类：

• 结构化数据检索，如ElasticSearch、Solr、关系型数据库等
• 非结构化数据检索，如图片、音频、视频等

向量检索第一步：对非结构化的数据进行向量化表示

即物品的向量要满足相似物品的距离近，不相似的距离远，这种对物品进行特征表示的方法称为度量学习（metric learning)。

传统度量学习方法：线性投影 核方法

缺点：无法解决非线性特征

深度度量学习：通过激活函数提供非线性变换能力

概述

向量检索定义：在一个给定向量数据集中，按照某种度量方式，检索出与查询向量相近的K个向量（K-Nearest Neighbor, KNN），但KNN计算量大，通常只关注近似近邻（Approximate Nearest Neighbor, ANN）问题。

向量检索算法需解决两个问题：

• 减少候选向量集：通过各种策略，比如构建索引结构，实现检索时绕开不相关向量；
• 降低单个向量计算的复杂度：找到候选向量后，要对单个向量的相似度进行计算，但复杂度搞，需要处理。

经典检索算法有三个：

• NSW

  关键是在构图过程中通过贪婪搜索算法记录下搜索最优路径。

• HNSW

  对NSW的升级，使用跳表结构代替NSW的链表结构通过空间换时间的方法将向量检索的复杂度从多重对数复杂度降至对数复杂度。

• IVF_PQ

  通过乘积量化（PQ）将向量进行压缩，降低计算复杂度；通过聚类加倒排（IVF）减少检索候选集。

其它：

IVFSQ8、IVF_FLAT是IVF算法变种，分别在召回率、内存占用和响应时间做了折中处理；适用于测试生成groud truth集合的FLAT纯暴力检索算法。

常见的四种向量度量方式：

欧氏距离（L2）、余弦、内积（IP）、杰卡德距离

通常欧式距离用于图片检索，余弦用于人脸识别，内积、杰卡德距离多用于推荐。

一些结论

高召回率从高到底

FLAT（仅供测试使用） > HNSW > IVFFLAT > IVF*SQ8 *> IVF_PQ

查询响应时间从低到高

HNSW > IVF*PQ *> IVF_SQ8 > IVF_FLAT > FLAT

资源占用从高到底

IVF_PQ > IVF_SQ8 > HNSW

如，内存和磁盘足够，百万~千万级，选HNSW算法；召回率要求不高，相应时间要求较高，集群资源有限，数据集较大（亿级），选IVF_SQ8算法。