提出PAG框架，让近似最近邻搜索更快更省内存。
Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach
- 用投影统计测试减少精确距离计算，提升搜索效率
- 在6个数据集上比HNSW快5倍，支持在线插入
- 兼顾高速索引、低内存、高维鲁棒性，适合实际部署
近似最近邻搜索（ANNS）是现代AI应用的核心。现有方案多侧重查询效率，却难以满足实际工作负载需求。本文总结现代AI应用的六大关键要求：高查询效率、快速索引、低内存占用、高维可扩展性、不同检索规模下的鲁棒性，以及支持在线插入。为此，我们提出投影增强图（Projection-Augmented Graph, PAG）框架，将投影技术融入图索引结构中。PAG通过投影引导的非对称比较，减少不必要的精确距离计算。设计三个核心组件集成于图索引中，优化索引与搜索性能。在六个现代数据集上的实验表明，PAG在查询每秒次数（QPS）-召回率表现上始终领先，最高达HNSW的5倍；同时具备快速索引速度和适中内存占用，且在维度和检索规模增加时仍保持鲁棒性，天然支持在线插入。
原文摘要 · Abstract (English)
Approximate Nearest Neighbor Search (ANNS) is fundamental to modern AI applications. Most existing solutions optimize query efficiency but fail to align with the practical requirements of modern workloads. In this paper, we outline six critical demands of modern AI applications: high query efficiency, fast indexing, low memory footprint, scalability to high dimensionality, robustness across varying retrieval sizes, and support for online insertions. To satisfy all these demands, we introduce Projection-Augmented Graph (PAG), a new ANNS framework that integrates projection techniques into a graph index. PAG reduces unnecessary exact distance computations through asymmetric comparisons between exact and approximate distances as guided by projection-based statistical tests. Three key components are designed and integrated into the graph index to optimize indexing and searching. Experiments on six modern datasets demonstrate that PAG consistently achieves superior queries per second (QPS)-recall performance -- up to 5x faster than HNSW -- while offering fast indexing speed and moderate memory footprint. PAG remains robust as dimensionality and retrieval size increase and naturally supports online insertions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。