# NSG

**Repository Path**: CongFu_63d0/nsg

## Basic Information

- **Project Name**: NSG
- **Description**: 存储高效的欧式距离向量检索算法。只需要HNSW 1/3的存储可以达到超越HNSW的检索效率。
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-11-04
- **Last Updated**: 2025-11-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# NSG : 用于近似最近邻搜索的 Navigating Spread-out Graph

## 合作（Cooperation）

如果你对最近邻搜索（Nearest Neighbor Search）的研究方向或应用感兴趣，并希望合作，请随时通过邮件联系我：fc731097343@gmail.com

目录
=================
<!--ts-->

* [简介](#简介)
* [性能表现](#性能表现)
     * [数据集](#数据集)
     * [对比算法](#对比算法)
     * [结果](#结果)
* [编译与构建](#编译与构建)
     * [先决条件](#先决条件)
     * [在 Ubuntu/Debian 上编译](#在-ubuntudebian-上编译)
     * [(可选) Docker 使用](#可选-docker-使用)
* [使用方法](#使用方法)
     * [构建 NSG 索引](#构建-nsg-索引)
     * [通过 NSG 索引进行搜索](#通过-nsg-索引进行搜索)
* [论文中的参数设置](#论文中的参数设置)
     * [NSG 构建](#nsg-构建)
     * [预构建的 kNN 图与 NSG 索引](#预构建的-knn-图与-nsg-索引)
* [在淘宝电商数据上的表现](#在淘宝电商数据上的表现)
* [参考文献](#参考文献)
* [待办事项](#待办事项)
* [许可证](#许可证)
<!--te-->

## 简介

NSG 是一种基于图的近似最近邻搜索（ANNS）算法。它为大规模稠密实向量上的近似最近邻搜索提供了灵活且高效的解决方案。该项目实现了我们 PVLDB 论文中的算法——[Fast Approximate Nearest Neighbor Search With The Navigating Spread-out Graphs](http://www.vldb.org/pvldb/vol12/p461-fu.pdf)。

NSG 已集成到淘宝（阿里巴巴集团）的搜索引擎中，用于电商场景下的**亿级规模** ANNS。

## 性能表现

### 数据集

+ [SIFT1M 和 GIST1M](http://corpus-texmex.irisa.fr/)
+ 合成数据集：RAND4M 和 GAUSS5M
  - **RAND4M**：从区间 [-1, 1] 的均匀分布中采样的 400 万个 128 维向量。
  - **GAUSS5M**：从高斯分布 N(0,3) 中采样的 500 万个 128 维向量。

### 对比算法

#### 基于图的 ANNS 算法

+ [kGraph](http://www.kgraph.org)
+ [FANNG](https://pdfs.semanticscholar.org/9ea6/5687a21c869fce7ecf17ca25ffcadbf77d69.pdf)：*FANNG: Fast Approximate Nearest Neighbour Graphs*
+ [HNSW](https://arxiv.org/abs/1603.09320)（[代码](https://github.com/searchivarius/nmslib)）：*Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs*
+ [DPG](https://arxiv.org/abs/1610.02455)（[代码](https://github.com/DBWangGroupUNSW/nns_benchmark)）：*Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement (v1.0)*
+ [EFANNA](https://arxiv.org/abs/1609.07228)（[代码](https://github.com/fc731097343/efanna)）：*EFANNA: An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph*
+ **NSG-naive**：我们设计的基线，详见[我们的 PVLDB 论文](http://www.vldb.org/pvldb/vol12/p461-fu.pdf)。
+ **NSG**：本项目实现，详见[我们的 PVLDB 论文](http://www.vldb.org/pvldb/vol12/p461-fu.pdf)。

#### 其他常见 ANNS 算法

+ [FLANN](http://www.cs.ubc.ca/research/flann/)
+ [FALCONN](https://github.com/FALCONN-LIB/FALCONN)
+ [Annoy](https://github.com/spotify/annoy)
+ [Faiss](https://github.com/facebookresearch/faiss)

### 结果

NSG 在四个数据集上均取得了**最优**的搜索性能。  
在所有***基于图的算法***中，NSG 具有***最小的索引体积***和***最佳的搜索性能***。

***注意：** 所有性能测试均在**无并行**条件下进行（一次仅搜索一个查询，无多线程）。*

**SIFT1M-100NN-All-Algorithms**

![SIFT1M-100NN-All-Algorithms](figures/siftall.png)

**SIFT1M-100NN-Graphs-Only**

![SIFT1M-100NN-Graphs-Only](figures/sift_graph.png)

**GIST1M-100NN-All-Algorithms**

![GIST1M-100NN-All-Algorithms](figures/gistall.png)

**GIST1M-100NN-Graphs-Only**

![GIST1M-100NN-Graphs-Only](figures/gist_graph.png)

**RAND4M-100NN-All-Algorithms**

![RAND4M-100NN-All-Algorithms](figures/randall.png)

**RAND4M-100NN-Graphs-Only**

![RAND4M-100NN-Graphs-Only](figures/rand_graph.png)

**GAUSS5M-100NN-All-Algorithms**

![GAUSS5M-100NN-All-Algorithms](figures/gaussall.png)

**GAUSS5M-100NN-Graphs-Only**

![GAUSS5M-100NN-Graphs-Only](figures/gauss_graph.png)

**DEEP1B-100NN**

![DEEP1B-100NN](figures/deep1b.png)

## 编译与构建

### 先决条件

+ GCC 4.9+（支持 OpenMP）
+ CMake 2.8+
+ Boost 1.55+
+ [TCMalloc](http://goog-perftools.sourceforge.net/doc/tcmalloc.html)

**重要说明：**本代码使用 **AVX-256** 指令进行快速距离计算，因此你的机器**必须**支持 AVX-256。可用如下命令检查：

```shell
cat /proc/cpuinfo | grep avx2
```

### 在 Ubuntu/Debian 上编译

1. 安装依赖：

```shell
sudo apt-get install g++ cmake libboost-dev libgoogle-perftools-dev
```

2. 编译 NSG：

```shell
git clone https://github.com/ZJULearning/nsg.git
cd nsg/
mkdir build/ && cd build/
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j
```

### （可选）Docker 使用

1. 构建 Docker 镜像

```shell
docker build -t nsg .
```

2. 运行并进入 Docker 容器

```shell
docker run -it --name nsg nsg bash
```

> 你可以根据需要修改项目中的 Dockerfile。

## 使用方法（Usage）

主要的接口与类在 `tests/` 目录下都有对应的测试代码。

### 构建 NSG 索引（Building NSG Index）

要使用 NSG 进行 ANNS，必须先构建 NSG 索引。以下是构建步骤。

#### 步骤 1：构建 kNN 图（Build kNN Graph）

首先，需要准备一个 kNN 图。

建议使用我们的 [efanna_graph](https://github.com/ZJULearning/efanna_graph) 来构建该 kNN 图；你也可以使用其他工具，例如 KGraph 或 Faiss。

#### 步骤 2：将 kNN 图转换为 NSG（Convert kNN Graph to NSG）

接着，将 kNN 图转换为 NSG 索引。

可以使用以下示例程序完成转换：
```shell
cd build/tests/
./test_nsg_index DATA_PATH KNNG_PATH L R C NSG_PATH
```

+ `DATA_PATH`：基础数据的路径，格式为 `fvecs`。
+ `KNNG_PATH`：*步骤 1* 中预构建的 kNN 图路径。
+ `L`：控制 NSG 的质量，数值越大质量越高。
+ `R`：控制图的索引规模；最优的 `R` 与数据集的**内在维度**相关。
+ `C`：控制 NSG 构建期间候选池的最大大小。
+ `NSG_PATH`：生成的 NSG 索引输出路径。

### 通过 NSG 索引进行搜索（Searching via NSG Index）

下面是使用 NSG 索引进行搜索的说明。

使用示例程序执行 kNN 搜索：
```shell
cd build/tests/
./test_nsg_optimized_search DATA_PATH QUERY_PATH NSG_PATH SEARCH_L SEARCH_K RESULT_PATH
```

+ `DATA_PATH`：基础数据路径（`fvecs` 格式）。
+ `QUERY_PATH`：查询数据路径（`fvecs` 格式）。
+ `NSG_PATH`：上一节中预构建的 NSG 索引路径。
+ `SEARCH_L`：控制搜索结果质量，越大越好但更慢；且 **`SEARCH_L` 不能小于 `SEARCH_K`**。
+ `SEARCH_K`：需要返回的近邻数量。
+ `RESULT_PATH`：查询结果输出（`ivecs` 格式）。

在 `tests/` 目录下还提供了 `test_nsg_search` 程序，其参数与 `test_nsg_optimized_search` **完全相同**。  
相较之下，`test_nsg_search` **更慢**但**占用内存更少**；在极度关注内存占用的场景下可以替代 `test_nsg_optimized_search` 使用。

***注意：** 目前仅支持 **int32** 与 **float32** 两种数据类型。*

> **提示 1：关于 `data_align()`**  
> 我们提供的 `data_align()` 函数对正确性至关重要，因为实现中使用了 AVX/SSE2 等 SIMD 指令进行数值计算加速。  
> 该函数用于将特征维度对齐至 8 或 16 的倍数。例如：若原始特征维度为 70，需要扩展到 72，并将新增的 2 个维度填充为 0，以保证距离计算的正确性。

> **提示 2：数据格式**  
> 关于 `fvecs/ivecs` 格式的详细说明，请参考：[http://yael.gforge.inria.fr/file_format.html](http://yael.gforge.inria.fr/file_format.html)

## 论文中的参数设置

### NSG 构建（NSG Building）

我们使用以下参数得到论文中图 6（参见 [arXiv 版本](https://arxiv.org/abs/1707.00143)）的结果。  
kNN 图由 [efanna_graph](https://github.com/ZJULearning/efanna_graph) 构建。

#### 步骤 1：构建 kNN 图（Build kNN Graph）

+ 工具： [efanna_graph](https://github.com/ZJULearning/efanna_graph)  
+ 参数：

| 数据集 (Dataset) |  K   |  L   | 迭代次数 (iter) |  S   |  R   |
| :--------------: | :--: | :--: | :-------------: | :--: | :--: |
|      SIFT1M      | 200  | 200  |       10        |  10  | 100  |
|      GIST1M      | 400  | 400  |       12        |  15  | 100  |

+ 命令：
```shell
efanna_graph/tests/test_nndescent sift.fvecs sift_200nn.graph 200 200 10 10 100    # SIFT1M
efanna_graph/tests/test_nndescent gist.fvecs gist_400nn.graph 400 400 12 15 100    # GIST1M
```

#### 步骤 2：将 kNN 图转换为 NSG（Convert kNN Graph to NSG）

+ 参数：

| 数据集 (Dataset) |  L   |  R   |  C   |
| :--------------: | :--: | :--: | :--: |
|      SIFT1M      |  40  |  50  | 500  |
|      GIST1M      |  60  |  70  | 500  |

+ 命令：
```shell
nsg/build/tests/test_nsg_index sift.fvecs sift_200nn.graph 40 50 500 sift.nsg        # SIFT1M
nsg/build/tests/test_nsg_index gist.fvecs gist_400nn.graph 60 70 500 gist.nsg        # GIST1M
```

### 预构建的 kNN 图与 NSG 索引（Pre-built kNN Graph and NSG Index）

我们同时提供用于论文实验的预构建文件：

- **kNN 图**：
  - SIFT1M — [sift_200nn.graph](http://downloads.zjulearning.org.cn/nsg/sift_200nn.graph)
  - GIST1M — [gist_400nn.graph](http://downloads.zjulearning.org.cn/nsg/gist_400nn.graph)
- **NSG 索引**：
  - SIFT1M — [sift.nsg](http://downloads.zjulearning.org.cn/nsg/sift.nsg)
  - GIST1M — [gist.nsg](http://downloads.zjulearning.org.cn/nsg/gist.nsg)

## 在淘宝电商数据上的表现

**环境：**
+ **CPU**：Xeon E5-2630

**单线程测试：**
+ **数据集**：10,000,000 个 128 维向量
+ **延迟**：在 10,000 次查询上平均 1ms

**分布式搜索测试：**
+ **数据集**：45,000,000 个 128 维向量  
  划分方式：将数据集随机划分为 12 个子集，各自构建 NSG，**并行**搜索后合并结果。
+ **延迟**：在 10,000 次查询上平均 1ms

## 参考文献（Reference）

如果你在研究中使用了 NSG，请引用以下论文：

```
@article{FuNSG17,
  author    = {Cong Fu and Chao Xiang and Changxu Wang and Deng Cai},
  title     = {Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graphs},
  journal   = {{PVLDB}},
  volume    = {12},
  number    = {5},
  pages     = {461 - 474},
  year      = {2019},
  url       = {http://www.vldb.org/pvldb/vol12/p461-fu.pdf},
  doi       = {10.14778/3303753.3303754}
}
```

## 待办事项（TODO）

- [x] 添加 Docker 支持
- [ ] 改进 SIMD 相关代码的兼容性
- [ ] Python 封装
- [ ] 添加 Travis CI

## 许可证（License）

NSG 采用 **MIT** 许可。