Подключенная маркировка компонентов по случайным образом разделенным данным?

Question

В настоящее время мне поручено реализовать алгоритм CCL в системе баз данных (написанный на C++). Этот алгоритм назначил метку всем значениям заданного многомерного массива, которые превышают пороговое значение, а соседние помеченные значения будут иметь одну и ту же метку.

Кодирование базового алгоритма CCL не было затруднительным, но в моем домене входной массив случайным образом разбивается на несколько экземпляров базы данных. Когда вызывается мой оператор CCL, каждый экземпляр выполняет операцию над куском данных, за которые отвечает и возвращает свой локальный результат CCL. Эти локальные результаты затем объединяются для получения конечного результата.

Во время выполнения я не знаю, какой экземпляр отвечает за любую данную часть массива, а экземпляры не могут связываться друг с другом до последнего шага слияния.

- = - = - = -

В настоящее время у меня есть этот рабочий, выполнив следующие действия:

1. Каждый экземпляр создает массив логических значений размера, равного число пунктов в массиве и устанавливает все значения в FALSE.

2. Каждый экземпляр проходит через значения, за которые он отвечает, и проверяет, превышают ли эти значения порог; если они есть, то изменят соответствующие логические значения в их локальном массиве на ИСТИНА.

3. Все экземпляры отправляют свои массивы координатору, который объединяет результаты с использованием OR для создания конечного булева вектора.

4. Координатор передает каждое значение в массиве, пропуская значения , которые уже обозначены. Если значение не помечено и , то логическое значение, соответствующее этому значению, истинно, оно присваивает ему новую метку и рекурсивно присваивает все ее соседи (и соседние соседи и т. Д.) Одну и ту же метку.

5. Вектор этикетки возвращается.

Вышеупомянутый алгоритм работает, но единственное, что использует множественные экземпляры, это пороговые вычисления. Поскольку эта реализация просто собирает все и проверяет ее на координаторе, она скорее поражает точку использования нескольких экземпляров в первую очередь.

- = - = - = -

По существу, этот алгоритм делается в алгоритме разделяй и властвуй автоматически, но подразделения полностью и бесконтрольно случайным образом.

Мы хотим воспользоваться этим разделением, выполнив как развертки CCL на каждом экземпляре, так и объединив эти локальные результаты CCL на координаторе; то есть, если два экземпляра создают группы ярлыков, которые соседствуют друг с другом, мы хотим объединить эти два ярлыка , не просматривая каждое значение снова. Эта курсивная точка - это то, что дает нам наибольшую проблему, и мы скорее теряемся в том, как действовать дальше. Если у кого-то есть предложения либо для алгоритмов, либо для структуры данных, которые были бы хороши для изучения, это было бы высоко оценено.

Answer 1

Соединительные компоненты (в отличие от подключенных к графам компонентов) требуют проверки набора всех пар соседних (смежных пикселей).

То есть,

• Определим множество над парами точек, которые находятся рядом:
  • { ((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)

---

Следующий шаг понимания требует, чтобы знать Equivalence relation. В частности, он должен удовлетворять:

• рефлексивности
• Symmetry
• транзитивность

Существует интересное следствие из этих трех требований:

• Предположим, что вы дали частичное список отношений эквивалентности, таких как (a, b), (b, c), (c, d), (e , f)
• Обратите внимание, что перестановка этого списка, вставляя «эквивалентные» отношения эквивалентности (такие как (a, c), учитывая, что (a, b) и (b, c) уже существуют) и т. д., не влияют на секционирования.

Следует отметить, что интерфейс алгоритма «Disjoint-Set», который будет обсуждаться ниже, является в точности списком отношений эквивалентности. Таким образом, можно обрабатывать этот список отношений эквивалентности по-разному и все равно получить тот же результат.

---

В представляет и описывает алгоритмов, которые вычисляют и процесс, связанные компоненты, следует изучить Disjoint-Set.

Необходимо изучить фактическую реализацию Disjoint-Set, а также узнать, как он фактически используется (вызывается) из алгоритма подключенных компонентов.

После этого следует поднять уровень абстракции понимания - абстрактную концепцию (интерфейс алгоритма) Disjoint-Set. Изучив эту абстракцию, вы сможете повторно реализовать Disjoint-Set необычными способами.

• На этапе строительства требуется только функция Union из основного контура.
• Find функция используется только внутри Union функция.
• Таким образом, можно абстрагироваться от операций Disjoint-Set, предоставляя приемник для потока сообщений Union((x1, y1), (x2, y2)).
• Эти сообщения могут быть асинхронными, поставленными в очередь, случайным образом перегруппированными, пакетными, однако вы хотите обработать их, если все такие вызовы в конечном итоге обрабатываются целиком.
• Это приведет к избыточным вызовам Union, потому что не будет проверок того, являются ли два узла уже одной и той же меткой перед очередью вызова в очередь. Этот вопрос будет рассмотрен в следующей части.

---

Теперь мы введем способ планирования этих Union сообщений для обработки.

Предположим, что узлы распределены на разные машины.

• Мы разобьем множество пар смежных пикселей { ((x1, y1), (x2, y2)) } следующим образом:
  • Для каждой машины, мы хотели бы найти подмножество пар соседних пикселей, которые находятся на одной и той же машине.
  • После этого мы хотели бы подмножество всего остального - пары соседних пикселей, которые находятся на двух отдельных машинах.

---

Обрабатывать Union-Find через другую машину, один просто * Генерирует Union сообщения из одной и той же машины множества пар смежных пикселей * Затем отфильтровать Union сообщения для удаления избыточные. * Генерирует сообщения Union из набора пар разных соседних пикселей. * Выполняйте сообщения разных машин по результатам сообщений с одинаковыми машинами.

---

Этот ответ написан в слишком абстрактно, так как более конкретный ответ потребует более подробной информации о проблеме, особенно часть о «полностью и бесконтрольно случайном разбиении».