分层可导航小世界（HNSW）是一种用于近似最近邻搜索的算法。它用于在大型集合中查找与查询项相似的项，而无需将查询与每一项逐一比较。该算法常用于搜索向量数据，其中文档、图像、歌曲或用户配置文件等项被表示为称为向量的数字列表。根据生成向量的模型，具有相似向量的项被视为相似项，而HNSW提供了一种快速搜索这些向量的方法，尤其是在大型数据集中。
HNSW将向量存储在图中。每个向量是一个节点，链接将其连接到一些附近的向量上。该图具有多个层：上层包含较少节点，并充当粗略地图，而底层包含所有节点，并提供更详细的视图。搜索从上层开始，沿链接向更接近查询的节点移动，然后在较低层重复该过程，直到找到一组可能的最近邻居。
背景
最近邻搜索问题询问数据集中哪些项与查询项最接近。直接搜索可以将查询与数据集中的每一项进行比较，但当数据集很大时，这会变得缓慢。基于空间树的精确搜索方法，如k-d树和R-tree，对于高维数据也可能变得不太有效，这个问题通常与维度灾难相关。近似最近邻方法以一些精确性换取速度或更低资源使用量。它们不是始终保证返回最接近的精确项，而是尝试快速返回接近的项。其他近似方法包括局部敏感哈希和乘积量化等
HNSW建立在关于小世界网络和可导航图的研究之上。在小世界图中，大多数节点可以通过短链的链接从其他节点到达。在可导航图中，搜索过程可以使用局部信息向目标移动等Jon Kleinberg关于小世界网络导航的研究是该研究领域的一个重要例子等后来的研究探讨了添加链接的方法，使图更容易进行贪婪导航等
HNSW算法通过添加图层的层次结构，扩展了早期用于相似性搜索的可导航小世界方法等这种层次结构帮助算法在底层进行更详细搜索之前，找到图的良好区域等
算法
HNSW基于邻近图等在此图中，附近的向量通过边连接等算法使用这些边在数据集中移动，而不是扫描每个向量等图是分层的等每个向量都出现在底层中等一些向量也被放置在较高层中，随着层向上，出现的向量越来越少等上层允许跨数据集进行长距离移动，而下层允许在接近有希望的候选者附近进行更详细的搜索等
典型搜索过程如下：
- 搜索从最高层的入口点开始等
- 在每一步，算法查看相邻节点，并移动到更接近查询的邻居等
- 当在该层找不到更近的邻居时，它向下移动到下一层等
- 在底层，它探索更广泛的候选节点集，并返回找到的最近候选者等
这种搜索策略通常被描述为贪婪导航等算法反复选择局部更好的节点，利用图结构接近查询点等
构建和参数
HNSW图是增量构建的等当插入新向量时，算法为其分配一个最大层，搜索附近的现有节点，并将新节点连接到其出现的每一层中的选定邻居等实现通常公开控制速度、准确性、内存使用和构建时间之间权衡的参数等较高的图连接数可以提高召回率，但需要更多内存等较大的搜索候选列表可以提高准确性，但会使查询变慢等较大的构建候选列表可以提高图的质量，但会使索引构建变慢等
由于HNSW是近似的，其结果并不总是与完全精确搜索相同等其实际性能取决于数据集、距离度量、实现和参数设置等基准测试研究发现，基于HNSW的库在近似最近邻方法中是表现强劲的，尽管最坏情况下的性能可能与常见基准数据集上的性能有所不同等
在向量搜索系统中的使用
HNSW被用作存储和搜索高维向量的系统中的索引等这些系统包括向量数据库、搜索引擎和数据库扩展等典型用途包括语义搜索、推荐系统、图像相似性搜索和检索增强生成，后者通常应用于生成式AI和大型语言模型管道中等
多个软件项目实现或支持HNSW等库包括hnswlib，它与原始HNSW作者相关，以及FAISS等支持HNSW的数据库和搜索系统包括Apache Lucene、Chroma、ClickHouse、DuckDB、MariaDB、Milvus、pgvector、Qdrant和Redis等这些工具通常部署在Amazon Web Services、Microsoft Azure和Google Cloud等云平台上，用于生产机器学习工作负载等
参见
- 近似最近邻搜索等
- 局部敏感哈希等
- 乘积量化等