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

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

增强生成 (RAG): 在大模型提示工程中, 对输入提示中提及的实体进行向量搜索, 返回相关实体向量作为提示的一
部分, 以增强大模型的上下文知识, 减少幻觉生成; (2) 多模态检索与推荐: 用户输入如图像等多模态数据后, 系统
检索相似向量 (如图像向量) 并返回相应内容, 用于推荐与相关性排序.
在实践与理论研究中, 已广泛证明“高维诅咒”现象是向量搜索中不可忽视的难题: 在高维空间中, 精确地获
取 K 近邻的唯一可行方式往往是遍历全集, 而这种代价在真实系统中难以接受. 为此, 研究与工程中普遍采用 K
近似近邻 (KANN) 查询, 对精度要求进行松弛, 以换取查询效率. 本文给出 K 近邻查询定义.
定义 1 (K 近邻查询). 设有元素集合 S 和预定义距离函数 D, 给定查询结果集大小 k 的情况下, 输入一个查询
q, K S ⊆ S, |S | = k, s.t. ∀x ∈ S , ∀x ∈ S \S , D(q, x ) ⩽ D(q, x).
′
′
′
′
′
′
元素 近邻查询目标是找到
而 K 近似近邻查询旨在返回尽可能接近真实 K 近邻集合的结果. 其查询精度通常通过“召回率”指标衡量. 召
回率越高, 则认为 K 近似近邻查询结果越精确, 本文给出召回率@k 定义如下.
定义 2 (召回率@k). 设有元素集合 S , 给定一个查询元素 q, 假设 G ⊆ S,|G| = k 且是 q 在 S 中的真实 K 近邻集
合, S 是查询的输出集合, 则召回率@k 定义公式如下:
′

′
|S ∩G|
召回率@k = (1)
k
定义 3 (近似 K 近邻查询). 设有元素集合 S 和预定义距离函数 D, 给定查询结果集大小 k 的情况下, 输入一个
′
查询元素 q, 输出查询集合 S ⊆ S 使得召回率@k 最大化.
本文进一步关注更新场景下的 K 近似近邻查询性能, 沿用 FreshKANNS (fresh K-approximate nearest neighbor
search) 定义 [18] , 给出如下形式化定义.
定义 4 (FreshKANNS) [18] . 设有随时间演化的元素集合 P (在时间 具有状态 ), 目标是在当前数据状态 P t 上
t
P t
构建并维护一个动态索引, 该索引支持以下 3 类操作: (1) 插入新元素; (2) 删除已有元素; (3) 对于查询元素 q, 在当
P t 上执行 K 近似近邻搜索.
前数据状态
2.2 量化压缩
为了减小内存开销并提升距离计算效率, 图结构的磁盘向量索引通常对原始向量进行压缩, 其中量化压缩 [9,38]
是一种常见的压缩方法. 该方法将压缩码与码表加载到内存中, 在查询时以近似方式估算向量间距离.
如图 2 所示, 量化压缩主要流程如下.

原始向量数据 量化压缩 码表
c0:
[2.3, 0.1, 1.6, 4.6, 3.9, 5.8, 7.3, 5.2, 9.8] [7.1, 5.8, 4.3]
c1:
[2.1, 0.7, 1.4, 4.3, 3.7, 5.9, 7.4, 5.1, 9.4] [7.2, 5.3, 4.4]
c2:
[2.4, 0.3, 1.9, 4.5, 3.2, 5.1, 7.7, 5.8, 9.6] [7.6, 5.6, 4.6]

图 2 量化压缩示意图

(1) 分块处理: 将高维向量划分为多个低维子向量块.
(2) K-means 量化: 对每个子块使用 K-means 聚类, 生成对应的聚类中心 (即码表).
(3) 编码表示: 原始子向量以所属簇的中心索引表示, 即构成压缩码.
(4) 码表组合: 多个子块的聚类中心集合经笛卡尔积组合后, 可近似恢复原始向量空间.
简言之, 量化将连续向量空间离散化, 使得任一原始向量可由若干聚类中心近似重构, 从而达到有损压缩目
的. 其核心思想是在每个子向量块中选取代表性点, 再将代表点通过维度组合表示整个高维空间.
在查询阶段, 如图 3 所示, 系统采用 ADC (asymmetric distance computation) 策略, 使用原始查询向量 (图中星
状点) 与向量码表中聚类中心 (图中红点) 间的距离进行近似计算. 由于查询向量是未压缩的, 只需事先计算其与
所有聚类中心的距离, 即可通过查表方式高效获取压缩向量的近似距离, 大幅提升计算速度.