高维数据检索的一些算法库

高维数据检索的一些算法库

对向量进行索引化是实际使用中的必然需求,按ann-benchmarks上的benchmark看,考察如下的算法库

Annoy
FLANN
scikit-learn: LSHForest, KDTree, BallTree
PANNS
NearPy
KGraph
NMSLIB (Non-Metric Space Library): SWGraph, HNSW, BallTree, MPLSH
hnswlib (a part of nmslib project)
RPForest
FAISS
DolphinnPy
Datasketch
PyNNDescent
MRPT
NGT: ONNG, PANNG
SPTAG
PUFFINN
N2
ScaNN

综合比较来看,常见的annoy算法库是最为中规中矩的,并非是其中最优秀的,比较稳定的而优异的应当是NGT的PANNG算法,还有NMSLIB中的HNSW算法,尤其是NGT的PANNG算法,在Last.fm的50000次测试中表现仍然很优异,召回率很优秀,其它的各项测试中也比较稳健。

从Issue里看到有人指出,如果采用多核进程进行运算,很多结果会有不同,一个典型的是HNSW算法会出现大幅度的提升,hnsw还有一个ivf-hnsw的改进算法,可以用于在20G内存以下的机器上实现不错的结果。

根据这个测试,一些其它算法也在被推荐,例如纯C++的实现的NSG算法,不过已经两年没去跟进了,看作者的github主页上表现性能也相当优秀,并用淘宝的数据做了测试。

还有一个叫Product-Quantization-Tree算法的,虽然作者没有提供图表,但它是一个GPU实现的方案,可能会有不错的性能,但硬件依赖似乎有些过强了,毕竟现在GPU成本不低。

在ANN算法之外的,有个叫libnabo的算法库,声称要普遍比ANN算法更快20%以上,并且支持python。

在这些评测之外的,京东的vearch作为分布式向量搜索系统,按其自身说法,不仅性能优秀,重点是可以进行分布式搜索,提供了restful的请求接口,基本上属于开箱即用,可以直接拿来就行。

而在vearch之外的, Milvus也颇具名声,在GPU的支持下,甚至可以16G的PC上实现轻松的亿级搜索。

常用的Annoy虽然性能中规中矩,但它有一个非常大的优势就是内存占用最小,如果不是极为高频的数据请求,它可以在低内存的机器上表现良好。

三符风云涌

2条评论

刀刀 发布于下午 2:40 - 2020 年 8 月 18 日

真……这你都懂…

hetong007 发布于上午 8:54 - 2021 年 4 月 15 日

还有一个现在比较流行的是 FAISS: https://github.com/facebookresearch/faiss

比较ANN算法也可以参考这里的结果:http://ann-benchmarks.com/

回复 刀刀 取消回复