Page 15 - 《软件学报》2026年第3期
P. 15

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


                 对实时数据更新场景, 导致工业界依赖定期全量重建索引                   [49] 的高成本方案. 现有动态索引方案存在内存消耗大、
                 查询延迟高等缺陷, 而量化方法          [15] 虽然降低了内存需求却牺牲了召回精度. 针对这一挑战, FreshDiskANN             [49] 通过
                 设计更新图的算法与分层存储架构, 在单机上实现                 10  亿级数据集的毫秒级实时更新与搜索, 同时保持              95%  以上
                 的召回率.
                    FreshDiskANN  [49] 是面向流式相似性搜索的实时图索引系统, 支持动态更新. FreshDiskANN             的核心创新包含
                 3  部分. 首先, 提出了首个支持增删操作的图索引算法              FreshVamana, 通过  α-RNG  邻域剪枝规则  [36] 维持图结构的
                 搜索性能. 该算法采用两阶段更新策略: 插入时基于贪婪搜索定位新节点的拓扑位置, 采用鲁棒剪枝保留满足                               α-RNG
                 规则的最优邻接边; 删除时延迟处理失效节点, 通过合并邻域路径避免图稀疏化, 配合周期性批量剪枝消除冗余
                 边. 其次, 设计了分层存储架构, 将长期数据存储在             SSD  构建的长期索引 (long-term index, LTI) 中, 而内存中的临
                 时索引 (TempIndex) 负责聚合实时更新. LTI 采用乘积量化压缩数据以降低空间占用, 而                   TempIndex  保留原始精
                 度向量确保更新质量. 最后, 提出了流式合并算法              StreamingMerge, 通过删除阶段块扫描、插入阶段双路搜索、修
                 补阶段批量剪枝的       3  步策略, 将增量更新以线性时间复杂度合并至             LTI. 该算法仅需两次全量扫描即可完成索引
                 更新, 相比于全量重建节省       90%  计算资源, 同时通过距离近似计算减少           SSD  随机访问. 实验结果表明, FreshDiskANN
                 在  10  亿级规模数据集上可实现       1 800  次/s 的稳态更新吞吐, 搜索延迟稳定在       20 ms 内且召回率超过      95%. 相比于
                 现有方案, 其硬件成本降低到         1/5–1/10, 为流式相似性搜索提供了首个可扩展的工业级解决方案.
                  2.2   基于层次的数据组织方法
                  2.2.1    基于树的方法
                    基于树的索引方法是经典的索引组织方法, 其被广泛用于索引的设计, 但是由于维度灾难的问题, 在对高维向
                 量进行索引时难以取得较好的效果. 基于树的方法的核心思路是将向量数据集合递归地划分为若干个子集, 从而
                 形成层次化的树状组织结构.
                          [30]
                    k-d tree  是经典的多维数据索引结构, 它选择超平面作为划分数据的依据. k-d tree 是一棵二叉树, 每个节点
                 对应一个   k  维向量数据点. 每个非叶节点同时对应一个超平面, 该超平面将空间划分成两个半空间, 分别交由其左
                 右子节点处理. k-d tree 在非叶节点中考察方差最大的维度, 对于某一个非叶节点, 选择当前空间内在考察维度上
                 取值最接近平均值或者中位数的向量数据点所在的与考察维度的方向向量垂直的超平面以进一步划分空间. k-d
                 tree 的搜索过程是一个递归过程, 从根节点开始, 根据查询点               q  在当前节点考察的维度上的取值与当前节点对应
                 的向量数据点的取值的大小关系判断下一步向左子树或右子树前进, 直到到达叶节点, 将其标记为当前的最近点
                 并回溯, 对于每个回溯到的节点, 首先检查其本身与查询点                 q  的距离是否较当前最近点更近, 再计算查询点             q  与当
                 前节点的分隔超平面的距离, 如果该距离小于当前的最近距离, 则说明在超平面另一侧的空间内可能存在距离查
                 询点  q  更近的节点, 需要递归搜索另一棵子树.
                    除了  k-d tree 之外, 还有很多经典的基于树的方法. Randomized k-d tree    [50] 与传统的  k-d tree 相比, 在划分维度
                 的选取上有所不同. 传统的        k-d tree 在每个非叶节点中选择当前空间内数据方差最大的方向, 而                randomized k-d tree
                 只从所有数据方差最大的          D  个方向中随机选取其一. R-tree     [51] 使用最小边界矩形组织数据, PCA tree     [52] 与  PKD
                 tree [50] 根据主成分分析确定划分超平面, Random Projection tree [53,54] 不使用复杂度较高的主成分分析方法, 通过随
                 机投影的方法确定划分超平面. 而           M-tree [55]  (通过中心点与覆盖半径构建嵌套超球体结构) 和          VP-tree [56]  (对每个
                 节点选择单一观测点, 根据数据与参考点的距离将数据划分为两个区域) 等方法则是基于距离度量而非坐标来组
                 织数据. K-means tree [57] 和  Hierarchical K-means tree [58] , 基于  K-means 聚类算法将数据划分为  K  个簇, 并在簇内递
                 归划分直到满足终止条件 (如树的深度、簇内数据数量等). ANNOY                   [59] 是一个基于树的方案, 其不同版本中维护
                 了  Random Projection trees 森林与  Hierarchical K-means trees 森林. FLANN [60] 是一个包含一系列近似最近邻搜索
                 方法的库. 它可以根据不同数据集考虑索引构建、搜索耗时以及内存占用的消耗, 从不同的包括                            Hierarchical K-means
                 tree 与  Randomized k-d trees 森林以及线性扫描等算法中选择效果最好的方法. LRUS-CoverTree        [61] 设计了一种树
                 状索引, 并根据其性质设计了分支限界算法以支持近似的最大内积查询.
   10   11   12   13   14   15   16   17   18   19   20