HNSW(Hierarchical Navigable Small World)索引的原理如下:

一、总体结构

HNSW 构建了一个多层的图结构。

  1. 高层:包含少量的节点,但连接比较稀疏,用于快速缩小搜索范围。
  2. 底层:节点数量多,连接相对密集,提供更精确的搜索结果。

二、图的构建

  1. 插入节点
  2. 随机选择一个最高层作为起始层。
  3. 在当前层中找到距离新节点最近的邻居节点集合。
  4. 将新节点与邻居节点建立连接。
  5. 逐步下降到下一层,重复上述过程,直到最底层。

  6. 连接策略

  7. 对于每个节点,维护一个固定大小的邻居列表。新节点插入时,会根据距离远近更新邻居列表,保证邻居节点是相对较近的。

三、搜索过程

  1. 从最高层开始搜索。
  2. 在当前层找到距离查询节点最近的节点。
  3. 以该节点为中心,在其邻居列表中继续搜索,找到更近的节点。
  4. 逐步下降到下一层。
  5. 将上一层找到的最近节点作为下一层的起始点。
  6. 重复在当前层的搜索过程,直到最底层。
  7. 在最底层进行精确搜索。
  8. 最终在最底层找到距离查询节点最近的若干个节点作为近似最近邻结果。

HNSW 索引通过这种分层的图结构和高效的搜索策略,能够在大规模高维数据集中快速找到近似最近邻,具有较高的效率和准确性。