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

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

果, 将其分为面向硬件加速的方法、面向学习增强的方法、面向距离比较操作的方法、面向磁盘内存混合的方法、
面向数据访问优化的方法、面向分布式的方法、面向混合搜索的优化方法以及理论分析研究.
本文介绍了向量近似最近邻的背景和基本概念, 包括近似最近邻搜索的定义、数据类型和相似度函数; 根据
向量数据索引组织方式并结合最新的工作来介绍不同的向量搜索方案; 进一步总结最新的向量搜索优化方法成果;
基于当前近似最近邻搜索的研究, 展望未来的发展方向.

1 向量近似最近邻搜索的基本概念

本节主要介绍向量近似最近邻搜索的基本概念, 主要从 3 个方面进行: 问题定义、数据类型和相似度度量方法.
1.1 问题定义
向量 K 近邻搜索是在给定向量集合中, 根据特定的相似度度量标准, 获取与查询向量最相似的 k 个向量的过
程, 其具体的问题定义如下.
定义 1 (K 近邻搜索). 给定一个数据集 P, 其中的每个点 p ∈ R 为 d d 维实数向量, 查询点 q ∈ R 为同维向量, 定
d
′
义距离函数 δ(p,q) 衡量两个点之间的距离, 从数据集 P 中找出一个子集 K ⊂ P, 满足 |K| = k, 并且 ∀p ∈ P\K, 有
δ(p ,q) ⩾ max p∈K δ(p,q).
′
由于维度灾难问题 [9] , 寻找 K 近邻十分困难, 采用近似最近邻搜索的方式以放宽对结果的要求, 从而提高搜索
效率.
定义 2 ( (ε,k) -近似最近邻搜索). 给定 ε > 0, 给定数据集 P 和查询点 q, 让 r 是数据集 P 中距离查询 q 第 i 近
∗
i
的点, 从数据集 P 中返回 k 个点 r i ∈ P, 对每个点 , 满足 δ(r i ,q) ⩽ (1+ε)δ(r ,q).
∗
r i
i
ε 的要求, 而是利用召回率来衡量检索结果的准确度 [17] , 其定
在实践中向量数据库进行搜索时, 并不要求满足
义如下:

|R o ∩R k |
Recall(R o ) = ,
|R k |
其中, |·| 表示集合中元素的数量, R o 表示搜索结果, R k 表示最近的 k 个邻居节点 (ground truth). 同时, 通过 Recall-
QPS 曲线来衡量不同方法的搜索性能, 不同方法之间比较相同召回率下 QPS (query per second) 的高低, 或者比较
同样的 QPS 下召回率的高低.
1.2 数据类型
依据不同的检索模型以及应用场景, 会产生不同种类的向量类型, 主要包括稠密向量、稀疏向量以及二值向
量, 向量数据库支持多种数据类型以适应不同的检索需求, 表 1 总结了主要数据类型的特征与应用场景.

表 1 不同的数据类型比较

数据类型 特征 来源 典型应用 优点 缺点
768维BERT [18] 、 自然语言处理 [20] 、 语义表达能力强, 捕
稠密向量 连续浮点数, 高维 [19] 空间占用大
1 536维OpenAI 推荐系统 捉细微差别
词袋模型 [21] 、 可解释性好, 存储效
稀疏向量 高维但大部分为0 [22] 文本检索 语义表达相对较弱
SPLADE 率高
计算快速, 极省空间
二值向量 每维度0或1 图片哈希 [23] 跨模态检索 [24] 信息损失大, 召回率低
(1 bit/维)
关键词、标量等结构 对目标的结构化 混合查询、精细 补充向量表达, 提高
属性数据 需要额外维护
化数据 [1] 数据描述等 化检索 检索精度

(1) 稠密向量通过连续的浮点数表示, 能够编码丰富的语义信息, 在深度学习模型中广泛应用, 但高维度和浮
点表示导致存储开销较大. (2) 稀疏向量虽然维度可达上万, 但通过仅存储非零值实现高效存储, 它具有良好的可
解释性, 常见于词袋模型, 基于神经网络的 SPLADE 模型 [22] 结合了传统的稀疏检索 (BM25 [25] ) 以及稠密检索的优
点, 在保持可解释性的同时增强了语义表示. (3) 二值向量的每个维度是一个比特位, 取值 0 或 1, 来源于神经网络