В математическом анализе и информатике , функции , которые являются Z-порядок , кривым лебегово , Мортон кривого заполнения пространства , [1] Мортон заказать или Мортон код карту многомерных данных в одном измерения при сохранении расположения точек данных. Он назван в честь Гая Макдональда Мортона , который впервые применил этот порядок к упорядочиванию файлов в 1966 году. [2] Z-значение точки в многомерном пространстве просто вычисляется путем чередования двоичного файла.представления его значений координат. После сортировки данных в этом порядке можно использовать любую одномерную структуру данных, такую как деревья двоичного поиска , B-деревья , списки пропуска или (с усеченными младшими значащими битами) хэш-таблицы . Результирующий порядок можно эквивалентно описать как порядок, который можно получить при обходе в глубину квадродерева или октодерева .
Координатные значения
На рисунке ниже показаны Z-значения для двумерного случая с целочисленными координатами 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (показаны как в десятичном, так и в двоичном формате). Чередование двоичных значений координат дает двоичные значения z, как показано. Соединение z- значений в их числовом порядке дает рекурсивную Z-образную кривую. Двумерные Z-значения также называются квадратичными.
Z-значения x описываются как двоичные числа из последовательности Мозера – де Брейна , имеющие ненулевые биты только в их четных позициях:
x [] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}
Сумма и разность двух x вычисляются с помощью побитовых операций :
x [i + j] = ((x [i] | 0b10101010) + x [j]) & 0b01010101x [ij] = ((x [i] & 0b01010101) - x [j]) & 0b01010101, если i> = j
Это свойство можно использовать для смещения Z-значения, например, в двух измерениях, координаты вверху (уменьшение y), внизу (увеличение y), влево (уменьшение x) и вправо (увеличение x) от текущего значения Z z :
top = (((z & 0b10101010) - 1) & 0b10101010) | (z & 0b01010101)дно = (((z | 0b01010101) + 1) & 0b10101010) | (z & 0b01010101)left = (((z & 0b01010101) - 1) & 0b01010101) | (z & 0b10101010)вправо = (((z | 0b10101010) + 1) & 0b01010101) | (z & 0b10101010)
И вообще, чтобы добавить два двумерных Z-значения w и z :
сумма = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)
Эффективное построение квадродеревьев и октодеревьев
Z-порядок может использоваться для эффективного построения квадродерева (2D) или октодерева (3D) для набора точек. [3] [4] Основная идея состоит в том, чтобы отсортировать входной набор в соответствии с Z-порядком. После сортировки точки могут быть либо сохранены в двоичном дереве поиска и использоваться напрямую, что называется линейным деревом квадрантов [5], либо их можно использовать для построения дерева квадрантов на основе указателя.
Входные точки обычно масштабируются в каждом измерении, чтобы быть положительными целыми числами, либо как представление с фиксированной точкой в диапазоне единиц [0, 1], либо в соответствии с размером машинного слова. Оба представления эквивалентны и позволяют находить ненулевой бит высшего порядка за постоянное время. Каждый квадрат в дереве квадрантов имеет длину стороны, равную степени двойки, и угловые координаты, кратные длине стороны. Для любых двух точек производный квадрат для этих двух точек является наименьшим квадратом, покрывающим обе точки. Перемежение битов из компонентов x и y каждой точки называется перемешиванием x и y и может быть расширено до более высоких измерений. [3]
Точки можно сортировать в соответствии с их перемешиванием без явного чередования битов. Для этого для каждого измерения проверяется старший бит исключающего ИЛИ координат двух точек для этого измерения. Затем размерность, для которой наиболее значимый бит является наибольшим, используется для сравнения двух точек для определения их порядка перемешивания.
Операция исключающая или маскирует биты более высокого порядка, для которых две координаты идентичны. Поскольку при перемешивании биты чередуются от более высокого порядка к более низкому порядку, идентифицируя координату с самым большим старшим битом, идентифицирует первый бит в порядке перемешивания, который отличается, и эта координата может использоваться для сравнения двух точек. [6] Это показано в следующем коде Python:
Защиту cmp_zorder ( LHS , ки ) -> BOOL : "" "Сравнить Z-упорядочивание" "" # Предположат , левые и правые части массива , как объекты индексов. assert len ( lhs ) == len ( rhs ) # Будет содержать наиболее значимое измерение. msd = 0 # Перебираем другие измерения. for dim in range ( 1 , len ( lhs )): # Проверить, является ли текущее измерение более значимым # путем сравнения наиболее значимых битов. если less_msb ( LHS [ MSD ] ^ RHS [ MSD ], LHS [ тусклые ] ^ шк [ тусклое ]): MSD = тусклый возврата LHS [ MSD ] < RHS [ MSD ]
Один из способов определить, является ли самый старший бит меньшим, - это сравнить нижний предел логарифма с основанием 2 для каждой точки. Оказывается, следующая операция эквивалентна и требует только исключающих операций или: [6]
def less_msb ( x : int , y : int ) -> bool : вернуть x < y и x < ( x ^ y )
Также можно сравнивать числа с плавающей запятой, используя ту же технику. Функция less_msb модифицируется так, чтобы сначала сравнивать экспоненты. Только когда они равны, стандартная функция less_msb используется в мантиссах. [7]
После того, как точки расположены в отсортированном порядке, два свойства упрощают построение дерева квадрантов: первое - точки, содержащиеся в квадрате дерева квадрантов, образуют непрерывный интервал в отсортированном порядке. Во-вторых, если более одного дочернего элемента квадрата содержат входную точку, квадрат является производным квадратом для двух соседних точек в отсортированном порядке.
Для каждой смежной пары точек вычисляется производный квадрат и определяется длина его стороны. Для каждого производного квадрата интервал, содержащий его, ограничен первым большим квадратом справа и слева в отсортированном порядке. [3] Каждый такой интервал соответствует квадрату в дереве квадрантов. Результатом этого является сжатое дерево квадрантов, в котором присутствуют только узлы, содержащие входные точки или два или более дочерних элемента. При желании несжатое дерево квадрантов может быть построено путем восстановления отсутствующих узлов.
Вместо построения дерева квадрантов на основе указателя точки могут поддерживаться в отсортированном порядке в структуре данных, такой как двоичное дерево поиска. Это позволяет добавлять и удалять точки за время O (log n). Два квадродерева можно объединить, объединив два отсортированных набора точек и удалив дубликаты. Местоположение точки может быть выполнено путем поиска точек, предшествующих и следующих за точкой запроса в отсортированном порядке. Если дерево квадрантов сжато, найденный узел-предшественник может быть произвольным листом внутри сжатого интересующего узла. В этом случае необходимо найти предшественника наименее общего предка точки запроса и найденного листа. [8]
Использование с одномерными структурами данных для поиска диапазона
Несмотря на хорошее сохранение местоположения, для эффективного поиска по диапазону необходим алгоритм для вычисления из точки, встречающейся в структуре данных, следующего Z-значения, которое находится в многомерном диапазоне поиска:
В этом примере запрашиваемый диапазон ( x = 2, ..., 3, y = 2, ..., 6) обозначен пунктирным прямоугольником. Его максимальное значение Z (MAX) составляет 45. В этом примере значение F = 19 встречается при поиске структуры данных в направлении увеличения Z-значения, поэтому нам придется искать в интервале между F и MAX (заштрихованная область ). Чтобы ускорить поиск, нужно вычислить следующее Z-значение, которое находится в диапазоне поиска, называемое BIGMIN (36 в примере), и искать только в интервале между BIGMIN и MAX (значения, выделенные жирным шрифтом), таким образом пропуская большую часть заштрихованных область. Поиск в убывающем направлении аналогичен LITMAX, который является самым высоким Z-значением в диапазоне запроса ниже F. Проблема BIGMIN была впервые сформулирована, и ее решение показано в Tropf и Herzog. [9] Это решение также используется в UB-деревьях («GetNextZ-адрес»). Поскольку подход не зависит от выбранной одномерной структуры данных, по-прежнему существует свободный выбор структурирования данных, поэтому для работы с динамическими данными можно использовать хорошо известные методы, такие как сбалансированные деревья (в отличие, например, от R-деревьев, где необходимы особые соображения). Точно так же эта независимость упрощает включение метода в существующие базы данных.
Иерархическое применение метода (в соответствии с имеющейся структурой данных), необязательно как в направлении увеличения, так и уменьшения, дает высокоэффективный поиск по многомерному диапазону, который важен как для коммерческих, так и для технических приложений, например, как процедура, лежащая в основе поиска ближайшего соседа. Z-порядок - один из немногих методов многомерного доступа, который нашел свое применение в коммерческих системах баз данных ( Oracle database 1995, [10] Transbase 2000 [11] ).
Еще в 1966 году GMMorton предложил Z-порядок для упорядочивания файлов статической двухмерной географической базы данных. Единицы площадных данных содержатся в одном или нескольких квадратичных кадрах, представленных их размерами и Z-значениями нижнего правого угла, размеры которых соответствуют иерархии Z-порядка в угловой позиции. С большой вероятностью переход к соседнему кадру выполняется за один или несколько относительно небольших шагов сканирования.
Связанные структуры
В качестве альтернативы была предложена кривая Гильберта , поскольку она лучше сохраняет порядок [4] и, фактически, использовалась в оптимизированном индексе, S2-геометрии. [12]
Приложения
Линейная алгебра
Алгоритм Штрассны для матричного умножения на основе расщепления матрицы в четырех блоков, а затем рекурсивно расщеплении каждого из этих блоков в четырех небольших блоках, до тех пор пока блоки не единичные элементы (или более практически: до достижения матрицы столь мало , что Мозер-де Тривиальный алгоритм последовательности Брейна работает быстрее). Расположение элементов матрицы в Z-порядке улучшает локальность и дает дополнительное преимущество (по сравнению с упорядочением по строкам или по столбцам), заключающееся в том, что подпрограмме умножения двух блоков не требуется знать общий размер матрицы, а нужно знать только размер матрицы. размер блоков и их расположение в памяти. Эффективное использование умножения Штрассена с Z-порядком было продемонстрировано, см. Статью Валсалама и Скьеллума 2002 года. [13]
Buluç et al. представляют структуру данных разреженной матрицы, которая Z-упорядочивает свои ненулевые элементы, чтобы обеспечить параллельное умножение матрицы на вектор. [14]
Отображение текстур
Некоторые графические процессоры хранят карты текстур в Z-порядке, чтобы увеличить пространственную локальность ссылки во время растеризации с отображением текстуры . Это позволяет строкам кэша представлять прямоугольные плитки, увеличивая вероятность того, что доступ к ним находится в кэше. В более крупном масштабе это также снижает вероятность дорогостоящих, так называемых, «разрывов страниц» (т. Е. Затрат на изменение строк ) в SDRAM / DDRAM. Это важно, потому что 3D-рендеринг включает произвольные преобразования (поворот, масштабирование, перспективу и искажение анимированными поверхностями).
Эти форматы часто называют сдвинутыми текстурами или вращающимися текстурами . Также могут использоваться другие плиточные форматы.
Проблема N-тела
Barnes-Hut алгоритм требует конструкции октава дерева. Хранение данных в виде дерева на основе указателей требует множества последовательных разыменований указателей для итерации по окт-дереву в порядке глубины (дорого для машины с распределенной памятью). Вместо этого, если кто-то хранит данные в хэш- таблице , используя хеширование окт-дерева , кривая Z-порядка естественным образом выполняет итерацию окт-дерева в порядке глубины. [4]
Смотрите также
- Кривая заполнения пространства
- УБ-дерево
- Кривая Гильберта
- R-дерево Гильберта
- Пространственный индекс
- Geohash
- Местонахождение ссылки
- Хеширование с сохранением местоположения
- Матричное представление
- Линейная алгебра
Рекомендации
- ^ "Абстрактная спецификация дискретных глобальных сетевых систем" (PDF) . Открытый геопространственный консорциум . 2017 г.
- ^ Мортон, GM (1966), Компьютерная база геодезических данных; and a New Technique in File Sequencing (PDF) , Technical Report, Ottawa, Canada: IBM Ltd.
- ^ а б в Bern, M .; Эппштейн, Д .; Тенг, С.-Х. (1999), "Параллельное построение квадродеревьев и качественных триангуляций", Int. J. Comput. Геом. Прил. , 9 (6): 517-532, CiteSeerX 10.1.1.33.4634 , DOI : 10,1142 / S0218195999000303.
- ^ а б в Уоррен, MS; Лосось, JK (1993). «Параллельный хешированный алгоритм Oct-Tree N-body» . Материалы конференции ACM / IEEE 1993 г. по суперкомпьютерам - Supercomputing '93 . Портленд, Орегон, США: ACM Press: 12–21. DOI : 10.1145 / 169627.169640 . ISBN 978-0-8186-4340-8.
- ^ Gargantini, И. (1982), "Эффективный способ представления quadtrees", коммуникаций АСМ , 25 (12): 905-910, DOI : 10,1145 / 358728,358741 , S2CID 14988647.
- ^ а б Чан, Т. (2002), "Проблемы ближайших точек, упрощенные в ОЗУ", Симпозиум ACM-SIAM по дискретным алгоритмам.
- ^ Коннор, М .; Кумар, П. (2009), «Быстрое построение графов k-ближайших соседей для облаков точек», IEEE Transactions по визуализации и компьютерной графике (PDF)
- ^ Хар-Пелед, С. (2010), Структуры данных для геометрической аппроксимации (PDF)
- ^ Tropf, H .; Херцог, Х. (1981), "Поиск многомерного диапазона в динамически сбалансированных деревьях" (PDF) , Angewandte Informatik , 2 : 71–77.
- ^ Gaede, Volker; Гюнтер, Оливер (1998), "Методы доступа Многомерные" (PDF) , ACM Computing Surveys , 30 (2): 170-231, CiteSeerX 10.1.1.35.3473 , DOI : 10,1145 / 280277,280279 , S2CID 7075919.
- ^ Рамсак, Франк; Маркл, Фолькер; Фенк, Роберт; Циркель, Мартин; Эльхардт, Клаус; Байер, Рудольф (2000), "Интеграция UB-дерева в ядро системы баз данных", Int. Конф. по очень большим базам данных (VLDB) (PDF) , стр. 263–272, заархивировано из оригинала (PDF) 04 марта 2016 г..
- ^ «S2 Геометрия» .
- ^ Винод Валсалам, Энтони Скьеллум: структура для высокопроизводительного умножения матриц на основе иерархических абстракций, алгоритмов и оптимизированных низкоуровневых ядер. Параллелизм и вычисления: практика и опыт 14 (10): 805-839 (2002) [1] [2]
- ^ Булуч, Айдын; Fineman, Джереми Т .; Фриго, Маттео; Гилберт, Джон Р .; Лейзерсон, Чарльз Э. (2009). Параллельное умножение разреженных матриц-векторов и матриц-транспонированных векторов с использованием сжатых разреженных блоков (PDF) . ACM Symp. по параллелизму в алгоритмах и архитектурах. CiteSeerX 10.1.1.211.5256 .
Внешние ссылки
- STANN: библиотека для приблизительного поиска ближайшего соседа с использованием кривой Z-порядка.
- Методы программирования битового чередования , Шон Эрон Андерсон, Стэнфордский университет.