параллельное построение дерева квадрантов из упорядоченных по Мортону точек

Сначала некоторые мысли о вашем плане:

• Вы уверены, что распараллеливание построения поможет? Я думаю, есть риск, что вы не сильно ускоритесь. Конструкция Quadtree довольно дешева для процессора, поэтому она будет частично связана с пропускной способностью вашей памяти. Распараллеливание может не сильно помочь, если только у вас нет отдельных шин памяти, например отдельных машин.
• Если вы хотите распараллелить построение на параллельных машинах, может быть дешевле просто создать отдельные деревья квадрантов, разделив коллекцию точек на куски одинакового размера. Это имеет одно большое преимущество перед другими решениями: когда вы хотите вставить больше точек или хотите найти точки, порядок Мортона позволяет вам довольно эффективно определить, какое дерево содержит точку (или должно содержать ее для вставки). Для оконных запросов вы можете выполнить аналогичную оптимизацию, если коды Мортона углов «мин/мин» и «макс/макс» окна запроса лежат в одном и том же «куске» (поддереве), то вы нужно только запросить это одно дерево. Возможны дополнительные оптимизации.

Если вы действительно хотите создать одно дерево квадрантов на одном компьютере, существует несколько способов эффективного разделения набора данных:

• Пройдитесь по всем точкам и определите глобальные мин/макс. Затем пройдитесь по всем точкам и назначьте их (при условии, что 4 ядра) каждому ядру, где каждое ядро ​​представляет собой квадрант. Эти шаги можно легко распараллелить, разделив набор данных на 4 фрагмента одинакового размера, и в результате получится дерево квадрантов, которое точно соответствует вашему набору данных. Вам придется синхронизировать вставку в деревья, но, поскольку набор данных упорядочен по Мортону, должно быть относительно мало коллизий блокировок.
• Вы можете полностью избежать конфликтов блокировок во время вставки, выровняв квадранты по координатам Мортона так, чтобы кривая Мортона (z-кривая) пересекала границы квадрантов только один раз. Недостаток: дерево будет несбалансированным, т.е. маловероятно, что все квадранты будут содержать одинаковое количество данных. Это означает, что ваши процессоры могут иметь значительно разные рабочие нагрузки, если только вы не разделите поддерево на под-поддеревья и т. д., чтобы лучше распределить нагрузку. Разделенные плоскости для избегания z-кривой пересечения границ квадрантов можно определить по коду Мортона/z-коду ваших координат. Разделите z-код на куски по два бита, каждый из которых говорит вам, какой (суб-) квадрант выбрать, то есть 00 — нижний/левый, 01 — нижний/правый, 10 — верхний/левый и 11 — верхний/правый. Поскольку ваши точки заказал Мортон, вы можете просто использовать бинарный поиск, чтобы найти фрагменты для каждого квадранта. Я понимаю, что это может звучать довольно загадочно без дополнительных объяснений. Так что, возможно, вы можете взглянуть на PH-дерево, оно, по сути, Z-Ordered (упорядочено по Мортону). ) quadtree (скорее 'trie', чем 'дерево'). Есть также несколько подробных объяснений здесь и здесь (бесстыдная самореклама). PH-дерево имеет некоторые приятные свойства, такие как изначальное ограничение глубины до 64 уровней (для 64-битных чисел), при этом гарантируется наличие небольших узлов (максимум 4 записи для 2 измерений); он также гарантирует, как и дерево квадрантов, что любая вставка/удаление никогда не повлияет более чем на один узел, а также, возможно, добавление или удаление второго узла. Существует также реализация C++ здесь.