Some Algorithm Libraries for High-Dimensional Data Retrieval

Indexing vectors is an inevitable requirement in practical use. Judging by the benchmarks on ann-benchmarks, consider the following algorithm libraries:

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

Looking at the overall comparison, the well-known Annoy library is the most middling of the bunch — not the best among them. The more stable and excellent performers should be NGT's PANNG algorithm and NMSLIB's HNSW algorithm. In particular, NGT's PANNG algorithm still performs excellently in the 50,000-query Last.fm test, with excellent recall, and is also quite solid across other tests.

From the issue trackers one can see that someone pointed out that if multi-core processing is used for computation, many results will differ; a typical case is that the HNSW algorithm shows a substantial improvement. Hnsw also has an ivf-hnsw improved variant that can deliver good results on machines with under 20 GB of RAM.

According to this test, several other algorithms are also recommended — for example, the NSG algorithm implemented in pure C++. I haven't followed it in two years, but on the author's GitHub page the reported performance also looks quite impressive, and it has been tested with Taobao data.

There is also something called the Product-Quantization-Tree algorithm. Although the author did not provide charts, it is a GPU-based solution that may deliver good performance — though the hardware dependency seems somewhat excessive, given that GPUs are not cheap.

Beyond the ANN algorithms, there is an algorithm library called libnabo, which claims to be generally more than 20% faster than ANN algorithms and supports Python.

Beyond these evaluations, JD's Vearch, as a distributed vector search system, claims not only excellent performance but, more importantly, the ability to do distributed search. It provides a RESTful API and is essentially ready out of the box — you can just pick it up and use it.

Outside Vearch, Milvus is also quite well known. With GPU support, it can even easily handle hundred-million-scale searches on a PC with 16 GB of RAM.

The commonly used Annoy, while middling in performance, has one very large advantage: the smallest memory footprint. If the data queries are not extremely high-frequency, it can perform well on low-memory machines.