RNNDescent 向量检索算法

本项目实现了基于 RNNDescent（Recursive Nearest Neighbor Descent）的高效向量检索算法，适用于大规模高维向量数据的最近邻搜索任务。

许可声明

本项目（外部调试版本）的知识产权归华为公司所有，未经授权不得用于商业目的。详细许可条款请见本文档末尾的商用许可章节。

项目简介

RNNDescent 是一种基于图的近似最近邻搜索算法，通过构建和优化近邻图来加速向量检索过程。本实现支持大规模数据集（百万级）的高效检索，并围绕图构建、图搜索、精排和距离计算做了针对性的工程优化。

核心特性

• 支持多种向量维度与数据集 benchmark
• 支持按数据集或测试场景配置 build/search 参数
• 集成可配置的 PCA 降维链路
• 支持并行计算，充分利用多核 CPU
• 实现了多种距离计算优化（SIMD、BLAS 等）

算法原理

RNNDescent 算法通过以下步骤构建和优化近邻图：

1. 初始图构建：为每个数据点随机选择或通过启发式方法选择初始近邻
2. 迭代优化：重复应用局部搜索策略，不断改进近邻图的质量
3. 搜索过程：从种子点开始，在近邻图中进行贪婪搜索，找出近似最近邻

当前主线版本的优化重点不再是“单条指令多线程搜索后整体重排”的旧实验方案，而是围绕下面这条稳定链路展开：

1. 图构建优化：通过 RNNDescent 迭代构建近邻图，并在构建后对节点顺序做重排，提升图搜索时的局部性。
2. 图搜索优化：搜索阶段优先使用缓存后的图向量和专用距离计算器，降低候选扩展时的访存成本。
3. 精排优化：最终返回前，对候选集使用原始向量距离计算器做精排，保证返回距离和真实距离基本一致。
4. 距离计算优化：按平台选择 AVX512 / AVX2 / NEON / BLAS 路径，并复用统一的 distance-computer 工厂。
5. 内存优化：邻居缓存池按配置和可用内存动态收缩，避免为缓存命中率盲目占满内存。

项目结构

├── main.cpp          # 主程序入口，包含测试和性能评估
├── CMakeLists.txt    # CMake 构建配置
├── run.sh            # 运行脚本
└── solution/         # 核心算法实现
    ├── solution.h    # Solution 类接口定义
    ├── solution.cpp  # Solution 类实现
    └── rnndescent/   # RNNDescent 算法核心实现
        ├── IndexRNNDescent.h  # RNNDescent 索引接口
        ├── RNNDescent.h       # RNNDescent 算法核心
        └── discomputer/       # 距离计算模块

安装与编译

依赖项

• C++17 兼容的编译器
• CMake 3.23 或更高版本
• OpenMP（用于并行计算）
• Faiss 库（用于基础向量操作）
• BLAS 或 OpenBLAS（用于矩阵计算）

编译步骤

1. 确保所有依赖项已安装
2. 执行以下命令进行编译：

mkdir -p build
cd build
cmake ..
make -j$(nproc)

3. 编译完成后，可执行文件将生成在 build 目录下

使用方法

Benchmark 模式

当前主程序支持两种 benchmark 模式：

1. 随机数据压测
2. 真实数据集压测（参考 rnn-descent/benches 的思路）

随机数据压测

./build/algorithm
./build/algorithm --mode random --data-size 100000 --dim 256 --topk 10 --repeat 5

数据集压测

如果还没有数据集，可以先下载：

sh benches/download_dataset.sh siftsmall
sh benches/download_dataset.sh sift
sh benches/download_dataset.sh gist

如果目录下包含类似下面这些文件：

• base.fvecs 或 base.bvecs
• query.fvecs 或 query.bvecs
• groundtruth.ivecs 或 gt.ivecs

可以直接跑：

./build/algorithm --mode dataset --dataset-dir /path/to/siftsmall --topk 10 --repeat 5

也可以手动指定文件：

./build/algorithm --mode dataset \
  --base /path/to/base.fvecs \
  --query /path/to/query.fvecs \
  --gt /path/to/groundtruth.ivecs \
  --topk 10 --repeat 5

支持格式

• dense vectors: fvecs, bvecs
• ground truth: ivecs

结果落盘

每次 benchmark 会自动把结果写到：

benches/results/<dataset_name>/latest.txt
benches/results/<dataset_name>/<timestamp>.txt

结果文件会包含：

• build 时间
• 每轮 query latency
• 平均/最小/最大 latency
• recall
• 距离误差
• top1 gap

基本使用

编译完成后，可以直接运行生成的可执行文件：

./algorithm

或者使用提供的运行脚本：

./run.sh

自定义配置

当前 benchmark 的主要参数入口在 main.cpp：

• S：局部搜索的大小
• R：构建过程中的采样数量
• beam_size：beam search 参数
• search_L：搜索过程中的扩展参数
• K0：初始搜索数量
• num_initialize：搜索初始化项数量
• refine_max：最终精排候选上限
• neighbor_pool_size_limit_bytes：邻居缓存池上限

可以按随机测试维度或真实数据集预设不同参数组合。

性能评估

主程序会自动生成随机测试数据并进行性能评估，输出以下信息：

1. 索引构建时间
2. 搜索延迟（每查询平均毫秒数）
3. 吞吐量（每秒查询数）
4. 检索结果的距离信息

随机模式默认覆盖多种维度；数据集模式可以直接评估 siftsmall、sift、gist 等标准数据。

优化技术

本实现采用了多种优化技术来提升性能：

1. 多线程并行：使用 OpenMP 实现构建和搜索过程的并行化
2. SIMD 优化：使用 SIMD 指令加速距离计算
3. 缓存图搜索：对图搜索使用缓存后的向量布局和快速距离计算器
4. 精排校正：对候选结果使用原始向量精排，保证距离准确性
5. 参数调优：支持按数据集或测试场景优化算法参数

注意事项

1. 当前实现不支持动态插入数据，索引构建后无法添加新向量
2. 算法参数针对特定硬件环境进行了优化，可能需要根据实际环境进行调整
3. 编译时需确保正确链接 BLAS 或 OpenBLAS 库

参考资料

• RNNDescent 算法原始论文
• Faiss 库文档
• OpenMP 并行编程指南

商用许可

本项目（外部调试版本）遵循以下商用许可条款：

1. 非商业用途许可：未经华为公司书面授权，不得将本项目用于任何商业目的。

2. 内部调试使用：本代码仅用于算法调试和性能测试，与华为公司内部商用版本存在较大差异。

3. 知识产权声明：本项目包含的所有代码、算法和优化方法的知识产权归华为公司所有。

4. 修改限制：未经授权，不得修改、分发、逆向工程或以任何形式传播本项目代码。

5. 免责声明：本调试版本不保证性能、稳定性或正确性，仅供参考和学习使用。

如需商业授权或了解更多商用版本信息，请联系华为公司相关部门。

---

本项目为华为算法大赛参赛作品(外部调试版本)，实现了高效的大规模向量检索算法。与内部商用有较大差别