0

我目前的任务是在数据库系统中实现 CCL 算法（用 C++ 编写）。该算法将为给定多维数组中超过阈值的所有值分配一个标签，并且相邻的标签值将具有相同的标签。

编写一个基本的 CCL 算法并不难，但在我的领域中，输入数组是随机分区到数据库的多个实例中的。当我的 CCL 操作符被调用时，每个实例都会对其负责的数据块执行操作并返回其本地 CCL 结果。然后将这些本地结果合并以产生最终结果。

我不知道在运行时哪个实例负责数组的任何给定部分，并且实例在最后的合并步骤之前无法相互通信。

-=-=-=-

目前，我通过执行以下操作来完成此工作：

  1. 每个实例创建一个布尔值数组，其大小等于数组中的项目数，并将所有值设置为 FALSE。

  2. 每个实例都会检查它负责的值并检查这些值是否超过阈值；如果是，则将其本地数组中的相应布尔值更改为 TRUE。

  3. 实例都将它们的数组发送到协调器，协调器使用 OR 组合结果以创建最终的布尔向量。

  4. 协调器遍历数组中的每个值，跳过已经标记的值。如果该值未标记并且对应于该值的布尔值为真，则它为其分配一个新标签并递归地为其所有邻居（以及邻居的邻居等）分配相同的标签。

  5. 返回标签向量。

上述算法有效，但利用多个实例的唯一优势是阈值计算。因为这个实现只是简单地收集所有东西并在协调器上扫描它，所以它首先破坏了使用多个实例的意义。

-=-=-=-

本质上，这个算法被自动地变成了一种分治算法，但是这种划分是完全不可控的随机的。

我们希望通过在每个实例上执行两次 CCL 扫描，然后在协调器上组合这些本地 CCL 结果来利用这种划分；也就是说，如果两个实例产生了一组彼此相邻的标签，我们希望将这两个标签组合起来，而不是再次扫描每个值。这个斜体字是给我们带来最大麻烦的地方，我们不知道如何进行。如果有人对算法或数据结构有建议可以很好地研究，将不胜感激。

4

1 回答 1

0

相邻连接组件（与图形连接组件相反）需要检查所有相邻（相邻像素）对的集合。

那是，

  • 在相邻的点对上定义集合：
    • { ((x1, y1), (x2, y2)) }为此
      • 对于 4 连接：(abs(x2 - x1) + abs(y2 - y1)) <= 1和(x1 != x2 && y1 != y2)
      • 对于 8 连接：max(abs(x2 - x1), abs(y2 - y1)) <= 1和(x1 != x2 && y1 != y2)

下一步的理解需要知道等价关系。值得注意的是，它必须满足：

  • 反身性
  • 对称
  • 传递性

这三个要求有一个有趣的结果：

  • 假设给定一个等价关系的部分列表，例如 (a, b), (b, c), (c, d), (e, f)
  • 请注意，置换此列表、插入“等价”等价关系（例如 (a, c) 鉴于 (​​a, b) 和 (b, c) 已经存在）等，不会影响分区。

需要注意的是，下面要讨论的“不相交集”的算法接口，正是等价关系的列表。因此，人们可以以不同的方式处理这个等价关系列表，并且仍然得到相同的结果。

为了表示和描述计算和处理连接组件的算法，应该研究Disjoint-Set。

应该学习 Disjoint-Set 的实际实现，并了解它是如何从连接组件算法中实际使用（调用）的。

之后，应该提高理解的抽象层次——Disjoint-Set的抽象概念（算法接口）。在学习了这个抽象之后，您将能够以不寻常的方式重新实现 Disjoint-Set 。

  • 在构建阶段，只需Union要从主循环调用函数。
  • 该Find函数仅在Union函数内部使用。
  • Union( (x1, y1), (x2, y2) )因此，可以通过为消息调用流提供接收器来抽象出不相交集的操作。
  • 这些消息调用可以是异步的、排队的、随机排列的、批处理的，但是您想处理它们，只要所有这些调用最终都被完整地处理。
  • 这将导致对 的冗余调用Union，因为在将调用排队之前不会检查两个节点是否已经是相同的标签。这个问题将在下一部分中处理。

现在我们将介绍一种调度这些Union消息进行处理的方法。

假设节点分布在不同的机器上。

  • 我们将按如下方式划分相邻像素对的集合{ ((x1, y1), (x2, y2)) }：
    • 对于每台机器，我们希望找到位于同一台机器上的相邻像素对的子集。
    • 之后，我们想要其他所有内容的子集——位于两台独立机器上的相邻像素对。

要在不同机器上处理联合查找，只需 *Union从同一机器的一组相邻像素对中生成消息 * 然后，过滤Union消息以删除冗余消息。*Union从不同机器的相邻像素对中生成消息。* 对同机消息的结果执行不同机消息。

这个答案写得太抽象了，因为更具体的答案需要更多关于问题的细节，尤其是关于“完全和不可控制的随机分区”的部分。

于 2014-08-17T22:43:23.087 回答