HNSW: A Hierarchical Navigable Small World for Efficient Nearest Neighbor Search

HNSW is a hierarchical navigable small world graph-based algorithm for nearest neighbor search of vector embeddings. It utilizes a hierarchical structure to speed up the search process. The algorithm builds sparse and dense graph structures at different levels, and searches efficiently from top to bottom. The code is concise, using modern C++ and Eigen for SIMD acceleration, requiring only about 500 lines of code.