并行与分布式系统中的并行K-最近邻图构建：基于局部敏感哈希（LSH）的近似并行KNN图构建算法
字数 5462 2025-12-19 18:41:26

并行与分布式系统中的并行K-最近邻图构建：基于局部敏感哈希（LSH）的近似并行KNN图构建算法

题目描述

在数据科学、机器学习、信息检索和推荐系统中，经常需要为高维数据集（如向量集合）构建一个 K-最近邻（KNN）图。在这个图中，每个数据点（向量）对应一个节点，每个节点通过边连接到与其最相似的 K 个其他节点（即欧氏距离或其他度量下最近的 K 个向量）。精确计算 KNN 图需要比较所有点对，时间复杂度为 O(N²D)，其中 N 是数据点的数量，D 是维度。这在海量高维数据上是不可行的。

我们的任务是设计一个并行与分布式算法，能够高效地为大规模高维数据集构建一个近似 KNN 图。核心要求是：

  1. 可并行性：算法必须能在多核、多机（如集群）上高效执行，充分利用计算资源。
  2. 可扩展性：算法的时间复杂度应明显低于 O(N²)，且内存占用可控，以适应大规模 N。
  3. 近似质量：结果不必是完全精确的 KNN 列表，但应能返回高质量的近似最近邻，保证在召回率（Recall）和精度（Precision）之间取得良好平衡。

我们将重点关注基于局部敏感哈希（Locality Sensitive Hashing, LSH） 的近似并行 KNN 图构建算法。LSH 的核心思想是：哈希函数经过特殊设计，使得空间中距离较近的点（相似点）有更高概率被哈希到同一个桶（Bucket）中，而距离较远的点被哈希到同一个桶的概率较低。这使我们能够将“在整个数据集中搜索最近邻”的问题，转化为“在每个哈希桶内进行搜索”的问题，从而大幅降低比较的次数。

解题过程循序渐进讲解

步骤 1：理解局部敏感哈希（LSH）的基本原理

LSH 不是一个单一的哈希函数，而是一个函数族 ℋ。对于一个特定的距离度量（如欧氏距离），LSH 函数族 ℂ 满足以下性质：

  • 局部敏感性：如果两点 x, y 的距离 d(x, y) ≤ R，则它们被随机选中的哈希函数 h ∈ ℂ 哈希到相同值的概率至少是 p1。
  • 距离放大：如果两点 x, y 的距离 d(x, y) ≥ cR (c > 1)，则它们被哈希到相同值的概率至多是 p2，且 p1 > p2。

关键思路：通过设计这样的哈希函数，我们可以将“距离相近”的点聚集到相同的哈希桶中。为了增加聚集的准确性和召回率，我们通常使用以下两种技术：

  1. 增加哈希表数量（L）：构建 L 个独立的哈希表，每个表使用一组（通常由 K 个基本 LSH 函数串联组成）不同的哈希函数。一个点会被插入到 L 个表中的 L 个桶中。查询时，我们检查查询点在这 L 个桶中的所有候选点。这增加了找到真正近邻的概率（提高召回率）。
  2. 增加哈希键长度（K）：在每个哈希表中，我们使用 K 个独立的 LSH 函数，将它们的输出串联起来作为最终的桶索引。这要求点必须在所有 K 个函数上都一致才能落入同一个桶，这使得桶内的点更加相似（提高精度），但也可能漏掉一些较近的点（降低召回率）。通过调整 L 和 K，可以在召回率和计算效率之间进行权衡。

对于欧氏距离，一个经典的 LSH 函数族是 p-stable 分布 LSH（通常使用正态分布）。其基本哈希函数为：
h_{a, b}(v) = ⌊(a·v + b) / w⌋
其中：

  • v 是 D 维输入向量。
  • a 是一个 D 维随机向量，每个分量独立服从标准正态分布 N(0, 1)。
  • b 是一个在 [0, w) 范围内均匀采样的随机数，w 是“窗口”或“桶宽”参数。
  • ⌊·⌋ 是向下取整函数。

步骤 2：串行 LSH-KNN 图构建算法概述

在并行化之前，我们先理解单机串行的流程：

  1. 初始化 L 个哈希表：对于 l = 1 到 L：

    • 生成 K 个随机的 (a, b) 对，构成一个哈希函数组 g_l(v) = [h_{a1, b1}(v), h_{a2, b2}(v), ..., h_{aK, bK}(v)]。
    • 初始化一个空的哈希表（字典）T_l，键是 K 元组（哈希值），值是点的 ID 列表。

  2. 索引构建阶段：对于数据集中的每个点 v_i (i=1..N)：

    • 对于每个哈希表 T_l (l=1..L)，计算其哈希键 key_l = g_l(v_i)。
    • 将点 ID i 追加到 T_l[key_l] 对应的桶列表中。

  3. 候选生成与图构建阶段：初始化一个空的邻接表 Graph，为每个点预留一个候选邻居列表。

    • 对于每个点 v_i：
      • 初始化一个空的候选点集合 Candidates（或使用一个位图/布隆过滤器去重）。
      • 对于每个哈希表 T_l：
        • 计算 key_l = g_l(v_i)。
        • 将 T_l[key_l] 桶中所有其他点的 ID 加入到 Candidates 中。
      • 去重：Candidates 中可能包含重复的点（因为一个点可能出现在 v_i 的多个桶中）。
      • 精确距离计算与排序：对于 Candidates 中的每个候选点 v_j，计算精确的距离 d(v_i, v_j)。
      • 选取 Top-K：从这些计算过精确距离的候选点中，选出距离最小的 K 个，作为点 v_i 在 KNN 图中的邻居，存入 Graph[i]。

复杂度分析：串行算法避免了 O(N²) 的全量比较。其主要成本在于：1) 索引构建 O(N L K D)；2) 候选生成（依赖于 LSH 参数，理想情况下远小于 N）；3) 精确距离计算（|Candidates| * D）。通过调整 L 和 K，可以控制候选集大小和构建质量。

步骤 3：并行化策略设计（数据并行）

我们的并行化将遵循 SPMD（单程序多数据） 和 数据并行 模型。假设我们有 P 个处理器（或工作进程）。

  • 数据划分：最简单有效的方式是将 N 个数据点近似均匀地划分给 P 个处理器。每个处理器 p 获得一个数据子集 S_p，满足 |S_p| ≈ N/P，且所有 S_p 互不相交，并集为全集。
  • 目标：每个处理器 p 负责为其拥有的点集 S_p 中的每个点，找到其在全局数据集中的近似 K 个最近邻。

步骤 4：并行 LSH-KNN 图构建算法详解

我们将算法分为几个阶段，并说明每个阶段如何并行与通信。

阶段 0：参数广播与哈希函数生成（预处理）

  • 主进程（或通过约定方式）确定 LSH 参数：哈希表数量 L，每个哈希函数的键长度 K，桶宽 w。
  • 主进程 生成 L * K 个全局共享的随机向量 a 和随机偏移 b。关键：这些 (a, b) 对必须在所有 P 个处理器上保持一致，否则哈希计算会不一致。
  • 并行操作：将这些全局参数（L, K, w, 以及所有 (a, b) 对）广播到所有处理器。每个处理器都存储一份相同的副本。

阶段 1：并行本地索引构建

  • 每个处理器 p 为其本地数据子集 S_p 中的每个点 v_i，计算它在 L 个哈希表上的哈希键 {g_l(v_i)}_{l=1..L}。
  • 在处理器 p 内部，为每个哈希表 l 维护一个本地哈希表 T_{p, l}。这是一个映射：哈希键 -> 本地点ID列表。
  • 处理器 p 将其本地每个点 v_i 的 ID，插入到对应的 L 个本地哈希表 T_{p, l} 的相应桶中。
  • 此阶段无进程间通信，是完全并行的。

阶段 2：全局桶信息收集与分发（关键通信步骤）
为了能让处理器 p 为其本地点 v_i 生成候选集，它需要知道全局有哪些点（分布在所有处理器上）和 v_i 在同一个哈希桶中。

  • 方法：我们采用 “All-to-All” 通信 模式，但基于哈希键进行聚合。
  • 具体步骤：
    1. 本地桶信息打包：每个处理器 p 遍历其 L 个本地哈希表 T_{p, l}。对于每个哈希表 l 中的每个桶（哈希键 key），处理器 p 知道有哪几个本地点的 ID 在这个桶里。我们将这个信息打包成消息：(l, key, 本地点ID列表)。
    2. 基于哈希键的全局重分布：
      • 我们设计一个全局的哈希路由函数 R(l, key) -> processor_id。这个函数将特定的 (l, key) 对映射到一个指定的目标处理器。例如，可以使用一个简单的哈希：target_rank = (hash(l, key) mod P)。关键是，对于同一个 (l, key)，所有处理器必须计算出相同的 target_rank。
      • 处理器 p 将其打包的所有消息 (l, key, local_point_ids)，根据 R(l, key) 发送到对应的目标处理器。
    3. 接收与合并：每个处理器 q 会从所有其他处理器收到一系列消息。对于每一条收到的 (l, key, point_ids_from_sender) 消息，处理器 q 在本地维护一个全局桶目录 G_q。G_q 的结构类似于一个字典，键是 (l, key)，值是全局点ID列表。处理器 q 将收到的 point_ids 合并到 G_q[(l, key)] 中。
  • 完成后：每个处理器 q 现在拥有了全局桶目录 G_q 的一个子集。具体来说，它只负责存储那些通过 R(l, key) 映射到自身的 (l, key) 所对应的全局桶成员列表。所有处理器的 G_* 合起来，就构成了完整的全局桶索引的分布式存储。

阶段 3：并行候选生成与精确搜索

  • 每个处理器 p 遍历其本地数据子集 S_p 中的每个点 v_i。
  • 候选生成：
    • 对于 v_i，计算其 L 个哈希键 {key_l}。
    • 对于每个哈希键 key_l，需要找到对应的全局桶成员列表。根据我们阶段 2 的设计，这个列表存储在处理器 R(l, key_l) 上。
    • 因此，处理器 p 需要向多个其他处理器（具体是那些 R(l, key_l) 对应的处理器）发送请求，询问：“请把桶 (l, key_l) 的全局成员列表发给我”。
    • 这引发了一轮点对点通信。为了提高效率，处理器 p 可以先将对同一个目标处理器 r 的多个 (l, key) 请求批量打包，再发送。
    • 目标处理器 r 收到请求后，从其本地存储的全局桶目录 G_r 中查找对应的成员列表，发回给请求者 p。
    • 处理器 p 收集到 v_i 在所有 L 个桶中的候选点 ID 列表后，进行去重，得到候选集 Candidates_i。
  • 精确距离计算与 Top-K 选择：
    • 处理器 p 现在需要计算 v_i 与 Candidates_i 中每个候选点的精确距离。问题是，候选点 v_j 的数据（向量）可能存储在另一个处理器上。
    • 因此，处理器 p 需要向持有这些候选点数据的处理器发起数据获取请求。
    • 这又是一轮点对点通信。同样可以进行批量请求优化。
    • 收到所有需要的向量数据后，处理器 p 在本地计算 v_i 与每个候选点的精确距离。
    • 最后，处理器 p 从这些距离中选出最小的 K 个，将对应的点 ID 作为 v_i 的近似 K 近邻，存入最终的本地图结果中。

阶段 4：结果收集（可选）

  • 如果需要一个全局统一的 KNN 图，可以将所有处理器上的本地结果收集到一个根处理器。

步骤 5：算法优化与讨论

  1. 通信优化：阶段 2 和阶段 3 的通信是主要开销。

    • 阶段 2 优化：可以使用高效的 All-to-All 通信原语（如 MPI_Alltoallv）来实现桶信息的全局重分布，避免显式的点对点发送循环。
    • 阶段 3 优化：可以将“请求桶列表”和“请求候选点向量数据”两轮通信合并或流水线化。也可以使用布隆过滤器在本地对候选集进行预过滤，减少需要获取向量的数量。

  2. 负载均衡：

    • 数据划分不均或某些哈希桶特别大都会导致负载不均。
    • 数据划分：可以采用基于空间填充曲线（如 Z-order）或基于聚类中心的划分，使相似点尽量在同一分区，可能减少候选集大小。
    • 桶重分布：阶段 2 的路由函数 R(l, key) 应设计成尽量均匀地将 (l, key) 对分散到所有处理器上，避免单个处理器存储过大的全局桶目录。

  3. 近似质量与参数调优：算法的质量（召回率）和效率取决于 L 和 K。

    • 增加 L：增加哈希表数量，提高召回率，但会增加索引大小、通信量和候选集大小。
    • 增加 K：增加哈希键长度，提高桶内点的相似性（精度），但会降低召回率，因为点落入相同桶的概率降低。
    • 通常需要通过实验在目标数据集上进行调整，以达到所需的召回率/精度与运行时间的平衡。

  4. 多表 vs 复合哈希：为了减少存储和通信开销，有时会采用“复合哈希”或“调和”的方式，用更少的哈希函数生成更多的“虚拟”哈希表，但这会增加算法复杂性。

总结

这个基于 LSH 的并行 KNN 图构建算法，通过局部敏感哈希将全局近邻搜索问题转化为局部桶内搜索，并利用数据并行和基于哈希的全局桶信息分发策略，实现了算法的并行化。其核心在于通过两阶段通信（全局桶信息收集、候选点数据获取）来协调分布式数据和计算，最终使每个处理器能独立为其本地数据点找到高质量的近似 K 近邻。该算法是大规模高维数据近似相似性搜索和图构建的经典并行范例。

并行与分布式系统中的并行K-最近邻图构建：基于局部敏感哈希（LSH）的近似并行KNN图构建算法 题目描述 在数据科学、机器学习、信息检索和推荐系统中，经常需要为高维数据集（如向量集合）构建一个 K-最近邻（KNN）图。在这个图中，每个数据点（向量）对应一个节点，每个节点通过边连接到与其最相似的 K 个其他节点（即欧氏距离或其他度量下最近的 K 个向量）。精确计算 KNN 图需要比较所有点对，时间复杂度为 O(N²D)，其中 N 是数据点的数量，D 是维度。这在海量高维数据上是不可行的。 我们的任务是设计一个 并行与分布式算法 ，能够高效地为大规模高维数据集构建一个 近似 KNN 图 。核心要求是： 可并行性 ：算法必须能在多核、多机（如集群）上高效执行，充分利用计算资源。 可扩展性 ：算法的时间复杂度应明显低于 O(N²)，且内存占用可控，以适应大规模 N。 近似质量 ：结果不必是完全精确的 KNN 列表，但应能返回高质量的近似最近邻，保证在召回率（Recall）和精度（Precision）之间取得良好平衡。 我们将重点关注基于 局部敏感哈希（Locality Sensitive Hashing, LSH） 的近似并行 KNN 图构建算法。LSH 的核心思想是：哈希函数经过特殊设计，使得空间中距离较近的点（相似点）有 更高概率 被哈希到同一个桶（Bucket）中，而距离较远的点被哈希到同一个桶的概率较低。这使我们能够将“在整个数据集中搜索最近邻”的问题，转化为“在每个哈希桶内进行搜索”的问题，从而大幅降低比较的次数。 解题过程循序渐进讲解 步骤 1：理解局部敏感哈希（LSH）的基本原理 LSH 不是一个单一的哈希函数，而是一个函数族 ℋ。对于一个特定的距离度量（如欧氏距离），LSH 函数族 ℂ 满足以下性质： 局部敏感性 ：如果两点 x, y 的距离 d(x, y) ≤ R，则它们被随机选中的哈希函数 h ∈ ℂ 哈希到相同值的概率至少是 p1。 距离放大 ：如果两点 x, y 的距离 d(x, y) ≥ cR (c > 1)，则它们被哈希到相同值的概率至多是 p2，且 p1 > p2。 关键思路 ：通过设计这样的哈希函数，我们可以将“距离相近”的点聚集到相同的哈希桶中。为了增加聚集的准确性和召回率，我们通常使用以下两种技术： 增加哈希表数量（L） ：构建 L 个独立的哈希表，每个表使用一组（通常由 K 个基本 LSH 函数串联组成）不同的哈希函数。一个点会被插入到 L 个表中的 L 个桶中。查询时，我们检查查询点在这 L 个桶中的所有候选点。这增加了找到真正近邻的概率（提高召回率）。 增加哈希键长度（K） ：在每个哈希表中，我们使用 K 个独立的 LSH 函数，将它们的输出串联起来作为最终的桶索引。这要求点必须在所有 K 个函数上都一致才能落入同一个桶，这使得桶内的点更加相似（提高精度），但也可能漏掉一些较近的点（降低召回率）。通过调整 L 和 K，可以在召回率和计算效率之间进行权衡。 对于欧氏距离 ，一个经典的 LSH 函数族是 p-stable 分布 LSH （通常使用正态分布）。其基本哈希函数为： h_ {a, b}(v) = ⌊(a·v + b) / w⌋ 其中： v 是 D 维输入向量。 a 是一个 D 维随机向量，每个分量独立服从标准正态分布 N(0, 1)。 b 是一个在 [ 0, w) 范围内均匀采样的随机数，w 是“窗口”或“桶宽”参数。 ⌊·⌋ 是向下取整函数。 步骤 2：串行 LSH-KNN 图构建算法概述 在并行化之前，我们先理解单机串行的流程： 初始化 L 个哈希表 ：对于 l = 1 到 L： 生成 K 个随机的 (a, b) 对，构成一个哈希函数组 g_ l(v) = [ h_ {a1, b1}(v), h_ {a2, b2}(v), ..., h_ {aK, bK}(v) ]。 初始化一个空的哈希表（字典）T_ l，键是 K 元组（哈希值），值是点的 ID 列表。 索引构建阶段 ：对于数据集中的每个点 v_ i (i=1..N)： 对于每个哈希表 T_ l (l=1..L)，计算其哈希键 key_ l = g_ l(v_ i)。 将点 ID i 追加到 T_ l[ key_ l ] 对应的桶列表中。 候选生成与图构建阶段 ：初始化一个空的邻接表 Graph，为每个点预留一个候选邻居列表。 对于每个点 v_ i： 初始化一个空的候选点集合 Candidates（或使用一个位图/布隆过滤器去重）。 对于每个哈希表 T_ l： 计算 key_ l = g_ l(v_ i)。 将 T_ l[ key_ l] 桶中 所有其他点 的 ID 加入到 Candidates 中。 去重 ：Candidates 中可能包含重复的点（因为一个点可能出现在 v_ i 的多个桶中）。 精确距离计算与排序 ：对于 Candidates 中的每个候选点 v_ j，计算精确的距离 d(v_ i, v_ j)。 选取 Top-K ：从这些计算过精确距离的候选点中，选出距离最小的 K 个，作为点 v_ i 在 KNN 图中的邻居，存入 Graph[ i ]。 复杂度分析 ：串行算法避免了 O(N²) 的全量比较。其主要成本在于：1) 索引构建 O(N L K D)；2) 候选生成（依赖于 LSH 参数，理想情况下远小于 N）；3) 精确距离计算（|Candidates| * D）。通过调整 L 和 K，可以控制候选集大小和构建质量。 步骤 3：并行化策略设计（数据并行） 我们的并行化将遵循 SPMD（单程序多数据） 和 数据并行 模型。假设我们有 P 个处理器（或工作进程）。 数据划分 ：最简单有效的方式是将 N 个数据点 近似均匀地划分 给 P 个处理器。每个处理器 p 获得一个数据子集 S_ p，满足 |S_ p| ≈ N/P，且所有 S_ p 互不相交，并集为全集。 目标 ：每个处理器 p 负责为其拥有的点集 S_ p 中的每个点，找到其在 全局数据集 中的近似 K 个最近邻。 步骤 4：并行 LSH-KNN 图构建算法详解 我们将算法分为几个阶段，并说明每个阶段如何并行与通信。 阶段 0：参数广播与哈希函数生成（预处理） 主进程 （或通过约定方式）确定 LSH 参数：哈希表数量 L，每个哈希函数的键长度 K，桶宽 w。 主进程 生成 L * K 个全局共享的随机向量 a 和随机偏移 b。 关键 ：这些 (a, b) 对必须在所有 P 个处理器上保持一致，否则哈希计算会不一致。 并行操作 ：将这些全局参数（L, K, w, 以及所有 (a, b) 对）广播到所有处理器。每个处理器都存储一份相同的副本。 阶段 1：并行本地索引构建 每个处理器 p 为其本地数据子集 S_ p 中的每个点 v_ i，计算它在 L 个哈希表上的哈希键 {g_ l(v_ i)}_ {l=1..L}。 在处理器 p 内部，为每个哈希表 l 维护一个 本地哈希表 T_ {p, l}。这是一个映射： 哈希键 -> 本地点ID列表 。 处理器 p 将其本地每个点 v_ i 的 ID，插入到对应的 L 个本地哈希表 T_ {p, l} 的相应桶中。 此阶段无进程间通信 ，是完全并行的。 阶段 2：全局桶信息收集与分发（关键通信步骤） 为了能让处理器 p 为其本地点 v_ i 生成候选集，它需要知道 全局 有哪些点（分布在所有处理器上）和 v_ i 在同一个哈希桶中。 方法 ：我们采用 “All-to-All” 通信 模式，但基于哈希键进行聚合。 具体步骤 ： 本地桶信息打包 ：每个处理器 p 遍历其 L 个本地哈希表 T_ {p, l}。对于每个哈希表 l 中的每个桶（哈希键 key），处理器 p 知道有哪几个本地点的 ID 在这个桶里。我们将这个信息打包成消息： (l, key, 本地点ID列表) 。 基于哈希键的全局重分布 ： 我们设计一个 全局的哈希路由函数 R(l, key) -> processor_ id。这个函数将特定的 (l, key) 对映射到一个 指定的目标处理器 。例如，可以使用一个简单的哈希： target_rank = (hash(l, key) mod P) 。 关键是 ，对于同一个 (l, key)，所有处理器必须计算出相同的 target_ rank。 处理器 p 将其打包的所有消息 (l, key, local_point_ids) ，根据 R(l, key) 发送到对应的目标处理器。 接收与合并 ：每个处理器 q 会从所有其他处理器收到一系列消息。对于每一条收到的 (l, key, point_ids_from_sender) 消息，处理器 q 在本地维护一个 全局桶目录 G_ q。G_ q 的结构类似于一个字典，键是 (l, key)，值是 全局点ID列表 。处理器 q 将收到的 point_ ids 合并到 G_ q[ (l, key) ] 中。 完成后 ：每个处理器 q 现在拥有了全局桶目录 G_ q 的一个 子集 。具体来说，它只负责存储那些通过 R(l, key) 映射到自身的 (l, key) 所对应的 全局桶成员列表 。所有处理器的 G_* 合起来，就构成了完整的全局桶索引的分布式存储。 阶段 3：并行候选生成与精确搜索 每个处理器 p 遍历其本地数据子集 S_ p 中的每个点 v_ i。 候选生成 ： 对于 v_ i，计算其 L 个哈希键 {key_ l}。 对于每个哈希键 key_ l，需要找到对应的全局桶成员列表。根据我们阶段 2 的设计，这个列表存储在处理器 R(l, key_ l) 上。 因此，处理器 p 需要向 多个其他处理器 （具体是那些 R(l, key_ l) 对应的处理器）发送请求，询问：“请把桶 (l, key_ l) 的全局成员列表发给我”。 这引发了一轮 点对点通信 。为了提高效率，处理器 p 可以先将对同一个目标处理器 r 的多个 (l, key) 请求批量打包，再发送。 目标处理器 r 收到请求后，从其本地存储的全局桶目录 G_ r 中查找对应的成员列表，发回给请求者 p。 处理器 p 收集到 v_ i 在所有 L 个桶中的候选点 ID 列表后，进行 去重 ，得到候选集 Candidates_ i。 精确距离计算与 Top-K 选择 ： 处理器 p 现在需要计算 v_ i 与 Candidates_ i 中每个候选点的精确距离。问题是，候选点 v_ j 的数据（向量）可能存储在另一个处理器上。 因此，处理器 p 需要向持有这些候选点数据的处理器发起 数据获取请求 。 这又是一轮点对点通信。同样可以进行批量请求优化。 收到所有需要的向量数据后，处理器 p 在本地计算 v_ i 与每个候选点的精确距离。 最后，处理器 p 从这些距离中选出最小的 K 个，将对应的点 ID 作为 v_ i 的近似 K 近邻，存入最终的本地图结果中。 阶段 4：结果收集（可选） 如果需要一个全局统一的 KNN 图，可以将所有处理器上的本地结果收集到一个根处理器。 步骤 5：算法优化与讨论 通信优化 ：阶段 2 和阶段 3 的通信是主要开销。 阶段 2 优化 ：可以使用高效的 All-to-All 通信原语（如 MPI_ Alltoallv）来实现桶信息的全局重分布，避免显式的点对点发送循环。 阶段 3 优化 ：可以将“请求桶列表”和“请求候选点向量数据”两轮通信合并或流水线化。也可以使用布隆过滤器在本地对候选集进行预过滤，减少需要获取向量的数量。 负载均衡 ： 数据划分不均或某些哈希桶特别大都会导致负载不均。 数据划分 ：可以采用基于空间填充曲线（如 Z-order）或基于聚类中心的划分，使相似点尽量在同一分区，可能减少候选集大小。 桶重分布 ：阶段 2 的路由函数 R(l, key) 应设计成尽量均匀地将 (l, key) 对分散到所有处理器上，避免单个处理器存储过大的全局桶目录。 近似质量与参数调优 ：算法的质量（召回率）和效率取决于 L 和 K。 增加 L ：增加哈希表数量，提高召回率，但会增加索引大小、通信量和候选集大小。 增加 K ：增加哈希键长度，提高桶内点的相似性（精度），但会降低召回率，因为点落入相同桶的概率降低。 通常需要通过实验在目标数据集上进行调整，以达到所需的召回率/精度与运行时间的平衡。 多表 vs 复合哈希 ：为了减少存储和通信开销，有时会采用“复合哈希”或“调和”的方式，用更少的哈希函数生成更多的“虚拟”哈希表，但这会增加算法复杂性。 总结 这个基于 LSH 的并行 KNN 图构建算法，通过 局部敏感哈希 将全局近邻搜索问题转化为局部桶内搜索，并利用 数据并行 和 基于哈希的全局桶信息分发 策略，实现了算法的并行化。其核心在于通过两阶段通信（全局桶信息收集、候选点数据获取）来协调分布式数据和计算，最终使每个处理器能独立为其本地数据点找到高质量的近似 K 近邻。该算法是大规模高维数据近似相似性搜索和图构建的经典并行范例。