最近鄰方法是機器學習中一個非常流行的方法，它的原理很容易理解：鄰近的數據點是相似的數據點，更可能屬于同一分類。然而，在高維空間中快速地應用最近鄰方法，卻是非常有挑戰性的工作。

全球最大的流媒體音樂服務商Spotify需要向上面的海量用戶推薦音樂，其中就用到了最近鄰方法。也就是在高維空間、大型數據集上應用最近鄰方法。

由于維度高、數據規模大，直接應用最近鄰方法并不可行，因此，最佳實踐是使用逼近方法搜索最近鄰。這方面有不少開源庫，比如Spotify開源的Annoy庫。Annoy庫的作者Erik Bernhardsson在開發Annoy的過程中發現，盡管有成百上千的使用逼近方法搜索最近鄰的論文，卻很少能找到實踐方面的比較。因此，Erik開發了ANN-benchmarks，用來評測逼近最近鄰（approximate nearest neighbor，ANN）算法。

評估的實現

Annoy Spotify自家的C++庫（提供Python綁定）。Annoy最突出的特性是支持使用靜態索引文件，這意味著不同進程可以共享索引。

FLANN 加拿大英屬哥倫比亞大學出品的C++庫，提供C、MATLAB、Python、Ruby綁定。

scikit-learn 知名的Python機器學習庫scikit-learn提供了LSHForest、KDTree、BallTree實現。

PANNS 純Python實現。已“退休”，作者建議使用MRPT。

NearPy 純Python實現。基于局部敏感哈希（Locality-sensitive hashing，簡稱LSH，一種降維方法）。

KGraph C++庫，提供Python綁定。基于圖（graph）算法。

NMSLIB (Non-Metric Space Library) C++庫，提供Python綁定，并且支持通過Java或其他任何支持Apache Thrift協議的語言查詢。提供了SWGraph、HNSW、BallTree、MPLSH實現。

hnswlib（NMSLIB項目的一部分） 相比當前NMSLIB版本，hnswlib內存占用更少。

RPForest 純Python實現。主要特性是不需要在模型中儲存所有索引的向量。

FAISS Facebook出品的C++庫，提供可選的GPU支持（基于CUDA）和Python綁定。包含支持搜尋任意大小向量的算法（甚至包括可能無法在RAM中容納的向量）。

DolphinnPy 純Python實現。基于超平面局部敏感哈希算法。

Datasketch 純Python實現。基于MinHash局部敏感哈希算法。

PyNNDescent 純Python實現。基于k-近鄰圖構造（k-neighbor-graph construction）。

MRPT C++庫，提供Python綁定。基于稀疏隨機投影（sparse random projection）和投票（voting）。

NGT: C++庫，提供了Python、Go綁定。提供了PANNG實現。

數據集

ANN-benchmarks提供了一些預先處理好的數據集。

結果

Erik提供了在AWS EC2機器（c5.4xlarge）上運行測試的結果——跑了好幾天才跑完，費用約100美元。

glove-100-angular

sift-128-euclidean

fashion-mnist-784-euclidean

gist-960-euclidean

nytimes-256-angular

glove-25-angular

從以上評測可以看出（越靠上、靠右，成績越好），幾乎在所有數據集上，排名前五的實現為：

HNSW（NMSLIB的低內存占用版本），比Annoy快10倍。

KGraph位于第二，和HNSW的差距不算很大。和HNSW一樣，KGraph也是基于圖（graph）的算法。

SW-graph，源自NWSLIB的另一個基于圖的算法。

FAISS-IVF，源自Facebook的FAISS。

Annoy

在“評估的實現”一節中，我們看到，有不少使用局部敏感哈希（LSH）的庫。這些庫的表現都不是很好。在之前進行的一次評測中，FALCONN表現非常好（唯一表現優良的使用局部敏感哈希的庫）。但是這次評測中，FALCONN看上去退步得很厲害——原因未明。

從這次評測來看，基于圖的算法是當前最先進的算法（名列三甲的算法全都基于圖），特別是HNSW表現突出。