Apache Spark - реализация распределенного QuadTree

Question

Я действительно новичок в Apache Spark.

Я работаю над реализацией Приблизительного LOCI (или ALOCI), алгоритма обнаружения аномалий, распределенным способом через Spark. Этот алгоритм основан на хранении точек в QuadTree, которое используется для поиска числа соседей точки.

Я точно знаю, как работают QuadTrees. Фактически, я недавно реализовал такую ​​структуру в Java. Но я полностью растерялся, поскольку речь идет о том, как такая структура может работать распределенным образом над Spark.

Нечто похожее на то, что мне нужно, можно найти в геопарке.

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

GeoSpark во многих случаях использует класс PointRDD, который расширяет класс SpatialRDD, который, как я вижу, использует QuadTree, который можно найти в приведенной выше ссылке, для разделения пространственных объектов. Это то, что я понял, по крайней мере, в теории.

На практике я все еще не могу понять это. Скажем, например, что у меня есть миллионы записей в CSV, и я хочу прочитать и загрузить их в QuadTree.

Я мог бы прочитать csv в СДР, но что тогда? Как этот RDD логически соединяется с QuadTree, которое я пытаюсь собрать?

Конечно, я не ожидаю рабочего решения здесь. Мне просто нужна логика здесь, чтобы заполнить пробел в моей голове. Как реализовать распределенное QuadTree и как его использовать?

Answer 1

Хорошо, к сожалению, нет ответов на этот вопрос, но вот я через две недели с рабочим решением. Не уверен на 100%, если это правильный подход здесь.

Я создал класс с именем Element и превратил каждую строку моего csv в RDD [Element]. Затем я создал сериализуемый класс с именем QuadNode, который имеет List [Elements] и Array [String] размера 4. При добавлении элементов в узел эти элементы добавляются в список узла. Если список получает больше X элементов (в моем случае 20), узел разбивается на 4 дочерних элемента и элементы отправляются дочерним элементам. Наконец, я создал класс QuadTree, у которого есть RDD [QuadNodes] среди его остальных свойств. Каждый раз, когда узел переходит к дочерним элементам, эти дочерние узлы добавляются в RDD дерева.

На нефункциональном языке каждый узел будет иметь 4 указателя, по одному на каждого потомка. Поскольку мы находимся в распределенной среде, этот подход не может работать. Итак, я дал каждому узлу уникальный идентификатор. Корневой узел имеет id = "0". Корневые узлы имеют идентификаторы «00», «01», «02» и «03». Узел «00» имеет идентификаторы «000», «001», «002», «003». Таким образом, если мы хотим найти всех потомков узла, мы фильтруем RDD [QuadNode] нашего дерева, проверяя, начинаются ли идентификаторы узлов с идентификатора узла. Изменение этой логики помогает нам найти родительский узел узла.

Так я реализовал свое QuadTree, по крайней мере сейчас. Если кто-то знает лучший способ реализации этого, я хотел бы услышать его / ее мнение.