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

对向量进行索引化是实际使用中的必然需求,按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虽然性能中规中矩,但它有一个非常大的优势就是内存占用最小,如果不是极为高频的数据请求,它可以在低内存的机器上表现良好。