最近邻基准测试

在高维空间中快速搜索最近邻是一个日益重要的问题，但至今很少有客观比较各种方法的实证尝试，尽管这种比较对推动优化进展至关重要。

本项目包含了用于对特定度量标准的各种近似最近邻（ANN）搜索实现进行基准测试的工具。我们已经预先生成了数据集（HDF5格式），并为每种算法准备了Docker容器，以及用于验证功能完整性的测试套件。

已评估

• Annoy
• FLANN
• scikit-learn：LSHForest、KDTree、BallTree
• Weaviate
• PANNS
• NearPy
• KGraph
• NMSLIB（非度量空间库） ：SWGraph、HNSW、BallTree、MPLSH
• hnswlib（nmslib项目的一部分）
• RPForest
• FAISS
• DolphinnPy
• Datasketch
• nndescent
• PyNNDescent
• MRPT
• NGT ：ONNG、PANNG、QG
• SPTAG
• PUFFINN
• N2
• ScaNN
• Vearch
• Elasticsearch ：HNSW
• Elastiknn
• ExpANN
• OpenSearch KNN
• DiskANN ：Vamana、Vamana-PQ
• Vespa
• scipy：cKDTree
• vald
• Qdrant
• 华为(qsgngt)
• Milvus : Knowhere
• Zilliz(Glass)
• pgvector
• pgvecto.rs
• RediSearch
  • pg_embedding
• 笛卡尔(01AI)
• kgn 数据集 =========

我们提供了多个以HDF5格式预计算的数据集。所有数据集都已预先分割为训练集和测试集，并包含前100个最近邻的真实数据。

数据集	维度	训练集大小	测试集大小	邻居数	距离	下载
DEEP1B	96	9,990,000	10,000	100	角度	HDF5 (3.6GB)
Fashion-MNIST	784	60,000	10,000	100	欧几里得	HDF5 (217MB)
GIST	960	1,000,000	1,000	100	欧几里得	HDF5 (3.6GB)
GloVe	25	1,183,514	10,000	100	角度	HDF5 (121MB)
GloVe	50	1,183,514	10,000	100	角度	HDF5 (235MB)
GloVe	100	1,183,514	10,000	100	角度	HDF5 (463MB)
GloVe	200	1,183,514	10,000	100	角度	HDF5 (918MB)
Kosarak	27,983	74,962	500	100	Jaccard	HDF5 (33MB)
MNIST	784	60,000	10,000	100	欧几里得	HDF5 (217MB)
MovieLens-10M	65,134	69,363	500	100	Jaccard	HDF5 (63MB)
NYTimes	256	290,000	10,000	100	角度	HDF5 (301MB)
SIFT	128	1,000,000	10,000	100	欧几里得	HDF5 (501MB)
Last.fm	65	292,385	50,000	100	角度	HDF5 (135MB)

结果

以下结果均截至2023年4月，在AWS的r6i.16xlarge机器上运行所有基准测试，使用参数--parallelism 31并禁用超线程。所有基准测试都是单CPU运行。

glove-100-angular

sift-128-euclidean

fashion-mnist-784-euclidean

nytimes-256-angular

gist-960-euclidean

glove-25-angular

待办：更新http://ann-benchmarks.com上的图表。

安装

唯一的前提条件是Python（已测试3.10.6版本）和Docker。

1. 克隆仓库。
2. 运行pip install -r requirements.txt。
3. 运行python install.py以在Docker容器内构建所有库（这可能需要一段时间，大约10-30分钟）。

运行

1. 运行python run.py（这可能需要极长时间，可能会持续数天）
2. 运行python plot.py或python create_website.py来绘制结果。
3. 运行python data_export.py --out res.csv将所有结果导出到csv文件中，以便进行额外的后处理。

你可以按以下方式自定义算法和数据集：

• 检查ann_benchmarks/algorithms/{YOUR_IMPLEMENTATION}/config.yml是否包含你想要测试的参数设置
• 要在SIFT上运行实验，请执行python run.py --dataset glove-100-angular。有关可能的设置的更多信息，请参见python run.py --help。请注意，实验可能需要很长时间。
• 要处理结果，可以使用python plot.py --dataset glove-100-angular或python create_website.py。示例调用：python create_website.py --plottype recall/time --latex --scatter --outputdir website/。

包含你的算法

通过提供以下内容，将你的算法添加到ann_benchmarks/algorithms/{YOUR_IMPLEMENTATION}/文件夹中：

• 一个名为module.py的小型Python封装
• 一个名为Dockerfile的Dockerfile
• 一组在config.yml中的超参数
• 通过将你的实现添加到.github/workflows/benchmarks.yml来运行CI测试

查看可用实现以获取灵感。

原则

• 欢迎所有人提交拉取请求，对每个库的使用方式进行调整和修改。
• 特别是：如果你是这些库中任何一个的作者，并且认为可以改进基准测试，请考虑进行改进并提交拉取请求。
• 这是一个持续进行的项目，旨在反映当前状态。
• 使所有内容易于复制，包括安装和准备数据集。
• 尝试每个库的多个不同参数值，忽略不在精度-性能前沿的点。
• 高维数据集，维度约为100-1000。这既具有挑战性，又符合实际情况。不超过1000维，因为这些问题可能应该通过单独进行降维来解决。
• 默认使用单一查询。ANN-Benchmarks 确保在实验过程中只饱和一个 CPU，即不进行多线程处理。提供了一种批处理模式，可以一次性向实现提供所有查询。在 run.py 和 plot.py 中添加 --batch 标志以启用批处理模式。
• 避免极其昂贵的索引构建（超过几个小时）。
• 专注于适合 RAM 的数据集。对于十亿级基准测试，请参见相关的 big-ann-benchmarks 项目。
• 我们主要支持基于 CPU 的 ANN 算法。FAISS 存在 GPU 支持，但必须在本地编译 GPU 支持，并且必须使用 --local --batch 标志运行实验。
• 对索引数据和查询点进行适当的训练/测试集划分。
• 请注意，我们认为集合相似度数据集是稀疏的，因此我们向算法传递一个已排序的整数数组来表示每个用户的集合。

作者

由 Erik Bernhardsson 构建，Martin Aumüller 和 Alexander Faithfull 做出了重要贡献。

相关出版物

基准测试框架背后的设计原则在以下出版物中有所描述：

• M. Aumüller, E. Bernhardsson, A. Faithfull: ANN-Benchmarks: 近似最近邻算法的基准测试工具。Information Systems 2019. DOI: 10.1016/j.is.2019.02.006
• M. Aumüller, E. Bernhardsson, A. Faithfull: ANN-Benchmarks 的可复现性协议：近似最近邻搜索算法的基准测试工具，成果。

相关项目

• big-ann-benchmarks 是一项针对十亿级近似最近邻搜索的基准测试工作，作为 NeurIPS'21 竞赛赛道 的一部分。