Apache Spark -实现分布式QuadTree

Question

我真的，真的，不熟悉Apache Spark。

我正在致力于在Spark上实现近似轨迹(或ALOCI)，这是一种异常检测算法。该算法基于将点存储在用于查找点的邻居数量的QuadTree中。

我很清楚QuadTrees是如何工作的。事实上，我最近在Java中实现了这样一个结构。但我完全不明白这样的结构如何在Spark上以分布式的方式工作。

类似于我需要的东西可以在Geospark中找到。

https://github.com/DataSystemsLab/GeoSpark/tree/b2b6f1d7f0015d5c9d663a7b28d5e1bb1043c413/core/src/main/java/org/datasyslab/geospark/spatialPartitioning/quadtree

在许多情况下，GeoSpark使用PointRDD类，它扩展了SpatialRDD类，我可以看到该类使用了可以在上面的链接中找到的QuadTree来划分空间对象。这是我的理解，至少在理论上是这样。

在实践中，我仍然无法弄清楚这一点。例如，假设我在csv中有数百万条记录，我想在QuadTree中读取并加载它们。

我可以将csv读到RDD，但然后呢？这个RDD如何在逻辑上连接到我正在尝试构建的QuadTree？

当然，我不希望这里有一个有效的解决方案。我只需要这里的逻辑来填补我脑海中的空白。如何实现分布式QuadTree以及如何使用它？

Answer 1

好吧，遗憾的是，这个问题没有答案，但两周后我在这里提出了一个有效的解决方案。然而，不是100%确定这是否是正确的方法。

我创建了一个名为Element的类，并将csv的每一行转换为一个RDDElement。然后，我创建了一个名为QuadNode的可序列化类，该类有一个ListElements和一个大小为4的ArrayString。在向节点添加元素时，这些元素将被添加到节点的列表中。如果列表获得的元素超过X个(在我的示例中为20个)，节点将分解为4个子节点，并将这些元素发送给子节点。最后，我创建了一个类QuadTree，它的rest属性中有一个RDDQuadNodes。每次节点分解为子节点时，这些子节点就会被添加到树的RDD中。

在非函数式语言中，每个节点将有4个指针，每个子节点一个。因为我们是在分布式环境中，所以这种方法不能工作。因此，我为每个节点分配了一个唯一的Id。根节点的id = "0“。Root的节点ids为"00“、"01”、"02“和"03”。Node-"00“子节点的ids为"000”、"001“、"002”、"003“。这样，如果我们想要找到一个节点的所有后代，我们可以通过检查节点的id是否startWith出节点id来过滤树的RDDQuadNode。颠倒这个逻辑可以帮助我们找到一个节点的父节点。

这就是我实现QuadTree的方式，至少现在是这样。如果有人知道实现这一点的更好方法，我很想听听他/她的意见。