# PSP

**Repository Path**: CongFu_63d0/psp

## Basic Information

- **Project Name**: PSP
- **Description**: 面向最大内积检索的向量检索算法。在内积检索领域，其检索效率相对于HNSW提升35%，存储占用远小于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

<h1 align="center">PSP - Proximity Graph with Spherical Pathway </h1>

本仓库包含我们论文 **Maximum Inner Product is Query-Scaled Nearest Neighbor**（VLDB25）的源代码。

**如果你感兴趣，也可以查看我们扩展的后续成果：[SIGIR2025 MAG](https://github.com/ZJU-DAILY/MAG)**

## 1 摘要（Abstract）

本文提出了一个全新的理论框架，在**无需进行空间变换**的情况下，将 MIPS 等价为 NNS。由此我们可以直接利用先进的图索引（针对 NNS）以及高效的边裁剪策略，大幅减少不必要的计算。

## 2 基线对比算法（Competitors）

> ip-nsw 与 ip-nsw+ 的初始代码来自各自的原论文，我们基于 hnswlib 0.8.0 进行了重构。对于 Möbius-graph 与 NAPG，我们未找到可用的开源实现，因此根据论文自行实现了版本，并会开源以便复现实验。ScaNN 是商业产品，我们使用其开源版本，并通过细致的参数调优取得了优秀结果。其官方示例默认未开启多线程；如果你在评测中使用多线程，请调用相关函数。

- ip-NSW（[论文](https://proceedings.neurips.cc/paper_files/paper/2018/file/229754d7799160502a143a72f6789927-Paper.pdf)）：一种使用内积可导航小世界图的图方法。
- ip-NSW+（[论文](https://aaai.org/ojs/index.php/AAAI/article/view/5344/5200)）：在 ip-NSW 基础上引入额外角度邻近图的增强版本。
- Möbius-Graph（[论文](https://proceedings.neurips.cc/paper/2019/file/0fd7e4f42a8b4b4ef33394d35212b13e-Paper.pdf)）：利用 Möbius 变换将 MIPS 归约为 NNS 的图方法。由于原始代码不可得，我们基于论文自行实现。
- NAPG（[论文](https://dl.acm.org/doi/abs/10.1145/3447548.3467412)）：近期图方法，通过使用针对不同范数分布的自适应 $\alpha$ 改进 ip-NSW，声称达到 SOTA 表现。
- Fargo（[论文](https://www.vldb.org/pvldb/vol16/p1100-zheng.pdf)）：最新的、具备理论保证的基于 LSH 的 SOTA 方法。
- ScaNN（[论文](http://proceedings.mlr.press/v119/guo20h/guo20h.pdf)）：量化方向的 SOTA 方法。

## 3 数据集（Datasets）

数据格式：向量数量（n） × 维度（d）。

*：数据来源将在论文正式发表后开放。

| 数据集                                                       | 基础集规模  | 维度 | 查询集规模 | 模态   |
| ------------------------------------------------------------ | ----------- | ---- | ---------- | ------ |
| MNIST（[链接](https://yann.lecun.com/exdb/mnist/index.html)） | 60,000      | 784  | 10,000     | 图像   |
| DBpedia100K（[链接](https://huggingface.co/datasets/Qdrant/dbpedia-entities-openai3-text-embedding-3-large-3072-100K)） | 100,000     | 3072 | 1,000      | 文本   |
| DBpedia1M（[链接](https://huggingface.co/datasets/Qdrant/dbpedia-entities-openai3-text-embedding-3-large-1536-1M)） | 1,000,000   | 1536 | 1,000      | 文本   |
| Music100（[链接](https://github.com/stanis-morozov/ip-nsw)） | 1,000,000   | 100  | 10,000     | 音频   |
| Text2Image1M（[链接](https://research.yandex.com/blog/benchmarks-for-billion-scale-similarity-search)） | 1,000,000   | 200  | 100,000    | 多模态 |
| Text2Image10M（[链接](https://research.yandex.com/blog/benchmarks-for-billion-scale-similarity-search)） | 10,000,000  | 200  | 100,000    | 多模态 |
| Laion10M（[链接](https://arxiv.org/abs/2210.08402)）         | 12,244,692  | 512  | 1,000      | 多模态 |
| Commerce100M*                                                | 100,279,529 | 48   | 64,111     | 电商   |

## 4 编译说明（Building Instruction）

### 先决条件（Prerequisites）

- GCC 4.9+（支持 OpenMP）
- CMake 2.8+
- Boost 1.55+
- Faiss（可选）

### 在 Linux 上编译（Compile On Linux）

```shell
$ mkdir build/ && cd build/
$ cmake ..
$ make -j
```

## 5 使用方法（Usage）

### 代码结构（Code Structure）

- **datasets**：数据集
- **include**：C++ 类接口
- **output**：PSP 索引、k-MIP 结果文件
- **script**：实验脚本
- **src**：主功能实现
- **test**：测试代码

### 使用步骤（How to use）

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

首先需要准备一个 kNN 图。你可以使用 Faiss 或其他库生成。

#### 步骤 2：PSP 建索引（PSP indexing）

```shell
./test/test_mips_index DATA_PATH KNNG_PATH L R Angle M PSP_PATH DIM
```

- `DATA_PATH`：基础数据的路径（`bin` 格式）。
- `KNNG_PATH`：*步骤 1* 中预构建的 kNN 图路径。
- `L`：候选池大小。
- `R`：最大出度。
- `Angle`：边之间的最小夹角。
- `M`：内积邻居数（IP neighbor）。
- `PSP_PATH`：生成的 PSP 索引路径。
- `DIM`：数据集维度。

#### 步骤 3：PSP 搜索（PSP searching）

```shell
./test/test_mips_search DATA_PATH QUERY_PATH PSP_PATH searh_L K RESULT_PATH DIM
```

- `DATA_PATH`：基础数据路径（`bin` 格式）。
- `QUERY_PATH`：查询数据路径（`bin` 格式）。
- `PSP_PATH`：生成的 PSP 索引路径。
- `search_L`：搜索池大小，值越大效果越好但更慢（必须大于 `K`）。
- `K`：返回结果的近邻个数。
- `PSP_PATH`：结果近邻的输出路径。
- `DIM`：数据集维度。

## 6 待办清单（To-Do Lists）

- ✅ 已开源论文主要组件的代码。
- ✅ 在 Shopee 平台上的 Commerce100M 真实场景评测。
- 🔄 更自动化的入口点选择与“提前停止”技术。
- 🔄 改进与 SIMD 相关 PQ 代码的兼容性。
- 🔄 Python 封装。
- 🔄 覆盖更多不同范数分布的数据集。

## 7 性能（Performance）

#### 评测指标（Evaluation Metric）

- QPS、距离计算次数（针对图方法）

![evaluation](./evaluation.png)