🔗 NSG 图索引算法动态演示

1.5s
数据点
入口点 ⭐
查询点
最近邻
图边
当前步骤
点击"生成随机点"开始演示
图构建信息:
点击"生成随机点"开始
搜索统计
等待开始搜索...

🔗 NSG 图索引算法介绍

📖 算法概述

NSG（Navigating Spreading-out Graph）是一种基于图的近似最近邻搜索算法，通过构建一个导航图来实现高效的向量检索。NSG在保证搜索质量的同时，显著提升了搜索速度和内存效率。

🔧 核心思想

  • 图构建：为每个数据点建立与其最近邻的连接，形成一个连通图
  • 导航搜索：从入口点开始，沿着图边进行贪心搜索
  • 候选扩展：维护候选集合，不断扩展搜索范围
  • 剪枝优化：通过距离比较和角度约束进行有效剪枝

🚀 算法优势

⚡
高效搜索

通过图导航实现亚线性时间复杂度

💾
内存友好

相比树结构，图结构更节省内存

🎯
高精度

在高维空间中保持良好的搜索精度

💡 应用场景

🔍 向量搜索 🖼️ 图像检索 📝 文档相似性 🎵 音频匹配 🤖 推荐系统 🧬 生物信息学

⚖️ 与其他算法对比

🌳 树结构 (K-D Tree)

  • 适用于低维数据
  • 构建简单
  • 高维性能下降

🔗 图结构 (NSG)

  • 适用于高维数据
  • 搜索路径灵活
  • 内存效率高

📈 复杂度分析

构建时间: O(n²) 最坏
搜索时间: O(log n) 平均
空间复杂度: O(n·k)
by 福强 & Kiro