以阿里云OpenSearch为例谈向量检索技术选型

可见，召回率越高，结果就越精确。当时，算法就精确地找到了全部最近邻；当时，算法则没有找到任何最近邻。实际计算中一般有。召回率刻画了 ANN 搜索的精度，而检索的速度则由吞吐或延迟来衡量，延迟指的是给定S 后对某个q 进行一次 ANN 搜索的耗时，而吞吐则指的是给定S 后在单位时间内可以处理多少次 ANN 搜索，一般使用每秒检索数 (Queries Per Second, QPS) 来衡量。在 ANN 搜索中，我们希望能以尽可能少的时间和硬件资源，构建尽可能小的索引，同时在检索时能以尽可能少的硬件资源达到尽可能高的精度和速度。

基于树的方法

基于聚类的方法

基于量化的方法

基于哈希的方法

基于图的方法

基于图的方法最常用的是HNSW (Hierarchical Navigable Small World)，几乎所有的向量检索产品都实现了 HNSW，阿里云OpenSearch的图算法也是基于HNSW实现的，并在HNSW基础上进行了优化。HNSW 是一种分层小世界图的检索方法，上层小世界图可以看成是下层图的缩放。多层图的方式目的是为了减少搜索时距离计算和比较的次数，类似于跳表查找。检索时，从最高一层（即最稀疏的一层）开始，每一层得到的检索结果再作为下一层的输入，如此，不断迭代到最后一层。最后得到查询点的 K 个近邻。HNSW 本身基于另一种图索引 NSW (Navigable Small World)，同时借用了跳表的思想，将图分层来加速检索，从而能在较高召回率的同时保持较高的性能。不同于大部分其他图索引，在 HNSW 中存在m 张图，而非只有一张图。这m 张图从低到高形成了层次结构，如下图所示。从最低层（第0层）到最高层（第m-1 层），层越高，其中的节点越少；层越低，其中的节点越多，并且高层的节点总会出现在低层中，而第层则包含了索引中所有的节点。在检索时，算法首先从第m-1 层开始，选取一个起始点开始游走，开始查找层中距离查询向量q 最近的节点。接下来，以找到的最近节点作为新的起始点，在第m-2 层查找距离q 最近的节点。如此直到在第0层中完成查找。由于高层的节点稀疏，节点间的距离远，游走时能很快地达到q 附近。而低层中包含更多的节点，具有较完整的邻接关系，通过在低层的游走又能精确地找到q 的 top k的结果。因此 HNSW 得以在召回率和吞吐上均达到良好的性能。

包括HNSW算法在内的大部分knn算法的性能开销都集中在距离计算操作(distance comparison operations aka DCOs)上, DCO操作的计算复杂度是O(D)的,其中D是向量维度。而AKNN算法中的大部分距离比较操作都可以抽象为的形式，其中query为查询向量，object是当前的比较对象，r是一距离范数的阈值，函数的返回值表示当前query和oject的距离是否大于r，注意到这个过程中其实并不需要计算query和object的精确距离作为返回值，我们只需要知道和r的大小关系。如果把查询流程中的耗时做细分，把DCOs计算结果为小于阈值r的计算成为postitive DCO, 否则为negative DCO，那么如下图所示其实大部分cpu时间都花费在了计算negative DCO上。

数据集		ef 参数	召回率	有效距离计算占比
gist	10	100	95.9%	58.8%
	10	400	99.5%	31.4%
	100	200	96.7%	89.8%
	100	250	97.9%	89.7%
sift	10	50	98.4%	49.8%
	10	75	99.3%	39.7%
	100	125	98.5%	83.9%
	100	200	99.6%	71.3%
拍立淘	10	100	98.8%	26.9%
	10	200	99.3%	16.6%
	100	200	95.4%	72.1%
	100	500	98.4%	51.0%

从表 1 可以看到，在各种数据集的场景下，HNSW 的检索都存在不必要的计算，部分场景的有效计算甚至不到总计算量的 20%。倘若可以在检索时进行判断，提前终止游走，就可以节省这部分距离计算，从而在不影响召回率的情况下提升 qps。

• 构建阶段的优化：优化图结构，使图的出度入度更加合理，更利于 ANN 搜索；

• 检索阶段的优化：减少距离计算操作的开销，以及预测检索游走时所需的总步数，当到达预期步数时可以提前终止检索，以减少计算开销。

如图所示，在这一次 ANN 搜索的游走中，第 37 步左右就已经得到了最终的查询结果。如果可以提前预知这一点，直接在第 37 步终止，就可以节省大量的计算。这与上文的分析是一致的。直观上看，cur_dist 的下降意味着发现了距离q更近的节点，以此进一步查找更有可能找到实际的最近邻；而cur_dist 的上升则意味着没有发现这样的节点，只能进行回溯从次近的节点进行搜索。图中可以看到，cur_dist 的变化大体呈现为“U 形”的变化趋势。由于初始的游走中会发现大量距离q更近的节点，在游走过程中 cur_dist 首先下降 (0-10 步) 。在此之后，搜索中发现新的近邻节点的概率更小，因此游走开始远离q，cur_dist 开始上升 (10 步后) 。基于这一观察，要判断搜索是否应该终止，应当首先判断游走是否已经进入第二阶段，开始远离q。我们将作为游走进入第二阶段的判据。当然，进入了第二阶段并不足以终止检索，算法实际上应当在最后一次更新R后才停止。也就是说，假如算法预测在剩余的检索步骤中R 将不再更新，算法就应当终止了。用检索中的距离来描述这一点，就是在剩余的游走中始终成立。在第二阶段的检索过程中，top_k_dist 一般比较稳定，但 cur_dist 波动较大，不容易估计。我们可以将每一轮游走的 cur_dist 视为一个随机变量。这样整个游走就可以看作一个随机过程。如果把每一次找到新的近邻节点视为一次事件，那么每一次事件就对应了一次 cur_dist 的下降。这样，没找到新近邻时的回溯就对应了 cur_dist 的一段上升区间。假设事件之间是无记忆的，那么时间发生的次数就可以通过泊松过程来进行建模。利用泊松过程的性质以及实验测试，我们发现事件间的时间间隔以及每次事件 cur_dist 的下降值都是大体服从指数分布的。只要利用这一概率分布，就可以计算剩余游走中更新R 的概率。下图给出了建模方法的一个图示。

仅仅知道随机变量服从指数分布是不够的，我们还需要估计具体的分布参数。这可以通过最大似然估计实现。首先，指数分布的概率密度函数与累计分布函数如下所示：

那么对于指数分布的个样本，就可以得到相应的似然函数

对求导可以得到

因此利用样本均值的倒数就可以估计指数分布的参数。

现在我们来计算剩余游走中R 的更新概率。首先，注意到 ef 参数很大程度上决定了检索中的总步数，以此为依据即可在游走过程中估计剩余游走的最大步数，下面记为t。而利用泊松过程，则可得到在长度为的时间段中发生i 次事件的概率为

记，从上面的分析中可以看到，如果在接下来的步中都始终大于0，R 将不再更新，搜索就可以终止了。记 cur_dist 下降值随机变量为，泊松过程的参数为，那么R 不再更新的概率为

对于指数分布，有。记 cur_dist 下降值指数分布的参数为，就有

利用即可在每一步都对的更新概率进行预测，当以很高的概率不再更新，检索就可以终止了。

随机矩阵投影是一种通用常见的对高维向量进行降维的手段，根据Johnson–Lindenstrauss lemma一个D维向量在经过一个高斯随机矩阵映射被投影到一个更小的d维空间后，依然能以一定概率保持它的欧几里德范数，这意味如果向量x y在原空间的距离信息会在一定程度上被保留在新空间上。所以我们可以先对两个高维向量query object进行随机矩阵映射降维后在对其计算距离，这样可以大大减少DCO的计算量。

假设我们有两个随机正交矩阵P和P'且。

那么直接计算和 计算再取前d维得到的向量是同分布的，因为:

。

针对每次比较，可以采用统计学中假设检验的方法来判断当前的d取值是否适合，如果不适合，就继续增大d直到d等于D。

1. 虚无假设H0 : 当前真实距离。

2. 对立假设。

3. 取显著值p为, 其中c0是常量，而是一个调出来的经验值。

4. 假设H0成立，这样根据Johnson–Lindenstrauss lemma 事件的概率一定小于显著值p。

5. 我们检测 事件 𝑑𝑖𝑠′ > (1 + 𝜖0/ 𝑑) · 𝑟 是否发生，如果发生那么H0不成立，及对立假设成立，反之亦然。

可以看出随着d的增大近似距离dis'会逐渐更加精确，那么对于的object会更容易被假设检验识别出来，而且真实距离dis越大的object越容易在更小的d维度就被假设检验识别出来（占大多数的negative DCO），从而大大节省计算量。

(a). gist，top 10

(b). sift，top 100

• 在 gist 数据集上，召回率由 99.53% 变为 99.51% 时，qps 由 125.11 上升为 240.61，提升 92.3%；

• 在 sift 数据集上，召回率为 99.88% 时，qps 由 670.40 上升为 814.80，提升 21.5%；

• 在拍立淘数据集上，召回率由 99.20% 变为 99.19% 时，qps 由 80.42 上升为 139.72，提升 73.7%。

阿里云OpenSearch vs. Milvus vs. ElasticSearch