Кривая Мортона

В математическом анализе и информатике кривая Мортона, Z-последовательность, Z-порядок, кривая Лебега, порядок Мортона или код Мортона — это функция, которая отображает многомерные данные в одномерные, сохраняя локальность точек данных. Функция была введена в 1966 году Гаем Макдональдом Мортоном. Z-значение точки в многомерном пространстве легко вычисляется чередованием двоичных цифр его координатных значений. Когда данные запоминаются в этом порядке, могут быть использованы любые одномерные структуры, такие как двоичные деревья поиска, B-деревья, списки с пропусками или хеш-таблицы (с отбрасыванием младших битов). Созданный таким образом порядок можно эквивалентно описать как порядок, который можно получить обходом в глубину дерева квадрантов.

Четыре итерации кривой Мортона

Итерации кривой Мортона в трёхмерном пространстве

Координатные значенияПравить

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

 

Z-значения вдоль оси x описываются как двоичные числа из последовательности Мозера – де Брёйна^[en], имеющие ненулевые биты только в их чётных позициях:

x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}

Сумма и разность двух значений относительно x-координаты вычисляется с помощью битовых операций:

x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101
x[i-j] = ((x[i] & 0b01010101) - x[j]) & 0b01010101  если i >= j

Эффективное построение дерева квадрантовПравить

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

Входные точки обычно масштабируются по каждому из измерений, чтобы получить положительные целые числа либо как числа с фиксированной запятой в интервале [0, 1], либо в интервале, соответствующем машинному слову. Оба представления эквивалентны и позволяют найти старший ненулевой бит за постоянное время. Любой квадрат в дереве квадрантов имеет длину стороны, равную степени двойки, а координаты углов кратны длине стороны. Если заданы две точки, производный квадрат для этих двух точек — это наименьший квадрат, покрывающий обе точки. Чередующиеся биты из координат x и y каждой точки называется тасованием x и y и может быть распространено на более высокие размерности.

Точки могут быть отсортированы согласно их тасованию без явного чередования бит. Чтобы это сделать, для каждого измерения проверяется старший бит «исключающее ИЛИ» координат двух точек этого измерения. Размерность, для которой старший бит больше, используется затем для сравнения двух точек, чтобы определить их тасованный порядок.

Операция «исключающее ИЛИ» убирает одинаковые старшие биты, одинаковые для обеих координат. Нахождение координаты с большим старшим битом определяет первый бит, отличающийся в тасованном порядке, и эта координата может быть использована для сравнения двух точек. Это показано в следующем коде на языке Python:

    def cmp_zorder(a, b):
        j = 0
        k = 0
        x = 0
        for k in range(dim):
            y = a[k] ^ b[k]
            if less_msb(x, y):
                j = k
                x = y
        return a[j] - b[j]

Один из способов определения, является ли старший значащий бит меньше, это сравнить округленный вниз двоичный логарифм каждой точки. Оказывается, что следующая операция эквивалентна и требует лишь операцию «исключающее ИЛИ»:

    def less_msb(x, y):
        return x < y and x < (x ^ y)

Есть возможность сравнить числа с плавающей точкой, используя ту же технику. Функция less_msb модифицируется, чтобы сначала сравнивать экспоненты. Только в случае их совпадения выполняется стандартная функция less_msb на мантиссах .

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

Для каждой смежной пары точек вычисляется производный квадрат и его длина стороны. Для каждого производного квадрата содержащий его интервал ограничен первым бо́льшим квадратом справа и слева в сортировке. Каждый такой интервал соответствует квадрату в дереве квадрантов. В результате получается сжатое дерево квадрантов, где присутствуют только узлы, содержащие входные точки или два и более потомков. Несжатое дерево квадрантов может быть построено путём восстановления отсутствующих узлов, если нужно.

Вместо построения, основанного на точках дерева квадрантов, точки могут обрабатываться в отсортированном порядке с помощью таких структур данных, как двоичное дерево поиска. Это даёт возможность добавлять и удалять точки за время O(log n). Два дерева квадрантов можно слить вместе путём соединения двух отсортированных множеств точек с удалением дубликатов. Положение точки может быть определено путём поиска точек, предшествующих и следующих после точки из запроса в порядке сортировки. Если дерево квадрантов сжато, предшествующий найденный узел может быть произвольным листом внутри сжатого интересующего нас узла. В этом случае необходимо найти предшествующий общий узел точки из запроса и найденного листа.

Использование одномерных структур данных для поиска по диапазонуПравить

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

 

В этом примере диапазоном поиска (x = 2, …, 3, y = 2, …, 6) выделен пунктирным прямоугольником. Наибольшее Z- значение (MAX) в этом диапазоне равно 45. В этом примере значение F = 19 встречается, когда просматриваем данные в порядке возрастающих Z-значений, так что нам придётся искать в интервале между F и MAX (заштрихованная область). Чтобы ускорить поиск, желательно вычислить следующее Z-значение, принадлежащее области поиска, называемое BIGMIN (в нашем примере — 36), а затем искать только в интервале между BIGMIN и MAX (выделены жирным), тем самым отбрасывая большую часть заштрихованной области. Поиск в сторону уменьшения аналогичен, здесь LITMAX является наибольшим Z-значением в запросе по диапазону, меньшему F. Задача поиска BIGMIN впервые была сформулирована и решение задачи было показано в работе Тропфа и Герцога. Это решение используется в UB-деревьях («GetNextZ-address»). Поскольку подход не зависит от выбранной одномерной структуры данных, остаётся свобода её выбора, так что могут быть использованы хорошо известные методы, такие как сбалансированные деревья, для работы с изменяемыми данными (в отличие, например, от o R-деревьев, где необходимы специальные соглашения). Также эта независимость позволяет проще использовать метод в существующих базах данных.

Если использовать метод иерархически (согласно имеющейся под рукой структуре данных), метод даёт высокоэффективный метод поиска по диапазонам в обоих направлениях (по убыванию или возрастанию), что важно как в коммерческих, так и в производственных приложениях, например, в виде процедуры, на основе которой строится поиск ближайшего соседа. Z-порядок является одним из немногих методов доступа к многомерным данным, нашедших путь в коммерческие базы данных (Oracle Database 1995 (Gaede, Guenther 1998), Transbase^[en] 2000 (Ramsak, Markl, Fenk, Zirkel, Elhardt, Bayer 2000).).

В 1966 году Г. М. Мортон предложил Z-порядок для упорядочивания файлов статической двумерной географической базы данных. Единицы данных о поверхности содержатся в одном из нескольких квадратных рамок, представленных размером рамки и Z-значением нижнего правого угла. С большой долей вероятности переход к смежной рамке осуществляется одним или несколькими относительно маленькими поисками.

Связанные структурыПравить

В качестве альтернативы предлагается использовать кривую Гильберта, поскольку она имеет лучшее сохраняющее порядок поведение, но вычисления в этом случае будут существенно более сложными, что приводит к сильной загрузке процессора. Исходные коды BIGMIN как для кривой Z-порядка, так и для кривой гильберта описаны в патенте Х. Тропфа.

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

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

Линейная алгебраПравить

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

Булук и др. предложили структуру представления разреженной матрицы для распараллеливания умножения вектора на матрицу. В этом представлении ненулевые элементы расположены в Z-порядке.

Наложение текстурыПравить

Некоторые графические процессоры хранят текстуры в Z-порядке для увеличения пространственной локальности ссылок^[en] во время растеризации текстуры. Это позволяет строкам кэша^[en] представлять квадратные мозаики, увеличивая вероятность, что близкие запросы окажутся в кэше. Это существенно, поскольку визуализация в трёхмерном пространстве вовлекает произвольные трансформации (вращение, масштабирование, перспектива и искривление поверхностей). Могут использоваться и другие мозаичные форматы.

См. такжеПравить

• Заполняющая пространство кривая
• UB-дерево
• Кривая Гильберта
• R-дерево Гильберта
• Пространственный индекс
• Geohash^[en]
• Сохраняющее расстояние хеширование^[en]
• Представление матрицы^[en]

ЛитератураПравить

• G. M. Morton. A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing. — Ottawa, Canada: IBM Ltd., 1966. — (Technical Report).
• H. Samet. Foundations of Multidimensional and Metric Data Structures. — San Francisco: Morgan-Kaufmann, 2006. — ISBN 978-0123694461.
• M. Bern, D. Eppstein, S.-H. Teng. Parallel construction of quadtrees and quality triangulations // Int. J. Comp. Geom. & Appl.. — 1999. — Т. 9, вып. 6. — С. 517–532. — doi:10.1142/S0218195999000303.
• I. Gargantini. An effective way to represent quadtrees // Communications of the ACM. — 1982. — Т. 25, вып. 12. — С. 905–910. — doi:10.1145/358728.358741.
• M. Connor, P. Kumar. IEEE Transactions on Visualization and Computer Graphics. — 2009.
• S. Har-Peled. Data structures for geometric approximation. — 2010.
• Volker Gaede, Oliver Guenther. Multidimensional access methods // ACM Computing Surveys. — 1998. — Т. 30, вып. 2. — С. 170–231. — doi:10.1145/280277.280279.
• Frank Ramsak, Volker Markl, Robert Fenk, Martin Zirkel, Klaus Elhardt, Rudolf Bayer. Int. Conf. on Very Large Databases (VLDB). — 2000. — С. 263–272.
• Патент США № 7 321 890 от 22 января 2008. Database system and method for organizing data elements according to a Hilbert curve. Описание патента на сайте Ведомства по патентам и товарным знакам США.
• Vinod Valsalam, Anthony Skjellum. A framework for high-performance matrix multiplication based on hierarchical abstractions, algorithms and optimized low-level kernels // Concurrency and Computation: Practice and Experience. — 2002. — Вып. 14(10). — С. 805-839. — doi:10.1002/cpe.630.
• H. Tropf, H. Herzog. Multidimensional Range Search in Dynamically Balanced Trees // Angewandte Informatik. — 1981. — Т. 2. — С. 71–77.
• T. Chan. ACM-SIAM Symposium on Discrete Algorithms. — 2002.

СсылкиПравить

• STANN: A library for approximate nearest neighbor search, using Z-order curve
• Methods for programming bit interleaving, Sean Eron Anderson, Stanford University