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

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


                 CPU  普遍支持的   SIMD  和多线程机制, 能够为向量搜索提供灵活高效的基础算力支撑; GPU                   凭借其大规模并行架
                 构和高带宽显存, 则特别适合批量向量运算, 但同时也面临数据结构适配性要求高、显存容量制约大规模数据处
                 理以及高成本等挑战. 未来, 如何协同利用            CPU  与  GPU  的异构计算优势, 构建高效且可扩展的向量检索体系, 将
                 成为向量数据库发展的关键方向.
                    在算法层面, 面向学习增强的优化引入机器学习模型对数据分布主动建模以适应不同数据集的特性, 优化索
                 引划分以及搜索路由等, 并与倒排和图方法进行深度融合, 以提升搜索精度与效率. 面向距离比较操作 (DCO) 的
                 优化方法的核心思想是通过在距离计算过程中尽早判断两个点的距离是否超过阈值, 提前终止距离计算以实现计
                 算性能优化. 这些方法通过随机投影、主成分分析 (PCA)、残差角度估计等手段, 对两个点之间的距离进行估计,
                 结合假设检验等手段, 快速过滤掉不满足条件的点. 它们是在基于图、倒排等基本结构的基础上进行设计, 作为插
                 件进行使用, 降低系统的改动和适配难度.
                    在应对大规模数据与资源受限场景方面, 磁盘-内存混合索引 (如                  DiskANN、SPANN) 和分布式优化 (如     Pyramid、
                 Auncel、SmartANNS) 提供了横向与纵向的可扩展性解决方案. 它们通过内存压缩、分布式分片、异构硬件协同
                 等机制, 实现了单机与集群层面的高效处理能力. 磁盘-内存混合索引通常与数据访问优化 (如重排序、缓存) 协同
                 设计, 以最大化    I/O  利用率; 分布式优化则结合算法特性与系统调度, 提升全局负载均衡与资源利用.
                    在人工智能广泛应用、业务需求多样化背景下, 混合查询优化 (如                     Filtered-DiskANN、ACORN、SeRF  等) 实
                 现了向量与结构化属性的联合检索, 满足复杂的业务逻辑和多维查询需求. 通过整合向量检索方法与经典数据结
                 构来构建的混合查询索引, 按其核心优化目标, 主要分为面向关键词查询和面向范围查询两大类, 用户可以根据应
                 用需求, 选择合适的索引完成高性能的查询.
                    在理论研究方面, 研究者通过建立严谨的数学模型, 对算法的复杂度边界和性能极限进行了系统的刻画. 这些
                 工作不仅揭示了高维空间下          ANNS  算法的性能瓶颈, 还深入分析了如图结构构建、长边添加策略、搜索机制等
                 关键环节对搜索效率的影响, 提出了如            LID、RC、Steiner-hardness 等度量方法, 用以量化数据集和查询任务的内
                 在难度. 这些研究通过最坏情况分析与复杂度证明, 为算法设计和参数调优提供了坚实的理论基础, 减少了经验调
                 参的盲目性, 并为系统的可扩展性和性能保证提供了科学指导.
                  4   未来研究展望

                    在人工智能时代, 向量数据库作为关键的数据管理的基础设施, 会发挥越来越重要的作用. 向量近似最近邻搜
                 索作为其中的关键环节, 将在未来的研究中继续发挥重要作用. 通过以上的综述研究我们可以发现, 近年来向量近
                 似最近邻检索取得了一系列的进展, 但面对以下               3  个趋势: (1) 非结构化数据快速增长, 如每天有超过           2 000  万条视
                 频被上传到    YouTube 平台  [164] , 越来越多不同类型的如文本、图像、音频等数据会进行嵌入表示以实现深层语义
                 的表达, 向量数据发挥着日益重要的作用; (2) 实时动态需求越来越重要, 每天有大量的视频、购物信息等新数据
                 产生  [67] , 要求应用能够及时对新内容完成反馈; (3) 混合查询越来越重要, Miluvs 等向量数据库将混合查询作为向
                 量数据库的一个重要功能         [63] 来实现结合向量的深层语义表示以及结构化数据的精确语义, 从而更准确地提供给
                 用户满意的结果, 当前仍存在若干关键挑战亟待解决. 本节从                  5  个方向来对未来的研究方向进行展望.
                    (1) 面向磁盘的索引结构优化
                    向量数据维度高、数据量大、内存占用高, 当前基于图的方法, 如                     HNSW [28] 、NSG [17] 等严重依赖内存的方案
                 难以应对大规模数据的存储和检索需求. 当前已有一些工作在这方面取得了一些进展, 如                           SPANN [107] 、DiskANN [36]
                 等, 未来研究应致力于设计更高效的结构, 充分利用磁盘的存储能力, 设计磁盘内存结合的索引结构, 降低磁盘随
                 机  I/O  的开销以保证搜索性能, 避免因磁盘带来的性能瓶颈, 并探索利用新硬件来提升性能等.
                    (2) 动态索引更新机制
                    向量数据的动态更新是一个重要的研究方向. 当前的索引结构大部分是静态的, 难以支持动态的数据更新操
                 作, 尤其是基于图的方法. 当前在向量数据库中采用定期重建索引的方案来应对动态变化的数据, 导致开销巨大.
                 因此, 研究如何设计增量式的图更新策略, 在支持高效的增删操作的同时, 保证维持图的质量, 保持高召回率、低
   29   30   31   32   33   34   35   36   37   38   39