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

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

间中, 实现欧氏空间的 LSH 函数的设计. 后续有一系列工作提出更多的优化方案, 如经典的 QALSH 方案 [31] .
QALSH 的目标是解决哈希桶划分的问题 [31] . 在此前的工作如 C2LSH [70] 中, 需要预先划分哈希桶, 这种方式可
能导致距离查询较近的数据点被划分到不同的桶中, 影响搜索效率. QALSH 提出以查询对象为锚点, 根据到查询
点的距离信息来划分哈希桶. 图 4 展示了两种划分策略的区别, QALSH 可以更加高效而灵活地划分数据.
QALSH 进一步提出了虚拟重哈希 (virtual rehashing) 技术, 以动态地设置哈希桶的范围, 避免重建哈希表. 具体来
说, QALSH 是将数据点通过多个哈希函数映射为多个一维数据点并存储于若干 B+树中, 然后在 B+树的叶子节点
中进行线性搜索, 以扫描更多的哈希桶, 从而找到近似最近邻点, 当检查的点的数量超过预设值时停止搜索.

q q
o 1 o 2 o 1 o 2

→ →
a
a
0 h(o 1 ) h(q) h(o 2 ) 0 h(o 1 ) h(q) h(o 2 )
w w/2 w/2
(a) C2LSH (b) QALSH
图 4 C2LSH [69] 和 QALSH [70] 投影示例

此外, SOSIA [71] 研究利用哈希来加速稀疏向量的近似最大内积搜索问题. SOSIA 首先将稀疏向量数据转化为
二进制向量并视为集合, 随后通过多个不同的局部敏感哈希函数将其映射到哈希桶中. 对于查询向量, 首先将其转
化为二进制向量, 再根据 Jaccard 距离进行搜索. FARGO [72] 通过设计一种全局多次探测 (global multi-probing,
GMP) 策略, 利用内积的性质筛选高质量的候选项, 通过将点随机映射到两个不同方向的 RXT 变换来减少数据不
均衡分布, 结合自适应的终止条件以进一步提高搜索效率. 文献 [68] 对更多局部敏感哈希的相关工作进行了综述.
2.3.2 学习型哈希
学习型哈希通过学习一个映射函数, 将数据点编码为二进制形式, 从而能够在汉明空间中进行高效近邻搜索,
在保证检索性能的同时尽可能接近真实查询结果. 学习型哈希的关键在于如何设计映射函数, 使得相似的数据点
在映射后具有相似的哈希值, 更多的哈希函数族可以参考文献 [13,14] 中的介绍. 在学习哈希函数之后, 会对数据
进行哈希编码, 编码完成之后需要在学习到的哈希编码上进行搜索操作, 主要分为两类: 基于线性扫描的搜索方法
(Hamming ranking) 和基于哈希码索引的搜索方法 [13,14] . 前者通过计算查询点的哈希码和所有数据点的哈希码之
间的汉明距离, 然后保留距离最小的前 L 个数据点作为近似最近邻点. 后者则是通过索引结构来加速搜索过程, 由
于是二进制编码, 因此可以直接进行哈希表查找, 这也是一种倒排表. 但是实际中编码往往很长, 导致哈希表的存
储开销很大, 因此需要进一步设计基于倒排的方式对哈希码进行索引, 搜索过程是将查询点的哈希码按照倒排建
立的情况进行分割, 然后在每个分割的哈希码上进行倒排表的查找, 最后将所有的结果进行合并来得到最终的近
似最近邻点.
经典的方案是文献 [73] 提出的基于鸽巢原理的方案, 将两个二进制编码 h 和 g 分成 m 个子串, 如果两个点之

间的汉明距离 ∥h−g∥ H < r, 那么必然有一个子串的汉明距离小于等于 ⌊r/m⌋, 基于此, 只需要在所有的子串上执行
⌊r/m⌋ 的搜索操作即可. 该方案将二进制编码分为 m 个不相交的子串, 针对每个子串建立一个哈希
半径小于等于
表, 查询时, 同样将查询点的哈希码分为 m 个子串, 然后在每个子串上进行哈希表的查找, 最后将所有结果进行合
并, 计算精确的汉明距离, 最终返回汉明距离满足要求的数据. 在采用前述方式之前需要检查的桶的数量为:

r ∑
k
L(b,r) = C ,
b
k=0
优化之后变为 m· L(b/m,⌊r/m⌋). 这种方式减少了空桶的数量, 也就是减少了需要维护的哈希桶的数量, 从而降低
了内存需求.
GPH 方法 [32] 进一步优化了利用鸽巢原理在汉明空间进行检索的性能. 针对当前方法基于等长的空间划分和
固定阈值分配导致生成不必要候选集的问题, GPH 提出了一种新形式的鸽巢原理. 它允许变长的子空间划分和不