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

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


                 度相仿且都优于      SeRF, DIGRA  在低维度数据集 (比如     SIFT) 上相较于  iRangeGraph  表现更好.

                                          表 9 4  个面向范围与向量的混合查询方法对比

                                                      单次更新
                  具体方法     构建复杂度 空间复杂度 更新支持                                优点                    缺点
                                                      时间复杂度
                               2
                    SeRF    O(nm logn)  O(nmlogn) 全局重构  N/A             空间占用较低               不支持局部更新
                 iRangeGraph O(nm+nlogn) O(nmlogn) 全局重构  N/A   搜索精度高、可拓展支持多属性范围过滤 不支持局部更新
                   DIGRA    O(nlogn)  O(nmlogn) 局部更新   O(logn)      搜索精度高、更新效率高              空间占用较高
                   RangePQ  O(nlogn)   O(n)   局部更新     O(logn)           空间占用低               搜索精度略低

                    混合查询受到了越来越广泛的关注. 它能够提升信息检索的精确度和灵活性, 满足复杂多样化的搜索需求, 提
                 升用户体验. 如何支持高效的混合查询是向量数据库的关键问题之一, 探索更高效的搜索方法以及支持更多种类
                 的混合查询具有重要意义, 未来需要进行更多相关研究.
                  3.8   理论分析
                    通过对近似最近邻算法进行理论分析, 可以帮助我们理解算法性能的边界, 指导算法的设计和优化以及揭示
                 高维空间的性能, 避免按经验调参的盲目性, 为系统的扩展提供坚实基础. 近年来有不少工作在这方面取得了进
                 展, 下面我们进行介绍.
                    首先是面向图构建的理论分析研究. 文献              [160] 研究了基于图的近似最近邻搜索的理论和时间, 重点分析了
                 高维数据在稠密情况下 (d << logn) 的问题. 在图的构建中, 会通过添加长边 (long-range link) 来加速搜索进程. 该
                 文献理论分析了在图中添加长边对搜索的影响, 指出当前均匀地添加长边的策略优于随机添加. 该文献还对当前
                 以  best-first-search  为基础的束搜索方案进行了理论分析, 指出当前的搜索策略有助于减少图的度数, 进而降低图
                 的复杂度, 提升搜索性能. 当前理论依赖均匀分布假设, 未来需扩展至非均匀分布的情况. 这篇文献的理论分析为
                 基于图的近似最近邻搜索提供了理论基础, 帮助我们理解图的构建和搜索过程中的关键因素. 文献                                [114] 系统分
                 析了主流的基于图的方案的在最坏情况下的性能表现和理论局限性. 它从慢处理和快处理两个方面来分析当前基
                 于图的方案的性能表现. 慢处理是指在图中为每个节点添加邻居时考虑全局的数据点, 快处理是指先随机初始化
                 图, 然后搜索部分数据点作为候选节点从中选择相应的点作为邻居节点. 分析结果指出, 除了                            DiskANN  的慢处理
                 方法能够实现多对数时间复杂度之外, 所有方法在构建的数据实例上都需要线性的时间复杂度来进行搜索, 但是
                                          3
                 DiskANN  的慢处理方法需要     O(n ) 复杂度, 在实际中并不适用. 虽然算法的实际性能依赖数据分布和参数设置, 但
                 是本文通过理论证明与系统性实验揭示了               ANNS  算法的实际适用边界, 为算法选择与参数调优提供了重要参考.
                    其次是查询难度分析的研究. LID (local intrinsic dimensionality) [161,162] 是用来衡量数据集特征的重要工具. 它
                 结合数据点的距离分布来获得分析结果. 可以用这个指标来判断数据集进行近似最近邻搜索的难易程度. 文献                                  [10]
                 给出了一些常用数据集的         LID  值和  RC (relative contrast) [163] 值. RC  值是用平均距离和最近邻的距离的比值来衡量
                 难易程度. 文献    [115] 指出通过  LID  可以衡量一个不同      KNN  查询的难度, 这为我们从理论上对           ANNS  搜索的性
                 能分析带来了很多的启发和思路. 文献            [116] 提出了一种针对基于图的方法的查询难度度量方法                 Steiner-hardness,
                 旨在解决现有方法在衡量图的查询复杂性时的局限性. 当前图方法在处理某些困难查询时难以获得很高的召回
                 率, 导致整体性能下降, 传统的        LID  方法没有考虑图的拓扑结构信息, 难以反映查询的复杂性                 [116] . 文献  [116] 证明
                 了  Steiner-hardness 和有向斯坦纳树 (directed Steiner tree, DST) 高度关联, 因此将问题简化为  DST  问题, 然后利用
                 它的求解结果以有效地计算          Steiner-hardness. 实验结果显示, 与  LID  方法相比, Steiner-hardness 更能有效地反映查
                 询实际代价.
                  3.9   小 结
                    面对高维向量数据高性能的要求以及复杂业务场景的挑战, 学界与业界推动了向量搜索算法在多个维度的持
                 续创新与演进. 硬件加速技术 (如         SIMD  指令集、GPU   并行计算和多线程) 为向量搜索与索引构建提供了显著的
                 性能优化空间. 通过并行计算架构和指令集层面的优化, 这些技术有效缓解了高维向量计算中的性能瓶颈. 现代
   28   29   30   31   32   33   34   35   36   37   38