# MAG

**Repository Path**: CongFu_63d0/mag

## Basic Information

- **Project Name**: MAG
- **Description**: 欧式距离和内积距离两栖的向量检索算法。可以根据需要选择检索的相似度计算函数，一个索引同时支持欧式距离检索和最大内积检索，同时也是目前最好的最大内积检索算法。
- **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

# Metric-Amphibious Graph (MAG)

本仓库包含我们 SIGIR 2025 论文 **Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search** 的源代码。

**如果你感兴趣，也可以查看我们的理论工作：[VLDB2025 PSP](https://github.com/ZJU-DAILY/PSP)**

## 1 摘要（Abstract）

在基于图的搜索框架下，我们发现针对 MIPS，不同的建索引与搜索策略会因底层数据**拓扑结构**的差异而各具优势。基于这一洞见，我们提出了一种全新的图索引 **Metric-Amphibious Graph (MAG)**，以及与之配套的搜索算法 **Adaptive Navigation with Metric Switch (ANMS)**。为便于在不同数据分布上进行**参数调优**以获得更优性能，我们识别了三类能够刻画关键数据拓扑特性的统计指标，并验证了它们与参数选择之间的强相关性。

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

- 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)）
- Möbius-Graph（[论文](https://proceedings.neurips.cc/paper/2019/file/0fd7e4f42a8b4b4ef33394d35212b13e-Paper.pdf)）
- NAPG（[论文](https://dl.acm.org/doi/abs/10.1145/3447548.3467412)）
- ScaNN（[论文](http://proceedings.mlr.press/v119/guo20h/guo20h.pdf)）
- Naive MRNG

## 3 数据集（Datasets）

| 数据集            | Base | 维度 | 查询数  | 模态   | DBI(Euc.) | DBI(Cos.) | CV    |
| ----------------- | ---- | ---- | ------- | ------ | --------- | --------- | ----- |
| **Music100**      | 1M   | 100  | 10,000  | 音频   | 1.5       | 2.8       | 0.25  |
| **YFCC1M**        | 1M   | 100  | 1,000   | 多模态 | 1.51      | 2.9       | 0.07  |
| **SIFT1M**        | 1M   | 128  | 1,000   | 图像   | 3.26      | 2.6       | 0.001 |
| **Text2Image1M**  | 1M   | 200  | 100,000 | 多模态 | 2.5       | 3.0       | 0.03  |
| **MNIST1M**       | 1M   | 784  | 10,000  | 图像   | 2.7       | 2.8       | 0.18  |
| **GIST1M**        | 1M   | 960  | 1,000   | 图像   | 6.28      | 3.2       | 0.27  |
| **OpenAI-1536**   | 1M   | 1536 | 1,000   | 文本   | 4.1       | 5.3       | 0.0   |
| **Imagenet-1k**   | 1.3M | 1536 | 1,000   | 图像   | 1         | 1.4       | 0.36  |
| **Color3M**       | 3M   | 282  | 1,000   | 图像   | 2.6       | 2.1       | 0.17  |
| **Shopee10M**     | 10M  | 48   | 1,000   | 电商   | 2.4       | 2.1       | 0.24  |
| **Text2Image10M** | 10M  | 200  | 100,000 | 多模态 | 3.3       | 3.6       | 0.03  |
| **Laion10M**      | 12M  | 512  | 1,000   | 多模态 | 4.3       | 3.6       | 0.0   |

## 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**：主文件
- **benchmark**：存放索引与日志
- **script**：用于运行实验的脚本
- **test**：测试代码

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

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

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

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

```shell
./test/test_mag_index DATA_PATH KNNG_PATH L R C INDEX_PATH MODE DIM R_IP M THRESHOLD
```

- `DATA_PATH`：基础数据路径（`bin` 格式）。
- `KNNG_PATH`：*步骤 1* 中预构建的 kNN 图路径。
- `L`：初始搜索池大小（initial search pool size）。
- `R`：欧氏度量（NN）部分的最大出度。
- `C`：候选池大小（candidate pool size）。
- `INDEX_PATH`：生成的 MAG 索引路径。
- `MODE`：索引模式。
- `DIM`：数据维度。
- `R_IP`：内积度量（IP）部分的最大出度。
- `M`：最大出度（overall）。
- `THRESHOLD`：用于近似的 IP 阈值（严格等于 1，但设为 >1 通常效果更好）。

#### 步骤 3：带度量切换的自适应导航（Adaptive Navigation with Metric Switch）

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

- `DATA_PATH`：基础数据路径（`bin` 格式）。
- `QUERY_PATH`：查询数据路径（`bin` 格式）。
- `INDEX_PATH`：生成的 MAG 索引路径。
- `search_L`：搜索池大小；越大效果越好但更慢（必须大于 `K`）。
- `K`：返回的结果数量。
- `MODE`：搜索模式。
- `DIM`：数据维度。

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

- ✅ 已开源论文主要组件的代码  
- ✅ 支持更广泛、范数分布更丰富的数据集  
- 🔄 向量压缩加速（即将推出）  
- 🔄 面向内积的分层图结构（即将推出）  
- 🔄 分区算法集成（即将推出）  
- 🔄 自适应的提前停止策略（即将推出）  
- 🔄 Python 封装

## 7 性能（Performance）

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

- QPS

![evaluation](./evaluation.png)

## 8 引用（Citation）

```tex
@inproceedings{chen2025stitching,
  title={Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search},
  author={Chen, Tingyang and Fu, Cong and Ke, Xiangyu and Gao, Yunjun and Ni, Yabo and Zeng, Anxiang},
  booktitle={Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval},
  pages={2341--2350},
  year={2025}
}
```

## 9 联系方式（Contact）

如果你对我们的工作及后续合作机会感兴趣，欢迎联系：Tingyang Chen（chenty@zju.edu.cn）或 Cong Fu（fc731097343@gmail.com）。