HNSWLib是一个仅包含头文件的C++库，实现了用于近似最近邻搜索的分层可导航小世界（HNSW）算法。该库旨在无需将查询与每个条目逐一比较，即可在大规模向量数据集合中找到与查询条目相似的条目。它常用于机器学习系统、人工智能应用以及向量数据库中，这些场景对速度和可扩展性要求极高。
HNSWLib所实现的HNSW算法将向量存储在多层图结构中。每个向量成为一个节点，链接将其连接到附近的向量。上层包含较少的节点，充当粗略地图，而底层包含所有节点，用于详细搜索。搜索从上层开始，沿着链接向更接近查询的节点移动，然后在较低层重复该过程，直到识别出一组可能的最近邻。
背景
最近邻搜索问题询问数据集中哪些条目与查询条目最接近。直接搜索会将查询与每个条目进行比较，对于大型数据集来说这会变得缓慢。使用空间树（如k-d树或R树）的精确方法在高维数据中会因维度灾难而失效。近似最近邻方法以精确性换取速度，快速返回接近的条目，而不是保证绝对最近的条目。
HNSW建立在关于小世界网络和可导航图的研究基础上。在小世界图中，大多数节点通过短链的链接相连。Jon Kleinberg关于小世界网络导航的研究影响了后来关于添加使图更易于贪婪导航的链接的研究。HNSW算法通过添加图层的层次结构扩展了早期的可导航小世界方法，这有助于在详细搜索之前找到良好的区域。
算法
HNSWLib使用邻近图，其中附近的向量通过边连接。算法通过这些边在数据集中移动，而不是扫描每个向量。图是分层的：每个向量都出现在底层，而某些向量也出现在更高层，随着层级的上升，向量数量减少。上层支持长距离移动，而下层允许在候选附近进行详细搜索。
典型的搜索从最高层的入口点开始。在每一步，算法检查相邻节点并移动到更接近查询的节点。当该层中没有更近的邻居时，它会下降到下一层。在底层，它探索更广泛的候选集并返回找到的最近候选。这种贪婪导航反复选择局部更好的节点以接近查询点。
构建与参数
HNSW图是增量构建的。插入新向量时，算法为其分配一个最大层，搜索附近的现有节点，并在其出现的每一层中将新节点连接到选定的邻居。实现暴露了控制速度、准确性、内存使用和构建时间之间权衡的参数。更高的图连接提高召回率，但需要更多内存。更大的搜索候选列表提高准确性，但会减慢查询速度。更大的构建候选列表提高图质量，但会减慢索引构建速度。
由于HNSW是近似的，结果可能与精确搜索不同。实际性能取决于数据集特征、距离度量、实现质量和参数设置。基准测试研究发现，基于HNSW的库在近似最近邻方法中表现强劲，尽管最坏情况下的性能可能与常见基准结果不同。
在向量搜索系统中的应用
HNSWLib被用作存储和搜索高维向量的系统中的索引，包括向量数据库、搜索引擎和数据库扩展。典型应用包括语义搜索、推荐系统、图像相似性搜索和检索增强生成。该库与原始HNSW作者相关联，并广泛用于生产环境。
多个软件项目实现或支持HNSW。库包括HNSWLib和FAISS。记录HNSW支持的数据库和搜索系统包括Apache Lucene、Chroma、ClickHouse、DuckDB、MariaDB、Milvus、pgvector、Qdrant和Redis。这些系统利用HNSW在从大型语言模型检索到生成式人工智能管道的应用中实现快速近似搜索。
另见
- 近似最近邻搜索
- 向量数据库
- 局部敏感哈希
- 乘积量化