# SSG

**Repository Path**: CongFu_63d0/ssg

## Basic Information

- **Project Name**: SSG
- **Description**: 存储可调节的欧式距离向量检索算法。只需要HNSW 1/3的存储可以达到超越HNSW的检索效率。相对于NSG算法，可以根据数据集特性调节索引图结构。
- **Primary Language**: Unknown
- **License**: BSD-3-Clause
- **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

# SSG : 用于近似最近邻搜索的 Satellite System Graph

## 合作（Cooperation）

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

## 简介（Introduction）

======

SSG 是一种基于图的近似最近邻搜索（ANNS）算法。它为大规模稠密实向量上的ANNS 提供了灵活且高效的解决方案。  
该项目实现了我们的论文算法：[Satellite System Graph: Towards the Efficiency Up-Boundary of Graph-Based Approximate Nearest Neighbor Search](https://arxiv.org/abs/1907.06146)

## 基准数据集（Benchmark datasets）
------

| 数据集    | 下载                                                         | 维度 | 基础向量数 nb base vectors | 查询向量数 nb query vectors | 原始站点                                                     |
| --------- | ------------------------------------------------------------ | ---- | -------------------------- | --------------------------- | ------------------------------------------------------------ |
| SIFT1M    | [original website](http://corpus-texmex.irisa.fr/)           | 128  | 1,000,000                  | 10,000                      | [original website](http://corpus-texmex.irisa.fr/)           |
| GIST1M    | [original website](http://corpus-texmex.irisa.fr/)           | 128  | 1,000,000                  | 1,000                       | [original website](http://corpus-texmex.irisa.fr/)           |
| Crawl     | [crawl.tar.gz](http://downloads.zjulearning.org.cn/data/crawl.tar.gz) (1.7GB) | 300  | 1,989,995                  | 10,000                      | [original website](http://commoncrawl.org/)                  |
| GloVe-100 | [glove-100.tar.gz](http://downloads.zjulearning.org.cn/data/glove-100.tar.gz) (424MB) | 100  | 1,183,514                  | 10,000                      | [original website](https://nlp.stanford.edu/projects/glove/) |
| Deep100M  | deep100m.tar.gz* (34GB)                                      | 96   | 100,000,000                | 10,000                      | [original website](http://sites.skoltech.ru/compvision/noimi/) |

\* 对于 Deep100M，我们可在请求时提供下载链接。

## ANNS 性能（ANNS performance）
------

性能测试在**无并行**的条件下进行。  
在所有***基于图的算法***中，NSG 与 SSG 具有***最小的索引体积***。

![Performance](pictures/Performances.jpg)

对比算法（Compared Algorithms）：

#### 基于树（Tree-based）

* [FLANN](http://www.cs.ubc.ca/research/flann/)
* [Annoy](https://github.com/spotify/annoy)

#### 基于量化（Quantization-based）

* [Faiss](https://github.com/facebookresearch/faiss)

#### 基于图（Graph-based）

* [KGraph](http://www.kgraph.org)
* [HNSW](https://github.com/searchivarius/nmslib)
* [DPG](https://github.com/DBWangGroupUNSW/nns_benchmark)
* [NSG](https://github.com/zjulearning/nsg) —— 我们此前的[论文](http://www.vldb.org/pvldb/vol12/p461-fu.pdf)、[代码](https://github.com/ZJULearning/nsg)。

> 更多其他图算法（如 [FANNG](https://pdfs.semanticscholar.org/9ea6/5687a21c869fce7ecf17ca25ffcadbf77d69.pdf)）的性能，请参见我们的 [NSG 论文](http://www.vldb.org/pvldb/vol12/p461-fu.pdf)。

## 使用方法（How to use）
------

### 编译（Compile）

* 先决条件：openmp、cmake、boost  
* 编译步骤：  
  1. 进入 faiss 的根目录（在本项目旁边的 `extern_libraries` 目录下）。  
  2. 执行以下命令：

```bash
$ cd /path/to/project
$ mkdir -p build && cd build
$ cmake .. && make -j
```

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

主要接口与类在 `tests/` 目录下有相应的测试代码。  
请按照以下步骤构建 SSG 索引。

#### a) 构建 kNN 图（Build a kNN graph）

首先，需要准备一个 kNN 图。  
建议使用我们的 [efanna_graph](https://github.com/ZJULearning/efanna_graph) 来构建该 kNN 图；你也可以使用其他替代方案，如 KGraph 或 Faiss。

#### b) 将 kNN 图转换为 SSG（Convert the kNN graph to an SSG）

示例：

```bash
$ cd /path/to/project/build/tests/
$ ./test_ssg_index data_path knn_graph_path L R Angle ssg_path
```

* **data_path**：原始数据的路径。  
* **knn_graph_path**：预先构建好的 kNN 图路径。  
* **L**：控制索引质量，**越大越好**，且需满足 **L > R**。  
* **R**：控制图索引大小；最佳取值与数据集的**内在维度**相关。  
* **Angle**：控制两条边之间的夹角阈值。  
* **ssg_path**：结果 SSG 的保存路径。

### 使用 SSG 进行近似最近邻搜索（Approximate Nearest Neighbor Search using SSG）

示例：

```bash
$ cd /path/to/project/build/tests/
$ ./test_ssg_optimized_search data_path query_path ssg_path search_L search_K result_path [random_seed]
```

* **data_path**：原始数据路径。  
* **query_path**：查询数据路径。  
* **ssg_path**：预构建 SSG 的路径。  
* **search_L**：控制搜索质量，**越大越好但更慢**（且必须**大于** `search_K`）。  
* **search_K**：要寻找的近邻数量。  
* **result_path**：结果近邻的输出路径。  
* **random_seed**（可选）：随机种子。

> **注意：** 目前仅提供**单次单查询**的接口，并在**单线程**下测试性能。  
> **注意：** 数据对齐（data alignment）对正确性至关重要。由于我们使用 AVX、SSE2 等 SIMD 指令进行加速，需要确保特征维度以 8 或 16 个 `int/float` 对齐。  
> 例如：特征维度为 70 时，应扩展到 72，并将最后两个维度填充为 0；`data_align()` 的作用即在于完成该对齐与填充。  
> **注意：** 目前仅支持 **int32** 与 **float32** 两种数据类型。

### Python API

#### 安装（Install）

```bash
$ cd /path/to/project/
$ python setup.py install
```

#### 用法（Usage）

> 注意：当前 Python API 仅支持 `search` 方法。

```python
import numpy as np
import pyssg

data = np.fromfile("/path/to/sift_base.fvecs", dtype=np.float32)
dim = data[0].view(np.int32)
data = data.reshape(-1, dim + 1)
data = np.ascontiguousarray(data[:, 1:])
ndata, dim = data.shape

pyssg.set_seed(1234)
index = pyssg.IndexSSG(dim, ndata)
index.load("/path/to/ssg", data)

k, l = 100, 300
query = np.random.randn(dim).astype(np.float32)
knn = index.search(query, k, l)
print(knn)
```

更多实际示例请参考 `tests/test_python_query.py`。

## 我们论文中使用的参数（Parameters used in Our Paper）

### SSG 构建（SSG Building）

我们使用以下参数得到论文（[our paper](https://arxiv.org/abs/TODO)）图 6 中的 SSG 索引结果。  
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  |  12  |  10  | 100  |
|      GIST1M      | 400  | 400  |  12  |  15  | 100  |
|      Crawl       | 400  | 420  |  12  |  15  | 100  |
|    GloVe-100     | 400  | 420  |  12  |  20  | 200  |

+ 命令：

```bash
$ efanna_graph/tests/test_nndescent sift.fvecs sift_200nn.knng 200 200 12 10 100
$ efanna_graph/tests/test_nndescent gist.fvecs gist_400nn.knng 400 400 12 15 100
$ efanna_graph/tests/test_nndescent crawl.fvecs crawl_400nn.knng 400 420 12 15 100
$ efanna_graph/tests/test_nndescent glove-100.fvecs glove-100_400nn.knng 400 420 12 15 200
```

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

+ 参数：

| 数据集 (Dataset) |  L   |  R   | Angle |
| :--------------: | :--: | :--: | :---: |
|      SIFT1M      | 100  |  50  |  60   |
|      GIST1M      | 500  |  70  |  60   |
|      Crawl       | 500  |  40  |  60   |
|    GloVe-100     | 500  |  50  |  60   |

+ 命令：

```bash
$ ./test_ssg_index sift.fvecs sift_200nn.knng 100 50 60 sift.ssg
$ ./test_ssg_index gist.fvecs gist_400nn.knng 500 70 60 gist.ssg
$ ./test_ssg_index crawl.fvecs crawl_400nn.knng 500 40 60 crawl.ssg
$ ./test_ssg_index glove-100.fvecs glove-100_400nn.knng 500 50 60 glove-100.ssg
```

### SSG 搜索（SSG Search）

+ `search_L`：取值范围为 `search_K` 到 2000  
+ `random_seed`：161803398

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

这里提供我们在论文实验中使用的预构建 kNN 图与 SSG 索引文件：

| 数据集 (Dataset) |                            kNN 图                            |                           SSG 索引                           |
| :--------------: | :----------------------------------------------------------: | :----------------------------------------------------------: |
|      SIFT1M      | [sift_200nn.knng](http://downloads.zjulearning.org.cn/ssg/sift_200nn.knng) | [sift.ssg](http://downloads.zjulearning.org.cn/ssg/sift.ssg) |
|      GIST1M      | [gist_400nn.knng](http://downloads.zjulearning.org.cn/ssg/gist_400nn.knng) | [gist.ssg](http://downloads.zjulearning.org.cn/ssg/gist.ssg) |
|      Crawl       | [crawl_400nn.knng](http://downloads.zjulearning.org.cn/ssg/crawl_400nn.knng) | [crawl.ssg](http://downloads.zjulearning.org.cn/ssg/crawl.ssg) |
|    GloVe-100     | [glove_400nn.knng](http://downloads.zjulearning.org.cn/ssg/glove-100_400nn.knng) | [glove.ssg](http://downloads.zjulearning.org.cn/ssg/glove-100.ssg) |