| 摘要: |
| 高维向量近似最近邻搜索 (approximate nearest neighbor search, ANNS)是向量数据库的基础和核心之一. 随着人工智能的发展, 向量数据库发挥了日益关键的作用, 获得了广泛的关注, 高效的ANNS方法对向量数据库的性能优化十分关键. 在几十年的发展中, ANNS取得了一系列成果. 近些年随着该领域的快速发展, 涌现出来的新方法和研究成果亟须系统性梳理. 首先介绍了ANNS的基本概念; 其次在已有的综述框架的基础上, 根据向量数据组织方式将当前的内容进一步归纳为基于图、层次、量化、哈希和混合数据组织这5类, 并结合代表性和最新的成果进行介绍; 然后从向量数据搜索优化方法的角度提出面向硬件加速、面向学习增强、面向距离比较操作、面向磁盘内存混合场景、面向数据访问优化、面向分布式场景、面向混合查询和理论分析这8个方面的分类体系对最近的搜索方法进行综述; 最后基于当前的研究成果和趋势, 展望未来的研究方向. |
| 关键词: 近似最近邻搜索 向量数据库 索引 高维数据 向量搜索 查询优化 |
| DOI：10.13328/j.cnki.jos.007516 |
| 分类号:TP311 |
| 基金项目:国家重点研发计划 (2024YFF0617702); 国家自然科学基金 (U22A2025, 62232007, U23A20309); 高等学校学科创新引智计划 (B16009) |
|
| Survey on Key Techniques of Approximate Nearest Neighbor Search in Vector Databases |
|
SONG Zi-Wen, WANG Bin, ZHANG Xi-Rui, ZHAO Shi-Hao, YANG Xiao-Chun
|
|
School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China
|
| Abstract: |
| High-dimensional approximate nearest neighbor search (ANNS) is one of the fundamental and core components of vector databases. With the advancement of artificial intelligence, vector databases have played an increasingly critical role and have gained widespread attention. ANNS methods are essential for optimizing the performance of vector databases. Over decades of development, ANNS has achieved a series of milestones. Rapid advancements in this field in recent years have led to a surge of novel methods and findings, necessitating systematic organization. In this study, the basic concepts of ANNS are first introduced. Next, building upon existing survey frameworks, current approaches are further categorized into five groups based on vector data organization methods: graph-based, hierarchical, quantization-based, hashing-based, and hybrid data organization. Representative works and the latest research advances in the field are systematically discussed. Then, from the perspective of vector search optimization methods, recent advancements are reviewed and categorized into eight types. These categories include hardware acceleration oriented, learning enhanced, distance comparison operation oriented, disk-memory hybrid oriented, data access optimization oriented, distributed oriented, hybrid query oriented, and theoretical analysis. Finally, based on current research achievements and trends, potential future research directions are outlined. |
| Key words: approximate nearest neighbor search (ANNS) vector database index high-dimensional data vector search query optimization |
