on
向量检索
之前的一篇文章讨论了基于倒排索引的广告检索，这种形式的索引通常用于传统的广告场景中。本篇文章来讨论下在电商广告场景下，普遍使用的另一种检索方式——向量检索。
向量检索是什么
向量检索是在给定候选集中检索出与查询向量最接近的K个向量，我们称之为KNN（K-Nearest Neighbor）问题。如果想得到准确的KNN结果，那就需要逐个计算查询向量和候选集中每一个向量的距离（暴力检索），这在大数据在线场景下显然是不可行的，因此我们一般只关注近似的KNN结果，我们称之为ANN（Approximate Nearest Neighbor）问题。
通过构造ANN向量索引，可以在少量牺牲检索精度的情况下，大幅的提高检索的性能。我们一般通过召回率（recall rate）来评价ANN向量索引的精度：
\[recall=\frac{N \cap M}{K}\]N是通过ANN索引检索出的结果集，M是真实的结果集，一般通过暴力检索得到。
向量检索的优势
相比传统的基于倒排的索引，向量检索的优势有：
- 倒排索引的结果只有：“是” 或 “否”，因此存在两个问题：当结果集过多时，如何进行截断？结果集过少时，如何进行补充？而向量检索则没有这种问题，因为它的检索结果是按照“相似度”进行排序的，所以可以直接指定结果集的大小。
- 可以使用更多的无法构建倒排的字段进行检索，如：item的CTR、价格，甚至图像。
- 最重要的一点，提高平台的转化效率。向量检索能够很好的集成AI技术，如通过DNN生成向量，甚至可以通过DNN计算向量的相似度，这些都有助于提高平台的整体转化效率。
向量索引
向量检索的核心问题是：如何构造高召回率、高性能的向量索引。常用的方法有：
1. 基于树
基于树的索引有很多种，但思想是基本一致的，都是通过超平面对数据集进行不断的切分，将其划分成一个个的子节点，以此提高查询效率。
如常见的K-D树，通过选取当前向量空间中方差最大维度的中位数作为超平面，将向量空间分割为两个子空间，然后对两个子空间进行同样的操作，直至将空间分割至只包含一个元素时，完成构建，如下图所示。查询时也是大致相同的逻辑，但查询到叶子节点后，需要向上回溯，以找寻更优结果。
基于树的索引，在维度较低时能达到比较好的效果，但对于高维数据，它的效果则很差，一般认为对于d维数据，只有在数据量远远大于2^d时，才能达到比较好的效果。否则在查询时，会遍历大部分的节点，性能堪比暴力检索。
2. 基于局部敏感哈希
局部敏感哈希是通过构造一个特殊的哈希函数，将相似度高的两个向量经过哈希后能够分到同一个哈希桶中。查询时，查询向量经过哈希得到桶号后，将该桶中的全部向量与查询向量逐个计算，得到最终结果。
基于局部敏感哈希的方法，难点就在于如何构造哈希函数，并且不同的相似度度量方式，对应的哈希函数都不同，有的度量方式甚至无法找到对应的哈希函数。
3. 基于图
基于图的向量索引是工业界目前应用最广泛的，比如Elastic Search、Faiss、Vespa中的向量索引，使用的都是基于图的HNSW索引。 基于图的向量索引，其大致的思想基本都是构建邻接图，选取搜索的初始节点，然后通过一个贪心的搜索算法，进行查询。 不同的图索引，区别也就是构建邻接图的方式不同、选取初始节点的方式不同、贪心搜索的终止条件不同。
下面以Navigable Small World (NSW)为例简要介绍下。
NSW构建的邻接图中，有长边也有短边，短边用于精确搜索，长边用于加速搜索。
查询时，随机选取一个点作为entry point，然后搜索其邻接点，将其邻接点作为候选点，如果一个候选点与query point的距离，大于当前结果集中的第k个节点与query point的距离，那么就丢弃该候选点；否则将该候选点加入结果集中，然后继续搜索该候选点的邻接点。贪心搜索的终止条件是搜索完毕所有的候选点。
构建时，直接使用查询时的搜索算法获取当前插入点的邻接点，这样恰好能够保证有一定数量的边是长边。