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

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

写时复制技术实现秒级数据回滚. 实验结果表明, 在处理 10 亿级 SIFT 数据集时, SPFresh 在 15 核单 NVMe SSD
环境下同时支撑 4k QPS 搜索吞吐和 2k QPS 更新吞吐. 相较于仅支持追加更新的 SPANN+, 其查询准确率提升超
过 15 个百分点且尾部延迟稳定在 4 ms 左右, 验证了动态再平衡机制对索引质量的持续维护能力.

B B B
合并 A 1 A 2 分裂
A 2
A 2
A A 1
A 1
(a) 合并操作 (b) 分裂操作

B B B
A 2
分裂 重新分配

A 2
A 1
A A 1
(c) 重分配
图 3 SPFresh 的基本更新操作 [67]

2.3 基于哈希的数据组织方法
基于哈希的方法是一种高效的索引组织方法. 它将数据点映射到一个低维空间中或者由一系列比特组成的二
进制编码中成为哈希码, 从而可以通过哈希值来快速定位数据点. 基于哈希的索引组织方法主要分为两类: 局部敏
感哈希 (locality sensitive hashing, LSH) 和学习型哈希 (learning to hash). LSH 通过随机投影等方式将相似的数据点
映射到相同的桶中来实现近似最近邻搜索. LSH 一般是与数据无关的. 学习型哈希则是将数据点映射到一个二进
制编码中, 从而可以通过汉明距离来计算相似度. 它考虑了数据分布的特点. 本文依据其哈希后的结果是二进制形
式而称学习型哈希为二进制哈希. 关于哈希的相关工作在综述文献 [13,14,68] 中有详细的介绍. 在此, 我们从局部
敏感哈希和学习型哈希两个方面进行简要介绍, 主要介绍在利用哈希函数对数据进行哈希之后如何进行组织检
索, 更多更详细的介绍可以参考相关的综述.
2.3.1 局部敏感哈希
局部敏感哈希在文献 [9] 中被首次提出, 此后一系列以此为基础的研究工作取得了更好的搜索性能. 在
LSH 中, (r 1 , r 2 , p 1 , p 2 )-敏感哈希函数是其中的关键. 要找到一个哈希函数族满足如下的性质.
定义 3 (局部敏感哈希函数) [69] . 一个哈希函数族 H 被称为 (r 1 , r 2 , p 1 , p 2 )-敏感 (其中, r 1 <r 2 p 1 >p 2 ), 如果对于任
,
意两个数据点 x 和 y, 满足以下条件.
(1) 如果 d(x,y) ⩽ r 1 (即两点距离不超过 ), 则它们被哈希到同一桶的概率至少为 p 1 :
r 1

Pr [h(x) = h(y)] ⩾ p 1 .
h∈H
(2) 如果 p 2 :
r 2
d(x,y) ⩾ r 2 (即两点距离至少为 ), 则它们被哈希到同一桶的概率最多为
Pr [h(x) = h(y)] ⩽ p 2 .
h∈H
一个经典的方法是基于 p-stable 分布来设计 LSH 函数族. 其定义如下.
定义 4 (p-stable 分布) [69] . 一个分布 D 被称为 p-stable (其中 p ⩾ 0), 如果对于任意 n 个实数 v 1 ,v 2 ,...,v n 以及独
n ∑
立同分布 (independent and identically distributed, i.i.d.) 的随机变量 X 1 ,X 2 ,...,X n ∼ D, 随机变量 v i X i 的分布等同
i=1
 n  1/p
∑ 
  p 
于   |v i |   · X, 其中 X ∼ D.
 
i=1
高斯分布是一个 p-stable 分布. 文献 [69] 中提出利用高斯分布设计随机投影向量, 将高维数据映射到低维空