北京文景松科技有限公司最新的向量搜索算法与hnsw算法的比较

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

北京文景松科技有限公司最新的向量搜索算法，与经典的hnsw算法相比，建索引速度提高40倍以上，费用减少20倍，且搜索速度更快，效果更佳，且适用于超大规模数据集。

新的构建近似knn图的方法有如下优点：1.充分利用GPU计算速度快的特点，分批次计算近邻，每批计算前先将分散数据从CPU端打包并写入到显存的连续区域，消除随机读取数据的问题，同时解决超大数据集无法将数据全部放入显存的问题；2.每批次计算时，只对当次结果排序，计算结束后将结果传出，在CPU端使用SIMD指令完成新旧结果合并，无需频繁读写旧的结果，同时也解决了超大数据集的排序结果无法全部存储在显存的问题；3.由于数据是分批计算，不同批次间没有依赖关系，可以多GPU同时计算（若有必要），使处理速度成倍提高。新的算法是专为GPU设计的，完美的利用了计算速度快的特点，与传统的CPU生成近似knn图的算法有质的不同。

1.软硬件介绍

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

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图的费用)：

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等专利。