NSG vs 其他ANNS算法：为什么Navigating Spreading-out Graph能实现亿级数据秒级检索？

【免费下载链接】nsgNavigating Spreading-out Graph For Approximate Nearest Neighbor Search项目地址: https://gitcode.com/gh_mirrors/ns/nsg

NSG（Navigating Spreading-out Graph）是一种基于图结构的近似最近邻搜索（ANNS）算法，专为大规模密集向量检索设计。作为阿里巴巴淘宝搜索引擎的核心技术之一，NSG已成功应用于电商场景下的亿级数据检索任务，实现了毫秒级响应速度。本文将深入对比NSG与其他ANNS算法的核心差异，解析其如何突破传统检索技术的性能瓶颈。

📊 算法性能大比拼：NSG如何碾压同类方案？

在ANNS领域，算法性能通常通过查询速度与精度的平衡来衡量。NSG在多个权威数据集上的表现令人瞩目，尤其在高维向量检索场景中展现出显著优势。

高斯分布数据集（GAUSS5M）测试结果

图1：NSG与HNSW、KGraph等算法在GAUSS5M数据集上的Precision@100对比（越低的曲线代表相同精度下速度越快）

从图中可以清晰看到，NSG（紫色曲线）在几乎所有精度区间都保持着最低的查询延迟。当Precision@100达到0.95时，NSG的查询速度比HNSW快约30%，比KGraph快近2倍，这种优势在高精度要求场景下更为明显。

SIFT1M图像特征数据集测试结果

图2：不同算法在SIFT1M图像特征数据集上的检索性能对比

SIFT1M作为计算机视觉领域的标准测试集，包含100万张图像的128维特征向量。NSG在该数据集上再次展现统治力：在保持98%检索精度的同时，实现了每秒处理超过100次查询的性能，这一结果使其成为实时图像检索系统的理想选择。

随机分布数据集（RAND4M）测试结果

图3：NSG在均匀随机分布数据集上的鲁棒性测试

面对最难处理的随机分布数据，NSG依然保持稳定性能。其独特的图结构设计使其在数据分布不规则时，仍能维持高效的检索路径，而其他算法如FANNG和Efanna则出现明显的性能下降。

🔍 NSG核心优势解析

1. 创新的图结构设计：导航点与扩展图

NSG的核心突破在于提出了导航点（Navigation Point）机制和扩展图（Spreading-out Graph）结构。传统图算法（如HNSW）依赖层次化结构，导致构建复杂度高且对内存需求大。NSG通过：

• 精选导航点作为全局路径引导
• 优化邻居选择策略减少冗余连接
• 动态调整图密度适应数据分布

这种设计使NSG索引大小比HNSW小40%，同时保持更高的查询效率。相关实现代码可参考src/index_nsg.cpp中的图构建逻辑。

2. 高效的搜索算法：贪心路由+剪枝策略

NSG的查询过程结合了贪心路由与高效剪枝：

1. 从导航点出发快速定位候选区域
2. 采用动态邻居扩展策略探索潜在近邻
3. 通过距离阈值剪枝减少无效计算

这种搜索机制使其在tests/test_nsg_optimized_search.cpp中实现了单线程1ms/查询的性能，满足实时检索需求。

3. 工程级优化：SIMD加速与内存对齐

NSG深度优化了底层计算：

• 使用AVX-256指令集加速距离计算（需CPU支持AVX2，可通过cat /proc/cpuinfo | grep avx2检查）
• 实现特征向量内存对齐（参考include/efanna2e/util.h中的data_align()函数）
• 采用TCMalloc优化内存分配

这些优化使NSG在实际部署中能充分利用硬件性能，在淘宝的生产环境中实现了4500万向量的分布式检索，平均延迟仍控制在1ms以内。

🚀 快速上手NSG：从安装到检索

环境准备

NSG支持Linux系统，需以下依赖：

• GCC 4.9+（支持OpenMP）
• CMake 2.8+
• Boost 1.55+
• TCMalloc内存分配器

一键安装步骤

# 克隆仓库 git clone https://link.gitcode.com/i/238d6ca1545a188313beb176cd8f7054 cd nsg # 安装依赖 sudo apt-get install g++ cmake libboost-dev libgoogle-perftools-dev # 编译 mkdir build && cd build cmake -DCMAKE_BUILD_TYPE=Release .. make -j

构建与检索流程

NSG的使用分为两步：

1. 构建索引：将原始向量转换为NSG图结构

# 示例：处理SIFT1M数据集 ./build/tests/test_nsg_index sift.fvecs sift_200nn.graph 40 50 500 sift.nsg

2. 执行检索：使用优化的搜索接口查询近邻

# 示例：查询100个近邻 ./build/tests/test_nsg_optimized_search sift.fvecs query.fvecs sift.nsg 100 100 result.ivecs

Python用户可直接使用pynsg目录下的接口，简化集成流程。

💡 为什么选择NSG？适用场景与最佳实践

NSG特别适合以下场景：

• 高维向量检索：图像特征、文本嵌入、推荐系统
• 实时响应要求：搜索引擎、人脸识别、智能客服
• 大规模数据：千万至十亿级向量库

最佳实践建议：

• 对于128维以下向量，推荐设置R=50-70（邻居数量）
• 内存有限时使用test_nsg_search替代优化版
• 分布式场景可参考淘宝的12分片方案（4500万向量/1ms延迟）

📈 未来展望：NSG的持续进化

NSG项目仍在活跃发展中， roadmap包括：

• 改进SIMD兼容性以支持更多硬件
• 增加Travis CI自动化测试
• 扩展对稀疏向量的支持

作为开源项目，NSG欢迎贡献者参与开发，共同推动近似最近邻搜索技术的边界。

📚 参考文献与资源

• 核心论文：Fast Approximate Nearest Neighbor Search With The Navigating Spread-out Graphs
• 代码仓库：nsg
• 预训练索引：SIFT1M与GIST1M预构建索引

通过创新的图结构设计与工程优化，NSG正在重新定义大规模向量检索的性能标准。无论是学术研究还是工业应用，NSG都提供了一个兼顾速度、精度与内存效率的理想解决方案，为亿级数据检索难题提供了高效的答案。

【免费下载链接】nsgNavigating Spreading-out Graph For Approximate Nearest Neighbor Search项目地址: https://gitcode.com/gh_mirrors/ns/nsg