Page 28 - 《软件学报》2026年第3期

宋子文 等: 向量数据库中近似最近邻搜索关键技术综述 991

利用 PCA (principal component analysis) 投影, 以最小化近似距离和真实距离的误差, 然后利用基于标准差的方式
进行距离校正, 最后提出一个利用线性模型从数据中学习到的更通用的距离校正方法. 实验结果显示, 与
ADSampling 相比, DDC 实现了 1.6–2.1 倍的性能提升. DADE [140] 提出了一个基于数据分布的距离估计方法, 从理
论上证明了 DADE 的距离估计在数据分布上是无偏的. DADE 利用主成分分析获得的矩阵对数据进行正交变换,
实验结果显示其效果优于 ADSampling.

... ... ...
x 1 x 2 x 3 ... x i−1 x i x D x 1 x 2 x 3 ... x i−1 x i x D x 1 x 2 x 3 ... x i−1 x i x D
继续计算 停止计算

... ... ...
q 1 q 2 q 3 ... q i−1 q i q D q 1 q 2 q 3 ... q i−1 q i q D q 1 q 2 q 3 ... q i−1 q i q D

部分距离 dis i−1 ≤τ 部分距离 dis i >τ 部分距离 dis i >τ 不需要计算

图 9 DCO 时提前终止距离计算

表 8 展示了 ADSampling、DADE 和 DDC 在 3 个数据集下进行 Top20 查询时分别在 96% 和 98% 召回率下
的搜索性能 (QPS) 对比, “－”代表默认参数下无法达到对应的召回率, 从结果中可以看到, 不同方法在不同数据集
上的性能表现不同, 比如, 在 DEEP 数据集上, DDC 方法能够取得更好的效果, 而在 MSong 数据集上, ADSampling
效果更好. 在实际使用中需要根据数据集来选择合适的方法, 以取得更好的效果.

表 8 采用提前终止距离计算的 ADSampling、DADE 和 DDC 的搜索性能 (QPS) 对比

96%召回率 98%召回率
优化方法
DEEP GIST MSong DEEP GIST MSong
ADSampling 728 209 1 972 520 138 1 492
DDC 1 329 281 1 183 915 192 －
DADE 1 215 208 1 650 844 185 931

FINGER [141] 同样是一个优化距离比较操作的方法. 它不是通过提前终止距离计算, 而是通过估计残差向量之
间的角度来近似距离函数, 从而跳过对一些点的距离计算. 在此基础上, 它利用改进的局部敏感哈希方法来降低计
算成本, 相较于 ADSampling 方法, 需要更多的存储代价. 实验结果显示, FINGER 在搜索上相较于 HNSW 提升了
最多 60% 的性能. PEOs [106] 提出了概率路由的概念, 为搜索中探索邻居节点提供概率保证, 从而高效选择需要精确
距离计算的邻居节点. 它利用空间划分和随机投影技术来估计邻居节点和查询向量的角度, 然后根据估计的角度
来选择需要精确计算距离的邻居节点. 与 FINGER 相比, PEOs 显著减少了额外的存储代价, 在 GIST 数据集上由
6.12 GB 降低到 4.64 GB, 实验结果显示其性能相比于 FINGER 提升了最多 1.4 倍.
3.4 面向磁盘内存混合场景的优化
磁盘内存混合场景是指系统可用物理内存容量不足以直接存储全部待处理数据, 或内存使用成本过高迫使必
须采用混合存储策略的计算环境. 此类场景常见于超大规模数据应用 (如 10 亿级向量检索), 其核心矛盾在于内存
容量与数据规模的不匹配性. 高维向量数据每一条数据包含成百上千标量数据, 存储 1 000 万条 128 维的 float 类
型向量需要 4.7 GB 的空间, 建立的索引还会引入额外的空间占用, 在实际中需要处理更大规模的数据, 全部依赖
内存将带来极大的成本开销, 此时无法采用传统内存索引. 因此, 基于磁盘内存混合的近似最近邻算法被提出来,
以降低对内存容量的需求.
3.4.1 基于倒排的方法
SPANN [107] 是面向内存受限场景的高效近似最近邻搜索系统. 该系统基于倒排索引框架构建了一种内存-磁盘