当前位置:   article > 正文

近似最近邻算法查找(ann)--01_近似最近邻搜索anns算法

近似最近邻搜索anns算法

Ann, Approximate Nearest Neighbor的缩写,就是近似最近邻搜索。

在机器学习领域,语义检索,图像识别,推荐系统等方向常涉及到的一个问题是:给定一个向量X=[x1,x2,x3...xn],需要从海量的向量库中找到最相似的前K个向量。通常这些向量的维度很高,对于在线服务用传统的方法查找是非常耗时的,容易使得时延上成为瓶颈,因此业界通用的方式就是将最相似的查找转换成Ann问题

这样查找返回的前K个向量并不一定是最相似的K个向量,衡量Ann算法好不好的一个依据是召回,每次Ann请求返回的K个结果与使用暴力查找的K个结果去比较,如果完全一致,说明是最好的。因为省了搜索时间却没有影响效果。

目前的Ann算法有基于图的,基于树的,基于哈希等,并且有很多关于Ann算法的实现,开源的很多,如annoy, faiss,nmslib, falconn等。下图是一些算法及其实现在搜索效率和召回的一个性能评测。

ann-benchmarks

更详细的一些测试在这个网站有数据 http://ann-benchmarks.com。作者比较了不同的距离度量方式及在不同数据集的效果。

基于图的算法(hnsw)其实在评测上看起来是最好的, 但是其耗费比较多内存,树的方法在维度大时会变成暴力搜索,其它方法也有不同的特点。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/966579
推荐阅读
相关标签
  

闽ICP备14008679号