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

宋子文 等: 向量数据库中近似最近邻搜索关键技术综述                                                       995


                    (1) 关键词过滤
                    Filtered-DiskANN [111] 是一个基于图的混合查询索引方案. 它建立在        Vamana 图的基础上, 包括     FilteredVamana
                 和  StitchedVamana 两种方案. 前者从一个空的图开始进行构建, 通过动态剪枝和标签感知的搜索方法来确定每个
                 节点的邻居节点; 后者建立在前者的基础上, 通过合并不同过滤标签下的子图以形成统一的索引. 为了降低索引大
                 小, 在合并之后对每个点的邻居进行裁剪以降低每个节点的出度.
                    ACORN  [112] 是在  HNSW  基础上设计的支持同时处理向量相似性查询和结构化谓词过滤的索引方案. 它将每
                 个节点的邻居候选点数量从          M  扩展到  λM, 以提高搜索到满足要求的点的可能性, 但是这会导致索引大小和构建
                 时间的增加. 为了解决这个问题, 对扩展后的邻居列表进行剪枝操作, 保留                      Mβ 条边, 其余的边在搜索时通过两跳
                 邻居获取, 以平衡索引大小和搜索效率. 实验结果显示, ACORN                方案相较于     Filtered-DiskANN  等设计方案取得了
                 2  倍以上的性能提升. UNG     [151] 是一个用于支持带标签混合搜索的信息框架. 它将数据根据标签进行分组, 然后通
                 过有向无环图来构建标签导航图            LNG  以刻画标签的包含关系, 在此基础上利用当前的图构建方法对每一组数据
                 分别构建相应的图, 最后通过跨组边来连接不同标签组的向量, 实现高效的搜索.
                    此外, HQANN   [152] 同样是一个基于图的方法, 在邻近图的构建阶段优先链接属性相同或相似的数据点以保持
                               [153]
                 图的连通性. DEG      是一个面向多向量搜索的方法. 它同样是一个基于图的方案, 通过逐点插入的方式来构建索
                 引, 并通过贪心帕累托 (greedy Pareto) 搜索方法来获取候选邻居集合, 采用动态剪枝策略来选择邻居节点. VBase                    [154]
                 是一个微软开发的基于        PostgreSQL  的面向向量搜索的数据引擎. 它提供了用火山模型执行查询优化的后过滤搜
                 索方案. AnalyticDB-V [155] 是阿里巴巴开发的向量搜索引擎. 它能够根据查询优化器的代价估计选择合适搜索方案
                                  [1]
                 执行混合查询. Milvus 等向量数据库都提供包括前后过滤等一系列相关方案来支持混合搜索.
                    UNG  保证了在搜索过程中不会访问不能通过标签过滤的向量, 而                    Filtered-DiskANN  与  ACORN  不具有该性
                 质. 文献  [112] 中的  ACORN-1  索引构建速度较快, 而    ACORN-γ、UNG   与  Filtered-DiskANN  的构建速度相仿, 其
                 中  UNG  略慢于其余二者. 在索引的内存占用方面, UNG           索引占用较少内存, Filtered-DiskANN    可以结合内存与磁
                 盘存储索引以减少内存占用. 在更新方面, UNG             给出了一种局部重构的更新手段, 而其余方法并不能有效地支持
                 动态更新, 针对标签过滤查询索引的高效更新策略仍然亟须进一步研究.
                    (2) 范围过滤
                    范围过滤指的是要求属性数据落在一个范围内, 整体的查询目标是找出属性值在指定范围内与查询向量近似
                 的向量. SeRF [113] 是一个面向范围过滤的方法, 对于半有界查询, 提出段图 (segment graph) 来优化查询, 通过利用图
                 构建邻居节点的性质在单个          HNSW  索引中动态分段, 避免为每个范围单独构建图; 对于一般范围查询, 提出二维
                 段图 (2D segment graph) 来加快查询, 并通过压缩    n  个段图来实现降低存储空间的目标. 它适用于指出动态范围过
                 滤的向量检索, 如查询某个时间范围内具有显著特征的产品、车辆等. 实验结果显示其能够在保持较高召回率的
                 同时具有很高的查询效率.
                    WST [156] 是一个结合线段树和图来实现范围混合查询的方案. 它递归地划分数据集构建索引, 能够根据查询的
                 范围特点来选择相应的查询算法. iRangeGraph         [157] 同样是一个基于线段树的方案. 它在线段树的每个节点上建立
                 对应的图索引, 在搜索时先根据线段树来确定满足范围的点, 然后再进一步搜索返回满足要求的向量; 在构建阶段
                 构建少量基础图, 在查询时动态组合这些图生成与查询目标相符合的图来完成搜索. 实验结果显示其比                                 Milvus 等
                 方案在相同召回率下具有更快的查询速度. RangePQ             [158] 针对  iRangeGraph  难以支持更新和空间占用高的问题, 提
                 出  PQ  量化和二叉树结合的方法来设计优化策略. DIGRA            [159] 通过基于动态多叉树的结构来设计支持动态更新.
                    SeRF、iRangeGraph、DIGRA  与  RangePQ  算法的各项均摊复杂度如表       9 所示. DIGRA  与  RangePQ  的索引构
                 建速度相对较快. iRangeGraph    与  DIGRA  的索引内存占用相仿, SeRF      略小于二者, 由于     RangePQ  结合了量化技
                 术, 其内存空间占用是      4  个方法中最小的. DIGRA     与  RangePQ  提供了对动态更新的支持, 二者各自的删除速度都
                 明显快于插入速度; SeRF      与  iRangeGraph  当遇到数据更新时只能进行重构, 不能很好地支持数据频繁更新的场景.
                 iRangeGraph  可拓展以支持多属性范围查询, 而其余         3  个方法并未直接提供对该场景的支持. 在查询性能方面, 由
                 于  RangePQ  引入了量化技术, 其搜索精度会稍逊于其余           3  个方法, DIGRA  与  iRangeGraph  在高维数据集上搜索精
   27   28   29   30   31   32   33   34   35   36   37