随着互联网的不断发展，产生了各种各样的海量数据，比如图片、文本、视频和语音等非结构化数据，这些数据可以通过人工智能技术提取出特征向量，然后通过对这些特征向量的计算和检索来实现对非结构化数据的分析和检索，如何对非结构化的向量数据进行高效检索即为向量检索技术的核心问题。
向量检索的应用场景非常丰富，比如：
- 推荐系统：广告推荐、猜你喜欢等；
- 图片识别：以图搜图，通过图片检索图片。具体应用如：车辆检索和商品图片检索等；
- 自然语言处理：基于语义的文本检索和推荐，通过文本检索近似文本；
- 声纹匹配，音频检索；
- 文件去重：通过文件指纹去除重复文件；
向量距离计算
浮点型向量计算方式
- 内积（IP）/点积（DP）：两个向量在方向上的差异，内积值越大夹角越小越相似。通常用于推荐场景。
- 欧式（L2）：两点之间最短的直线距离，距离值越小越相似。能够体现个体数值特征的绝对差异，更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异。
- 曼哈顿（L1）：两个点在标准坐标系上绝对轴距总和。
- 余弦（Cosine）：两个向量之间的夹角余弦值，余弦相似度值越大夹角越小越相似。归一化后，内积与余弦相似度计算公式等价。
余弦距离和内积距离更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题。
举例：统计两部剧的用户观看行为，用户A的观看向量为(0,1)，用户B为(1,0)；此时二者的余弦距很大，而欧氏距离相对较小；我们分析两个用户对于不同视频的偏好，更关注相对差异，显然应当使用余弦距离或内积距离。
二值型向量计算方式
- 汉明距离（Hamming）：二进制字符串之间的距离。两个等长字符串之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。
- 杰卡德距离（Jaccard）：数据集之间的相似度，计算方式为数据集交集的个数和并集个数的比值。
- 谷本距离（Tanimoto）：对于二值变量，谷本系数等价于杰卡德距离。
基础算法
向量检索的本质是近似最近邻（ANN，Approximate Nearest Neighbors）搜索，通过尽可能减小查询向量的搜索范围，从而提高查询速度。目前业界的近邻搜索算法主要分为基于树、图、量化和哈希四类。
- 基于树
- KD树
- Annoy
- 基于图
- NSW
- HNSW
- 基于量化
- SQ
- PQ
- 基于哈希
- LSH
KD树（K-dimension tree），每次选择一个维度切割成两个子区域，构建形成树结构，搜索时利用树进行二分查找从而缩小搜索范围。
Annoy（Approximate Nearest Neighbors Oh Yeah），用超平面把高维空间分割成多个子空间，并把这些子空间以树型结构存储的索引方式。查询时顺着树结构找到距离目标向量较近的一些子空间，然后比较这些子空间里的所有向量。
K-Means聚类算法，通过不断分类找平均点，直到分类趋于稳定，搜索时只需要找出距离最近的聚类中心，以达到缩小范围的目的。但是会存在遗漏的问题，需要衡量聚类数量。
导航小世界（NSW，Navigable Small World），图结构建立过程：每次新增向量都和最近的几个向量建立连接。在搜索的过程中按照先粗快后细慢的方式快速导航到目标节点。
分层的导航小世界（HNSW，Hierarchical Navigable Small World），在NSW的基础上增加多个层级结构，最下层是包含所有节点的图结构，越往上层包含的节点数越少，最上面的节点最稀疏。搜索时上层连线长便于快速导航，下层连线短便于精细化搜索。
标量量化（ SQ，ScalarQuantization ），将每一个维度量化成指定位数的一个数，比如将32位的int量化成8位的int，通过损失一定的精度，缩减存储和计算成本，比较简单。
乘积量化（PQ，Produce Quantization），把向量用质心（聚类中心）编码表示，称为量化。质心编码对应一个码本，在高维向量中存在维度灾难问题，码本可能大到不可接受，此时可以先降维，将高维向量先分成多个低纬子向量，然后对每个子向量进行k-means聚类训练。子空间拆分实际上是把聚类数量或者说码本大小的增长从指数模式变成加法模式，从而节省内存。
位置敏感哈希（LSH，Locality Sensitive Hashing），位置越近或者越相近发生碰撞的概率越高，碰撞的向量放在同一个桶里。搜索时先计算查询向量的哈希值，找到相应的桶，从而实现缩小查询范围。
其他ANN算法见：ANN-Benchmark