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

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

FreshDiskANN LSMDiskANN
1 600 600 98.4
1 400 550 98.2 8
98.0
QPS 1 200 QPS 500 Recall@5 97.8 Memory (GB) 6
450
1 000
400 97.6 4
800 97.4
350 2
600 97.2
0 25 50 75 100 0 25 50 75 100 0 25 50 75 100 0 25 50 75 100
Iterations Iterations Iterations Iterations
(a) Insert throughput (b) Query throughput (c) Query accuracy (d) Memory usage
26 30.0 40 250
Latency (ms) 24 Latency (ms) 27.5 Latency (ms) 30 Latency (ms) 200
35
25.0
22
20
22.5
150
18
20.0
25
16
14 17.5 20 100
15.0
50
12 12.5 15
0 25 50 75 100 0 25 50 75 100 0 25 50 75 100 0 25 50 75 100
Iterations Iterations Iterations Iterations
(e) Query P90 latency (f) Query P95 latency (g) Query P99 latency (h) Query P99.9 latency
图 15 DEEP10M 数据集下索引稳定更新实验总体表现

● Q4: LSMDiskANN 是否可以获得与 FreshDiskANN 相当的召回率?
在两个实验中, LSMDiskANN 与 FreshDiskANN 的召回率总体相当且均处于高位, 差异处于可接受范围内. 在
索引快速膨胀实验中 (如图 10–图 12 所示), 考虑到插入数据的随机性, 二者的召回率均在合理的范围内波动; 在
索引稳定更新实验中 (如图 13–图 15 所示), 虽然 LSMDiskANN 在实验后期的查询召回率略低于 FreshDiskANN,
但是都处在一个高位召回率水平; 图 14、图 15 显示, LSMDiskANN 与 FreshDiskANN 的平均召回率基本一致, 但
是 LSMDiskANN 的波动范围略大一些.
每当新鲜数据插入到上层索引时, 由于冗余查询的存在, 此时召回率会不断上升; 每当数据从上层索引往下层
索引进行传递时, 都不可避免地导致召回率的陡然下降, 从而出现召回率波动的现象. 同时, 由于 FreshDiskANN
本身合并操作算法的两点缺陷, 导致 LSMDiskANN 召回率的下降与波动现象更加明显.
(1) 在合并操作后, 不会调整对应量化压缩中聚类中心的分布, 从而弱化了量化压缩反映真实向量数据分布的
特性, 并注定了磁盘向量索引在不断合并过程中召回率的下降趋势. 这一点在 GIST 数据集上尤为明显, 这是因为
GIST 数据集中向量维度更高, 其量化压缩反映真实向量数据分布的抗干扰性更弱, 进而加剧其召回率劣化速度.
因此, 无论如何调整插入算法, 当插入量积累足够多后, 必须通过重建或者调整量化表来维持高位召回率.
(2) 在合并操作插入阶段时, 所有插入点之间没有连边机制, 因此同一批插入点之间是不能互连的, 从而导致
图连通性下降, 但是在下一批次合并操作时, 新批次插入点会成为上一轮批次插入点之间的桥, 从而可能使得图连
通性有所弥补, 并出现图 14 中合并操作后的召回率有所回升的现象. 因此, 插入点批次量越大, 图质量下降幅度就
越大. 由于 LSMDiskANN 每次合并操作数据量的增大, 进一步加剧了图劣化速度, 从而导致如图 14、图 15 中更
大的波动范围.
总的来说, 相比于 FreshDiskANN, LSMDiskANN 的召回率波动均在可容忍的范围内, 关于合并操作插入算法
的改进, 本文将其留作一个未来工作.
● Q5: LSMDiskANN 是否可以获得比 FreshDiskANN 更低的内存占用?
从图 10–图 15 的内存占用变化来看, 结论是否定的. 不可否认的事实是, LSMDiskANN 由于引入了磁盘中间
层, 需要维护更多的磁盘层索引组件, 进而带来更多的量化压缩对应的码表, 内存开销必然有所增加. 但更多的内
存开销源于磁盘索引组件之间的数据冗余.
由于 FreshDiskANN 原本并未考虑在单个系统中集成多个磁盘索引组件, 因此在现有磁盘索引实现中, 均保