基础的索引构建算法

# KNN 图

# NN-Descent

# NN-DescentFULL

# NSW

找到节点𝑣𝑖最近邻的 𝑓 个邻居，建立𝑣𝑖和这些邻居的边连接

# HNSW

确定一个 I,p 从 0 到 I 都会出现

第一阶段：从顶层到第 I+1 层遍历，ef=1，ep = 唯一找到的点；
第二阶段：
9. 从第 I 层到 0 层遍历，ef,ep=w (ef 个最近邻节点的集合)

10.W 选 M 个节点于 q 连接，两种方法
SIMPLE 的：

直接选最近的
HEURISTIC 的：

要连接的点 p1（p1，q) 要比（所有？还是只需一个？应该是所有）原有的连接点 p2，(p1,p2) 小才允许连接，（p1，q)<(p1,p2)
为了在不同方向上选择邻居，从而避免邻居扎堆 “高速公路”
最后检查连接的邻居，用上面的算法缩减它们的邻居个数至 Wmax

# GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction

# 构建 NSG 图

这个算法是一个基于 GPU 的近邻搜索图（NSW，Navigable Small World Graph）构建算法。该算法旨在通过平行处理来构建一个包含点集合的近邻图，其中每个节点的度数在指定的最小度数 (d_{min}) 和最大度数 (d_{max}) 之间。具体步骤如下：

# 输入：

• P: 一个点的集合。
• (d_{min}): 图中节点的最小度数。
• (d_{max}): 图中节点的最大度数。

# 输出：

• G: 一个近邻图 (G = (V, E))，包含节点集 (V) 和边集 (E)。

# 步骤：

1. 划分点集合：
   • 将点集合 (P) 划分为互不相交的子集 (P_0, P_1, \ldots, P_t)。
2. 初始化图子集：
   • 并行（跨 GPU 块）初始化每个划分 (P_i) 的空图子集 (G_i)。
3. 局部邻居搜索和更新：
   • 对于划分 (P_i) 中的每个点 (v_{ij})：
     • 在局部图子集 (G_i) 中找到初始邻居 (v_{ij}.N) 和 (v_{ij}.N')，确保度数不少于 (d_{min})。
     • 对于 (v_{ij}) 的每个邻居 (u_{ij})：
       • 在块内并行，将 (v_{ij}) 添加到 (u_{ij}) 的邻居中。
4. 全局邻居搜索和更新：
   • 对于每个划分 (i) 从 1 到 (t)：
     • 初始化空边集 (E) 和索引集 (I)。
     • 并行（跨 GPU 块）处理 (G_i) 中的每个点 (v_{ij})：
       • 更新 (v_{ij}.N)，通过搜索全局图 (G_0) 确保度数不少于 (d_{min})。
       • 在块内并行，将 (v_{ij}.N) 与 (v_{ij}.N') 合并。
       • 对于 (v_{ij}) 的每个邻居 (u_{ij})：
         • 在块内并行，将边 ((u_{ij} \rightarrow v_{ij}, \delta (u_{ij}, v_{ij}))) 添加到 (E) 中。
     • 并行（跨 GPU 块）执行 gather-scatter 操作以更新 (E) 和 (I)。
     • 并行（跨和块内）更新 (u_{ij}) 的邻居，包含从 (E) 中收集的新边。
5. 返回最终图：
   • 返回全局图 (G_0)，它现在表示包含更新后的边和邻居的完整近邻图。

# 总结：

该算法有效地利用 GPU 的并行处理能力对点集进行划分、执行局部和全局邻居搜索，并更新图结构。这种方法确保在构建近邻图的同时维持节点度数的约束 (d_{min}) 和 (d_{max})。

# 关键概念：

• 并行处理：利用 GPU 块和线程并行执行操作，加速计算过程。
• 邻居搜索：为每个点找到并更新邻居以构建图。
• Gather-Scatter 操作：一种高效分布和收集数据的并行技术。

# 后向边更新

前向边：u 先插入，v 后插入，v 发出 knn 搜索，v->u 是前向边
** 后向边：**v 先插入，u 后插入，u 发出 knn 搜索，v->u 是后向边

合并子图时，算法 12-14 行，更新了前向边，但是后向边更新时可能两个 vij 同时搜索到一个点 u，所以先把距离记录到 CSR 表中
[[双调排序]]

# Fast k-NN graph construction by GPU based NN-Descent