Из Википедии, бесплатной энциклопедии
  (Перенаправлено из приказа Мортона )
Перейти к навигации Перейти к поиску
Не путать с кривой Z или Z-порядком .
Четыре итерации кривой Z-порядка.
Итерации кривой Z-порядка расширены до трех измерений.

В математическом анализе и информатике , функции , которые являются Z-порядок , кривым лебегово , Мортон кривого заполнения пространства , [1] Мортон заказать или Мортон код карту многомерных данных в одном измерения при сохранении расположения точек данных. Он назван в честь Гая Макдональда Мортона , который впервые применил этот порядок к упорядочиванию файлов в 1966 году. [2] Z-значение точки в многомерном пространстве просто вычисляется путем чередования двоичного файла.представления его значений координат. После сортировки данных в этом порядке можно использовать любую одномерную структуру данных, такую ​​как деревья двоичного поиска , B-деревья , списки пропуска или (с усеченными младшими значащими битами) хэш-таблицы . Результирующий порядок можно эквивалентно описать как порядок, который можно получить при обходе в глубину квадродерева или октодерева .

Значения координат [ править ]

На рисунке ниже показаны Z-значения для двумерного случая с целочисленными координатами 0 ≤  x  ≤ 7, 0 ≤  y  ≤ 7 (показаны как в десятичном, так и в двоичном формате). Чередование двоичных значений координат дает двоичные значения z, как показано. Соединение z- значений в их числовом порядке дает рекурсивную Z-образную кривую. Двумерные Z-значения также называются квадратичными.

Z-curve.svg

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] До S2 этого избегали, потому что вычисления были несколько более сложными, что приводило к значительным накладным расходам процессора. Исходный код BIGMIN как для Z-кривой, так и для кривой Гильберта был описан в патенте Х. Тропфа. [13]

Для недавнего обзора многомерной обработки данных, включая, например, поиск ближайшего соседа, см. Учебник Ханана Самета . [14]

Приложения [ править ]

Таблица сложения для того, где и оба принадлежат последовательности Мозера – де Брейна , и кривая Z-порядка, которая соединяет суммы в числовом порядке

Линейная алгебра [ править ]

Алгоритм Штрассны для матричного умножения на основе расщепления матрицы в четырех блоков, а затем рекурсивно расщеплении каждого из этих блоков в четырех небольших блоках, до тех пор пока блоки не единичные элементы (или более практически: до достижения матрицы столь мало , что Мозер-де Тривиальный алгоритм последовательности Брейна работает быстрее). Расположение элементов матрицы в Z-порядке улучшает локальность и дает дополнительное преимущество (по сравнению с упорядочением по строкам или по столбцам), заключающееся в том, что подпрограмме умножения двух блоков не требуется знать общий размер матрицы, а нужно знать только размер матрицы. размер блоков и их расположение в памяти. Эффективное использование умножения Штрассена с Z-порядком было продемонстрировано, см. Статью Валсалама и Скьеллума 2002 года. [15]

Buluç et al. представляют структуру данных разреженной матрицы, которая Z-упорядочивает свои ненулевые элементы, чтобы обеспечить параллельное умножение матрицы на вектор. [16]

Отображение текстуры [ править ]

Некоторые графические процессоры хранят карты текстур в Z-порядке, чтобы увеличить пространственную локальность ссылки во время растеризации с отображением текстуры . Это позволяет строкам кэша представлять прямоугольные плитки, увеличивая вероятность того, что доступ к ним находится в кэше. В более крупном масштабе это также снижает вероятность дорогостоящих, так называемых, «разрывов страниц» (т. Е. Затрат на изменение строк ) в SDRAM / DDRAM. Это важно, потому что 3D-рендеринг включает произвольные преобразования (поворот, масштабирование, перспективу и искажение анимированными поверхностями).

Эти форматы часто называют сдвинутыми текстурами или вращающимися текстурами . Также могут использоваться другие плиточные форматы.

Проблема N-тела [ править ]

Barnes-Hut алгоритм требует конструкции октава дерева. Хранение данных в виде дерева на основе указателей требует множества последовательных разыменований указателей для итерации по окт-дереву в порядке глубины (дорого для машины с распределенной памятью). Вместо этого, если кто-то хранит данные в хэш- таблице , используя хеширование окт-дерева , кривая Z-порядка естественным образом выполняет итерацию окт-дерева в порядке глубины. [4]

См. Также [ править ]

  • Кривая заполнения пространства
  • УБ-дерево
  • Кривая Гильберта
  • R-дерево Гильберта
  • Пространственный индекс
  • Geohash
  • Местонахождение ссылки
  • Хеширование с сохранением местоположения
  • Матричное представление
  • Линейная алгебра

Ссылки [ править ]

  1. ^ "Абстрактная спецификация дискретных глобальных сетевых систем" (PDF) . Открытый геопространственный консорциум . 2017 г.
  2. ^ Мортон, GM (1966), компьютерно-ориентированная база геодезических данных; and a New Technique in File Sequencing (PDF) , Technical Report, Ottawa, Canada: IBM Ltd.
  3. ^ a b c Берн, М .; Эппштейн, Д .; Тенг, С.-Х. (1999), "Параллельное построение квадродеревьев и качественных триангуляций", Int. J. Comput. Геом. Прил. , 9 (6): 517-532, CiteSeerX 10.1.1.33.4634 , DOI : 10,1142 / S0218195999000303 .
  4. ^ a b c Уоррен, 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.
  5. ^ Gargantini, И. (1982), "Эффективный способ представления quadtrees", коммуникаций АСМ , 25 (12): 905-910, DOI : 10,1145 / 358728,358741 , S2CID 14988647 .
  6. ^ a b Чан, Т. (2002), "Проблемы ближайших точек, упрощенные в ОЗУ", Симпозиум ACM-SIAM по дискретным алгоритмам.
  7. ^ Коннор, М .; Кумар, П. (2009), «Быстрое построение графов k-ближайших соседей для облаков точек», IEEE Transactions по визуализации и компьютерной графике (PDF)
  8. ^ Har-Peled, S. (2010), Структуры данных для геометрического приближения (PDF)
  9. ^ Tropf, H .; Херцог, Х. (1981), "Поиск многомерного диапазона в динамически сбалансированных деревьях" (PDF) , Angewandte Informatik , 2 : 71–77 .
  10. ^ Геде, Volker; Гюнтер, Оливер (1998), "Методы доступа Многомерные" (PDF) , ACM Computing Surveys , 30 (2): 170-231, CiteSeerX 10.1.1.35.3473 , DOI : 10,1145 / 280277,280279 , S2CID 7075919   .
  11. ^ Рамсак, Франк; Маркл, Фолькер; Фенк, Роберт; Циркель, Мартин; Эльхардт, Клаус; Байер, Рудольф (2000), "Интеграция UB-дерева в ядро ​​системы баз данных", Int. Конф. по очень большим базам данных (VLDB) (PDF) , стр. 263–272, заархивировано из оригинала (PDF) 04 марта 2016 г. .
  12. ^ "S2 Геометрия" .
  13. ^ США 7321890 , Tropf, H., «База данных системы и способ организации элементов данных в соответствии с кривой Гильберта», опубликованном 22 января 2008 года  .
  14. ^ Самет, Х. (2006), Основы многомерных и метрических структур данных , Сан-Франциско: Морган-Кауфманн.
  15. ^ Винод Валсалам, Энтони Скьеллум: структура для высокопроизводительного умножения матриц на основе иерархических абстракций, алгоритмов и оптимизированных низкоуровневых ядер. Параллелизм и вычисления: практика и опыт 14 (10): 805-839 (2002) [1] [2]
  16. ^ Buluç, Aydın; Fineman, Джереми Т .; Фриго, Маттео; Гилберт, Джон Р .; Лейзерсон, Чарльз Э. (2009). Параллельное умножение разреженных матриц-векторов и матриц-транспонированных векторов с использованием сжатых разреженных блоков (PDF) . ACM Symp. по параллелизму в алгоритмах и архитектурах. CiteSeerX 10.1.1.211.5256 .  

Внешние ссылки [ править ]

  • STANN: библиотека для приблизительного поиска ближайшего соседа с использованием кривой Z-порядка.
  • Методы программирования битового чередования , Шон Эрон Андерсон, Стэнфордский университет.