Маркировка подключенного компонента на случайно разделенных данных?

0

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

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

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

- = - = - = -

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

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

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

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

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

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

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

- = - = - = -

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

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

Теги:
arrays
algorithm

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. Изучив эту абстракцию, вы сможете нереализовать Disjoint-Set необычными способами.

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

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

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

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

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

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

Поделиться

Ещё вопросы

Сообщество Overcoder
Наверх
Меню