作者：hws000（hws.000#163.com）
声明：版权所有，转载请联系作者。
出处：https://blog.simbot.net/2024/07/08/ann_vs_hnsw_build_search_compare/

1.软硬件介绍

测试平台为AWS EC2，具体配置如下表：

名称	类型	CPU核数	内存(GB)	价格($/h)
g5.xlarge	A10G	4	16	1.006
g5.4xlarge	A10G	16	64	1.624
m7i.2xlarge	Xeon 8488C	8	32	0.4032
m7g.2xlarge	Graviton3	8	32	0.3264

A10G GPU的FP16算力为70TFLOPS，详细参数见：https://d1.awsstatic.com/product-marketing/ec2/NVIDIA_AWS_A10G_DataSheet_FINAL_02_17_2022.pdf

ann算法构建索引分为两步：(1)CPU与GPU协同加速构建近似knn图；(2)使用nsg算法对近似knn图进行裁剪，生成索引图。ann裁剪、搜索算法支持X86的AVX512指令集，也支持Arm的Neon指令集。

hnsw算法来源为https://github.com/nmslib/hnswlib，版本v0.8.0，支持AVX512指令集。

数据集分别为：Deep1B（维度96，欧式距离）的10M子集，查询数据集10K；cohere的miracl-zh-corpus-22-12（维度768，内积距离）中随机提取的1M子集，查询数据集1.3K。

2.建索引速度、成本对比

上图分别为deep1b(g5.4xlarge)、miracl-zh(g5.xlarge)在构建TopK为128的近似knn图时的耗时/准确率(召回率，随机选取10万个点进行验证)曲线。当准确率越高时，裁剪后的索引图搜索效果越好。后续裁剪选取的近似knn图的准确率分别为98.6%(deep1b，耗时25.4秒)、98%(miracl-zh，耗时9.75秒)。

下表中分别为ann(本算法)、ann-arm(本算法的arm版本)、hnsw(参数M=32 ef_c=400)、hnsw2(参数M=16 ef_c=200)，在m7i、m7g平台的索引耗时及费用(含用GPU创建近似knn图的费用)：

算法	deep1b耗时	miracl-zh耗时	deep1b费用	miracl-zh费用
ann	28.5	9.32	0.0147	0.0038
ann-arm	22.75	9.5	0.0135	0.0036
hnsw	2602	771	0.2914	0.0864
hnsw2	1000	288	0.1120	0.0323

3.搜索效果对比

上图分别为deep1b、miracl-zh数据集的查询总耗时(横轴，单位：秒)，及召回率(纵轴，80%-100%)。

上图分别为查询耗时，及100-召回率的值(对数刻度)，此表示更能反映高召回率时的细节。

上图分别为平均一次查询的比较次数(计算距离并比较的次数)，及100-召回率的值。

上图分别为不同的平均比较次数，及查询总耗时，可直观展示不同算法、平台的计算效率。

4.总结

通过以上对比可知，以M=32 ef_c=400为参数构建的hnsw索引的搜索效率更接近ann算法，但建索引耗时为ann算法的48倍、40倍，成本为ann算法的19.8倍、22.7倍(GPU单位时间的成本更高)。使用arm平台建索引、搜索的速度更快，成本更低。

通过用SIMD指令参与排序，使CPU在构建近似knn图时效率提高数倍。

ann算法的高效实现依赖CN202111620913.X、CN202210286230.3、CN202210763651.0等专利。