随机映射降维加速 ANN 距离计算｜向量检索论文分享

向量检索实验室 2024-07-30

457

今天为大家分享一篇SIGMOD 2023年的向量检索论文：

High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations

基于可靠高效的距离计算算子的高维向量近似最近邻检索

论文概述

目前，深度神经网络输出的嵌入向量的维数正在快速增长。比如，在自然语言领域，SalesForce公司最近发布的SFR-Embedding-2模型的输出向量维数是4096，阿里巴巴的gte-Qwen2-7B-instruct模型则输出3584维向量。

相比于低维向量，高维向量有更广泛的语义表示空间，可以提高文本表示的精确性。然而，这也给后续的向量检索带来了更大的压力。在向量相似性检索索引中，查询时间的主要瓶颈是向量间的距离计算（占总时间80%以上），而距离计算的复杂度和向量维数成正比。向量维数的提高意味着查询代价的线性增长。

针对这个问题，本篇论文提出基于低维计算估计高维向量精确距离的算法ADSampling，降低距离计算代价；同时针对两种主流的向量索引：IVF和HNSW进行改造。结果显示，ADSampling可以减少HNSW查询中至多75%，IVF中至多89%的距离计算代价。

论文地址：https://arxiv.org/pdf/2303.09855

代码地址：https://github.com/gaoj0017/ADSampling

关键算法

基于随机映射的向量间距离估计

为实现在低维空间中对高维向量间的距离进行估计，核心挑战是在尽量小的精度损失前提下，尽可能多的降低维度以节省计算开销。

本文采用了随机映射的方法：给定一个维向量，一个正交的随机矩阵，则降维后的向量为维向量，且存在理论保证:

简而言之，随机映射方法可以在低维空间中通过简单数学变换反映高维向量间距离，且维数越接近原始向量，精度损失越小。

自适应维数选择

在具备降维计算的能力之后，第二个问题是将高维向量降低至多少维可以保证有限的精度损失。显然，给定精度损失上限，在不同的查询向量上，不同的数据集向量，应该有不同的维度。因此，本文选择使用动态自适应的方法决定降维维度。

在构建索引时，首先将原始数据按照相等维度进行映射，此时向量间距离不变。在查询时，逐段计算向量与查询向量的距离（L2/内积等距离可以累积计算），并进行估计。若满足条件，则停止计算；否则继续计算下一段的距离。在最差情况下，即所有维度全部计算，得到最终结果。

与ANN算法的融合

在HNSW/IVF等ANN算法中，会在查询过程中维护一个堆结构代表当前找到的最优结果（Best-so-far answer, BSF），若当前访问向量比BSF距离查询向量更近，则更新堆，否则丢弃当前向量。因此，估算的向量距离可以用于剪枝。若估算距离已经比BSF距离更远，则停止计算；否则计算真实距离更新堆。这样，最终返回的kNN结果的距离是真实的。