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

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


                 Key words:  approximate nearest neighbor search (ANNS); vector database; index; high-dimensional data; vector search; query optimization

                    向量数据库     [1–4] 是专门用于高效存储和检索高维向量数据的数据库系统. 随着机器学习、计算机视觉和自然
                 语言处理等领域的快速发展, 向量化表征已经成为图像、文本、用户行为等多模态数据的通用抽象表示方法. 随
                 着大语言模型的兴起, 向量数据库的应用场景日益扩展. 面对大语言模型                      [5] 存在的幻觉问题和时效性局限        [6] , 检索
                 增强生成 (retrieval-augmented generation, RAG) 技术  [7] 通过向量搜索获取相关上下文作为模型输入, 有效提升了模
                 型性能, 在优化大模型推理性能的           KV cache 中也发挥着重要作用      [8] , 这使得向量数据库成为     AI 基础设施的关键
                 组成部分. 向量数据库的核心任务是高效地进行向量相似性搜索, 即在给定查询向量的情况下, 快速找到与之相似
                 的向量. 由于维度灾难的问题         [9] , 在高维向量上搜索难以返回准确的近邻点. 近似最近邻搜索 (approximate nearest
                 neighbor search, ANNS) 旨在放宽对精确近邻的要求, 以提高搜索速度和效率.
                    在人工智能和大数据驱动的技术场景下, 向量检索面临着更大的挑战, 当前向量数据维度进一步攀高, 能达到
                 成百上千维, 向量数据规模也进一步增长, 攀升至              10  亿级规模, 对于维度为     d  的  N  条向量采用暴力搜索的时间复
                 杂度为   O(Nd), 而且存储原始浮点向量所需的空间随着数据规模和维度的增加线性增加, 内存开销也随之增加. 计
                 算开销、存储成本开销和内存访问开销制约着向量搜索效率的提升. 向量数据库设计高效的索引结构和搜索算
                 法, 以支持快速的相似性搜索和高效的数据存储, 其主要从多个目标进行优化, 包括但不限于: (1) 降低数据访问代
                 价, 通过优化数据的访问方式来降低访问代价, 提升搜索性能; (2) 降低计算代价, 通过减少距离计算等来提升搜索
                 性能; (3) 降低内存开销, 通过量化编码等方式减少内存中的数据量; (4) 提升算法扩展性, 充分利用新硬件和分布
                 式提升处理能力. 在设计算法时需综合考虑查询效率、精度、存储开销和硬件适配之间的权衡, 并与向量数据库
                 有机配合, 以实现高效的向量检索.
                    向量近似最近邻搜索是一个经典的问题, 已有几十年的历史, 学术界进行了广泛而深入的研究. 过去已有不少
                 优秀的综述对近似最近邻搜索方法进行了系统的总结和分析, 主要集中在基于图、树、哈希、量化等方法上                                     [10] .
                 近年来, 大批新方法相继被提出, 包括设计新的图构建方法、量化方法等以及从如何利用硬件加速、面向分布式
                 环境的设计、如何优化距离比较操作等角度来进行优化, 已有的综述工作并没有对这些新工作进行充分反映, 亟
                 须对这些研究成果进行梳理. 文献           [10] 从基于树、哈希和图的方法上系统性地评估了各个算法的效果. 其成文时
                 间较早, 当前有更多新的研究成果被提出来并展示了良好的效果. 文献                     [11,12] 对基于图的近似最近邻搜索方法进
                 行了综述, 没有涉及近年来提出的其他优化方法. 文献                [13,14] 对基于哈希的近似最近邻搜索方法进行了系统的总
                 结  ,   主  要  介  绍  了  多  种  哈  希  函  数  和  索  引  结  构  .   其  成  文  时  间  较  早  ,   后  续  有  更  多  新  的  工  作  被  提  出  .   文  献  [ 1 5 ]
                 则对基于乘积量化的近似最近邻搜索方法进行了深入的分析, 探讨了量化技术在高维向量搜索中的应用, 其成文
                 时间同样较早, 当前有更多的量化方法被提出, 尤其将量化和其他形式索引结合的方式取得了很好的效果, 需要进
                 一步总结. 文献    [4] 从向量数据库系统的角度进行了综述, 其总结的算法主要是针对向量数据库系统实现的相关
                 方法. 文献   [16] 核心展示了对    ANNS  算法进行性能评测的工具. 这些综述为研究人员提供了宝贵的参考和指导,
                 更好地理解和应用近似最近邻搜索方法.
                    近年来涌现出一批新的研究成果. 一方面, 在向量数据索引组织方面, 一些新的优化策略被提出, 如更多基于
                 图的优化方案, 同时, 研究不再局限于单一的组织方式, 而是研究多种组织方式的协作, 如结合图和量化的方法对
                 索引结构进行优化以提升搜索性能, 这要求我们针对索引组织方法进行更系统的总结分类. 另一方面, 很多方法不
                 再局限于索引组织方式的优化, 而是扩展到更多技术路径, 面向更多场景, 采用更多技术手段来对向量搜索进行优
                 化, 如利用硬件加速进行优化, 利用学习方法来增强索引能力、面向分布式场景等. 这些方法不同于以往的分类框
                 架, 需要新的总结分类, 进行综述梳理.
                    本文的主要目的是对最新的近似最近邻搜索方法研究成果进行全面的综述. 以往的综述将近似最近邻搜索分
                 为基于图、基于树、基于哈希和基于量化的方法, 本文在现有基础上将向量数据组织方法分为                                5  类: 基于图的索
                 引组织方法、基于层次的索引组织方法、基于哈希的索引组织方法、基于量化的索引组织方法和混合索引组织
                 方法. 我们结合相关成果对每种方法进行介绍和分析. 在此基础上, 我们进一步总结最新的向量搜索优化方法成
   4   5   6   7   8   9   10   11   12   13   14