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

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

表 1 实验数据集

数据集 向量维度 向量距离类型 向量类型 向量数量 查询数量
SIFT1M 128 L2 float 1 000 000 10 000
GIST1M 960 L2 float 1 000 000 1 000
DEEP10M 96 L2 float 10 000 000 10 000

● GIST1M [53] 同样为评估大规模 ANNS 性能的图像数据集, 维度更高, 由图像的全局特征描述符生成, 包含
100 万个 960 维向量及 1 000 个查询向量.
[39]
● DEEP10M 是一个规模更大的图像向量数据集. 图像经过 GoogLeNet 模型处理并通过 PCA 降维至 96 维,
最终包含 1 000 万个 96 维向量及 1 万个查询向量.
4.2 评价指标及基准方法
根据 FreshKANN 的定义, 我们采用以下 4 项指标来评估性能: (1) 查询召回率 (Recall), 用于衡量查询精度;
(2) 查询操作 QPS, 每秒完成的查询操作数, 用于反映查询吞吐量; (3) 插入操作 QPS, 每秒完成插入操作数, 用于反
映更新吞吐量; (4) 内存用量变化, 用于评估硬件资源消耗.
本文将所提方法 LSMDiskANN 与当前领先的可更新图结构磁盘向量索引算法 FreshDiskANN (FreshDiskANN
代码仓库: https://github.com/microsoft/DiskANN/tree/diskv2) 进行对比. 两者在公共参数设置上保持一致, 确保实验
公平性. 尽管近期已有针对 FreshDiskANN 的改进工作发表于 arXiv [25,46] , 但由于未开源, 故未纳入对比对象.
4.3 实验设置
本文所有的实验都在同一台配置为 Intel(R) Xeon(R) Platinum 8352V @ 2.10 GHz 的 CPU, 128 GB 的 DDR4
内存和 1 TB 的 SSD 硬盘 (顺序读速度 V r = 567 MB/s, 随机读速度 V s = 390 MB/s) 的服务器上完成.
本文设计了两个对比实验和两个消融分析, 其中对比实验模拟实际应用场景中向量索引的使用情况, 设计了
索引快速膨胀场景和索引稳定更新场景 (代码已发布在 https://github.com/N0ir7/LSMDiskANN).
(1) 实验 1: 索引快速膨胀实验. 首先, 从原始数据集中抽取 10% 数据构建初始索引, 随后经历 100 个迭代轮
次, 数据量膨胀到原始数据集 80% 的数据. 在每个迭代轮次中, 会不断进行插入、查询与必要的合并操作, 并保证
在每个迭代轮次中随机插入原数据集总量 0.7% 的数据.
(2) 实验 2: 索引稳定更新实验. 在实验 1 的索引基础上, 整个索引再经历 100 个迭代轮次. 在每个迭代轮次中,
会不断进行插入、删除、查询与必要的合并操作, 并保证在每个迭代轮次中各随机插入与删除原数据集总量
0.3% 的数据.
消融实验则分别在实验 1 和实验 2 的场景下, 对本文提出的优化策略进行有效性验证.
在本文实验中, 对于相同数据集的不同实验均采用相同的参数. 对于不同方法之间的共有参数, 也采用相同参
数, 并使用 FreshDiskANN 中的默认设置. 表 2 共同实验参数展示了不同方法之间的共用参数, 表 3 展示了
LSMDiskANN 的特有参数.

表 2 共同实验参数

查询线程数 插入线程数 删除线程数 邻居列表长度 R 搜索参数 L s 剪枝系数 α 合并时最小单元大小 (MB)
6 2 1 63 75 1.2 256

表 3 LSMDiskANN 实验参数

内存层 磁盘中间层组件数 磁盘中间层合并 刷新线程检查 合并线程检查 磁盘中间层 动态搜索阈值 重布局阈值
组件数 最大值 组件数阈值 频率 (s) 频率 (s) 搜索参数 L s 0 系数 η 系数 λ
2 5 3 5 20 15 1.6 0.68

取值依据图 8(b) 曲线斜率变化, 在搜索列表长度为 15 时, 曲线斜率达最大值,
说明: 磁盘中间层搜索参数 L s 0
且召回率满足基本要求; 动态搜索阈值系数参考 SPANN [11] 进行设置; 重布局阈值系数 λ 由公式 (6) 确定.