向量相似度检索，即根据一个向量Q从的向量库中寻找TopK个与Q最相似或者距离最近的向量（K-Nearest Neighbor，KNN），其在工业中有着广泛的应用场景，比如图像检索、文本语义检索以及推荐系统中基于User与Item的 ding向量召回等。

在生产环境中，被查找的向量库往往是海量，甚至超过了内存的限制，而且面临着高并发与低延迟的需求，通常会关注近似近邻（Approximate Nearest Neighbor，

ANN）问题，通过牺牲一定的召回精度，满足对内存和召回效率的需求。

在高维空间中快速进行最近邻搜索已成为一个越来越重要的问题， Erik Bernhardsson 创建了一个 ANN 基准测试工具- ANN-Benchmarks

[https://github.com/erikbern/ann-benchmarks]，下图是各种ANN算法在glove-100-angular数据集上的表现。

上图中涉及的ANN算法：

• 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, QG

• SPTAG

• PUFFINN

• N2

• ScaNN

• Elastiknn

• OpenDistro Elasticsearch KNN

• DiskANN: Vamana, Vamana-PQ

• Vespa

根据实现方式，ANNS算法主要可分为：

• 基于树的ANN

• 基于哈希的ANN

• 基于量化的ANN

• 基于图的ANN

• ...

不同的距离计算方式比较向量间的距离。选择合适的距离计算方式能极大地提高数据分类和聚类性能。

• 欧氏距离 (L2)

• 内积 (IP)

• 杰卡德距离 (Jaccard)

• 谷本距离 (Tanimoto)

• 汉明距离 (Hamming)

• ...