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

984 软件学报 2026 年第 37 卷第 3 期

加速比. 实验结果表明, 该方法在保持 99% 搜索精度的同时, 10 亿级数据集查询吞吐量相比于现有最优方案提升
20.7 倍, 内存消耗减少至 1/3. 其创新之处在于, 首次实现压缩编码与图索引的端到端协同优化, 显著超越传统量化
方法与图搜索框架的组合方案, 为基于大语言模型的检索增强系统提供了可扩展的底层支持. 此外, DiskANN 同
样是一个基于图和量化的索引结构. 它是一个基于磁盘和内存混合的索引方式, 充分利用 SSD 的能力来提高单机
处理能力, 在第 3 节会进行更多的介绍.
2.5.2 基于图和树的组织方法
针对基于树的方法在搜索上效率不足以及图方法会陷入局部最优的问题, 文献 [37] 提出了基于树和图结合
的搜索策略, 将经典的 K-NN 图 [42] 和分区树 [30] 相结合, 采用查询驱动的迭代搜索策略, 不断地扩展搜索范围, 最终
获得搜索结果. 其搜索主要分为 4 个步骤: (1) 通过搜索树确定初始的搜索结果; (2) 在上一步基础上对局部的图做
进一步搜索; (3) 根据搜索历史在树上搜索, 确定在图上搜索的新位置; (4) 在图上进一步进行搜索. 其核心思想是
通过迭代的邻域扩展, 逐步逼近真实最近邻. 该方法结合了图结构与搜索策略的优势, 为基于图和树混合的组织方
法提供了重要参考. 实验展示出该方法相对于图方法取得了非常好的性能提升, 为后续基于图的方法的发展提供
了重要的依据. ELPIS [91] 是一个基于图和树的方法. 它首先通过 Hercules [92] 将数据集划分为若干个聚类, 每个叶子
节点对应一个聚类; 随后并行地在叶子节点上构建 HNSW 图索引. Hercules 通过 EAPCA [93] 摘要进行裁剪来加速
树上搜索过程.
2.5.3 基于图和哈希的组织方法
针对图方法构建成本高和局部敏感哈希查询效率低的问题, 文献 [38] 提出了结合 LSH 和图方法的 LSH-
APG 混合索引方法. 在构建时对数据集中的每个点, 通过 LSH 索引快速找到邻居候选节点, 然后根据邻居节点的
选择规则构建邻居, 如果邻居数量超过预先定义的上限, 则删除最远的点. 通过 LSH 框架加速邻居的搜索, 避免了
传统图方法的高计算成本. 在搜索时, 给定查询点 q 后通过 LSH 找到入口点, 从而降低搜索的半径, 并在检查邻居
节点时通过访问 LSH 结构过滤距离 q 较远的点, 检索距离计算. LSH-APG 通过 LSH 加速构建和动态剪枝优化,
在保证查询质量的同时, 与 HNSW 等图方法相比, 显著降低了构建时间.
2.5.4 基于倒排和量化的组织方法
IVFADC [39] 是一种结合倒排与非对称距离计算 (asymmetric distance computation, ADC) 的方法. 在预处理阶
段, IVFADC 将 N 条向量数据 X = [x 1 ,x 2 ,...,x N ] 划分为 J 组 X = ∪ X j . 每一组向量 X j 记录一个代表向量 C j . 对每
J
j=1
一组向量 X j , 计算其中的每一条向量 x ∈ X j 与该组代表向量的残差向量 x−C j , 并记录残差向量的乘积量化编码.
对于一条查询向量 y, IVFADC 会先对其进行粗糙量化 (coarse-quantization), 选择与 y 距离最近的 C j 并计算残差
y−C j . 随后 IVF x−C j 的非对称距离更新搜索结
向量 进行距离估计, 通过计算残差向量 y−C j 与乘积量化后的
果. IVFOADC+G+P 希望能将每个倒排索引管理的区域划分成更小的子区域, 但存储全部子区域对应的子质心会
导致码本占用过多的空间. 基于这个目标, IVFOADC+G+P 通过分组方法, 由区域质心和其邻近质心的凸组合来构
造子质心以减少内存开销. 此外, 文献 [34] 提出了 RaBitQ, 并将其应用到 IVF 索引结构上, 取得了比倒排加乘积量
化高的搜索性能.
IMI (inverted multi-index) [94] 将空间划分为两个子空间的笛卡尔积 (等同于在乘积量化中将空间划分为 m=2 个
2
子空间), 并为两个子空间分别维护码本, 根据两个大小为 K 的码本, 将空间实质划分为了 K 个区域并在每个区域
内使用乘积量化编码残差向量. 由于 IMI 对空间进行了更细粒度的划分, 每个区域内含有的向量数量较少, 缩减了
搜索空间以提升效率. IMI 方法在大规模数据检索上取得了很好的效果, 但是文献 [95] 指出 IMI 方法会导致很多
空区域导致性能问题, 其提出一个内存高效的数据分组方法来设计基于倒排的高维向量检索系统, 在 10 亿级的
SIFT 和 DEEP 数据集上取得了更优的效果.
2.5.5 基于哈希和树的组织方法
此类方法用树结构组织 LSH 投影后的数据. 如 C2LSH [69] 、QALSH [70] 、R2LSH [96] 利用 B+树来组织数据点哈
希后的结果; SRS [40] 可将数据投影到多维度空间, 因此采用 R 树来组织数据. 文献 [97] 提出 LSB-tree 以实现快速