Curva de orden Z

En análisis matemático y ciencias de la computación , las funciones que son orden Z , curva de Lebesgue , curva de relleno de espacio de Morton , ^[1] orden de Morton o código de Morton asignan datos multidimensionales a una dimensión mientras preservan la localidad de los puntos de datos. Se nombra en Francia en honor a Henri Lebesgue , quien lo estudió en 1904, ^[2] y en los Estados Unidos en honor a Guy Macdonald Morton, quien aplicó por primera vez el orden a la secuenciación de archivos en 1966. ^[3] El valor z de un punto en multidimensiones se calcula simplemente intercalando las representaciones binarias de sus valores de coordenadas. Una vez que los datos se clasifican en este orden, se puede usar cualquier estructura de datos unidimensional, como matrices unidimensionales simples , árboles de búsqueda binaria , árboles B , listas de omisión o (con bits significativos bajos truncados) tablas hash . El orden resultante se puede describir de manera equivalente como el orden que se obtendría de un recorrido en profundidad de un quadtree o octree .

La figura siguiente muestra los valores Z para el caso bidimensional con coordenadas enteras 0 ≤  x  ≤ 7, 0 ≤  y  ≤ 7 (mostradas tanto en decimal como en binario). Al intercalar los valores de coordenadas binarias (comenzando por la derecha con el bit x (en azul) y alternando hacia la izquierda con el bit y (en rojo)) se obtienen los valores z binarios (inclinados 45° como se muestra). Al conectar los valores z en su orden numérico se produce la curva recursiva en forma de Z. Los valores Z bidimensionales también se conocen como valores de clave cuádruple.

Los valores Z de las coordenadas x se describen como números binarios de la secuencia de Moser-de Bruijn , que tienen bits distintos de cero solo en sus posiciones pares:

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

La suma y la diferencia de dos valores x se calculan mediante operaciones bit a bit :

x[i+j] = ((x[i] | 0b10101010) + x[j]) y 0b01010101x[i−j] = ((x[i] y 0b01010101) − x[j]) y 0b01010101 si i ≥ j

Esta propiedad se puede utilizar para compensar un valor Z, por ejemplo, en dos dimensiones, las coordenadas superior (y decreciente), inferior (y creciente), izquierda (x decreciente) y derecha (x creciente) del valor Z actual z son :

arriba = (((z y 0b10101010) − 1) y 0b10101010) | (z & 0b01010101)inferior = (((z | 0b01010101) + 1) y 0b10101010) | (z y 0b01010101)izquierda = (((z & 0b01010101) − 1) & 0b01010101) | (z & 0b10101010)derecha = (((z | 0b10101010) + 1) & 0b01010101) | (z y 0b10101010)

Y en general para sumar dos valores Z bidimensionales w y z :

suma = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)

El ordenamiento Z se puede utilizar para construir de manera eficiente un quadtree (2D) o un octree (3D) para un conjunto de puntos. ^{[4] [5]} La idea básica es ordenar el conjunto de entrada según el orden Z. Una vez ordenados, los puntos se pueden almacenar en un árbol de búsqueda binaria y usarse directamente, lo que se denomina quadtree lineal, ^[6] o se pueden usar para construir un quadtree basado en punteros.

Los puntos de entrada suelen escalarse en cada dimensión para que sean números enteros positivos, ya sea como una representación de punto fijo sobre el rango de unidades [0, 1] o correspondiente al tamaño de la palabra de máquina. Ambas representaciones son equivalentes y permiten encontrar el bit distinto de cero de orden más alto en tiempo constante. Cada cuadrado del quadtree tiene una longitud de lado que es una potencia de dos y coordenadas de esquina que son múltiplos de la longitud del lado. Dados dos puntos cualesquiera, el cuadrado derivado para los dos puntos es el cuadrado más pequeño que cubre ambos puntos. El entrelazado de bits de los componentes x e y de cada punto se denomina mezcla de x e y , y se puede extender a dimensiones superiores. ^[4]

Los puntos se pueden ordenar según su orden de mezcla sin intercalar explícitamente los bits. Para ello, para cada dimensión, se examina el bit más significativo de la exclusiva o de las coordenadas de los dos puntos de esa dimensión. La dimensión para la que el bit más significativo es mayor se utiliza entonces para comparar los dos puntos y determinar su orden de mezcla.

La operación or exclusiva oculta los bits de orden superior para los cuales las dos coordenadas son idénticas. Dado que la operación de mezcla intercala bits de orden superior a orden inferior, al identificar la coordenada con el bit más significativo más grande, se identifica el primer bit en el orden de mezcla que difiere, y esa coordenada se puede utilizar para comparar los dos puntos. ^[7] Esto se muestra en el siguiente código Python:

def  cmp_zorder ( lhs ,  rhs )  ->  bool : """Comparar ordenamiento z.""" # Suponga que los objetos de índices son similares a matrices lhs y rhs. assert len ( lhs ) == len ( rhs ) # Contendrá la dimensión más significativa. msd = 0 # Recorrerá las otras dimensiones. for dim in range ( 1 , len ( lhs )): # Verificar si la dimensión actual es más significativa # comparando los bits más significativos. if less_msb ( lhs [ msd ] ^ rhs [ msd ], lhs [ dim ] ^ rhs [ dim ]): msd = dim return lhs [ msd ] < rhs [ msd ]                                

Una forma de determinar si el bit más significativo es menor es comparar el valor mínimo del logaritmo en base 2 de cada punto. Resulta que la siguiente operación es equivalente y solo requiere operaciones o exclusivas: ^[7]

def  less_msb ( x :  int ,  y :  int )  ->  bool :  devuelve  x  <  y  y  x  <  ( x  ^  y )

También es posible comparar números de punto flotante utilizando la misma técnica. La less_msbfunción se modifica para comparar primero los exponentes. Solo cuando son iguales se less_msbutiliza la función estándar sobre las mantisas. ^[8]

Una vez que los puntos están en orden, dos propiedades facilitan la construcción de un árbol cuaternario: la primera es que los puntos contenidos en un cuadrado del árbol cuaternario forman un intervalo contiguo en el orden ordenado. La segunda es que si más de un elemento secundario de un cuadrado contiene un punto de entrada, el cuadrado es el cuadrado derivado de dos puntos adyacentes en el orden ordenado.

Para cada par de puntos adyacentes, se calcula el cuadrado derivado y se determina la longitud de su lado. Para cada cuadrado derivado, el intervalo que lo contiene está limitado por el primer cuadrado más grande a la derecha y a la izquierda en orden ordenado. ^[4] Cada uno de estos intervalos corresponde a un cuadrado en el árbol cuaternario. El resultado de esto es un árbol cuaternario comprimido, donde solo están presentes los nodos que contienen puntos de entrada o dos o más hijos. Se puede construir un árbol cuaternario no comprimido restaurando los nodos faltantes, si se desea.

En lugar de construir un árbol cuaternario basado en punteros, los puntos se pueden mantener en orden ordenado en una estructura de datos como un árbol de búsqueda binario. Esto permite agregar y eliminar puntos en tiempo O (log n ) . Se pueden fusionar dos árboles cuaternarios fusionando los dos conjuntos ordenados de puntos y eliminando los duplicados. La ubicación de los puntos se puede realizar buscando los puntos anteriores y posteriores al punto de consulta en el orden ordenado. Si el árbol cuaternario está comprimido, el nodo predecesor encontrado puede ser una hoja arbitraria dentro del nodo comprimido de interés. En este caso, es necesario encontrar el predecesor del ancestro menos común del punto de consulta y la hoja encontrada. ^[9]

Mediante el entrelazado de bits, los registros de la base de datos se convierten en una secuencia de bits (posiblemente muy larga). Las secuencias de bits se interpretan como números binarios y los datos se ordenan o indexan por los valores binarios, utilizando cualquier estructura de datos unidimensional, como se mencionó en la introducción. Sin embargo, al consultar un rango de búsqueda multidimensional en estos datos, el uso de la búsqueda binaria no es realmente eficiente. Aunque el orden Z preserva bien la localidad, para realizar búsquedas de rango eficientes es necesario un algoritmo para calcular, a partir de un punto encontrado en la estructura de datos, el siguiente valor Z posible que se encuentre en el rango de búsqueda multidimensional:

En este ejemplo, el rango que se está consultando ( x  = 2, ..., 3, y  = 2, ..., 6) se indica mediante el rectángulo punteado. Su valor Z más alto (MAX) es 45. En este ejemplo, el valor F  = 19 se encuentra al buscar una estructura de datos en dirección de valor Z creciente, por lo que tendríamos que buscar en el intervalo entre F y MAX (área sombreada). Para acelerar la búsqueda, se calcularía el siguiente valor Z que está en el rango de búsqueda, llamado BIGMIN (36 en el ejemplo) y solo se buscaría en el intervalo entre BIGMIN y MAX (valores en negrita), saltándose así la mayor parte del área sombreada. La búsqueda en dirección decreciente es análoga a LITMAX, que es el valor Z más alto en el rango de consulta menor que F. El problema BIGMIN se ha planteado por primera vez y su solución se muestra en Tropf y Herzog. ^[10]

Tropf ofrece en 2021 una explicación detallada del algoritmo de cálculo LITMAX/BIGMIN, junto con el código fuente Pascal (3D, fácil de adaptar a nD) y sugerencias sobre cómo manejar datos de punto flotante y posiblemente datos negativos: Aquí, el entrelazado de bits no se realiza explícitamente; la estructura de datos solo tiene punteros a los registros de la base de datos original (sin ordenar). Con una función de comparación de registros general (mayor-menor-igual, en el sentido del valor z), se evitan las complicaciones con secuencias de bits que exceden la longitud de la palabra de la computadora, y el código se puede adaptar fácilmente a cualquier número de dimensiones y a cualquier longitud de palabra clave de registro.

Como el enfoque no depende de la estructura de datos unidimensional elegida, todavía hay libertad de elección para estructurar los datos, por lo que se pueden utilizar métodos bien conocidos, como árboles equilibrados, para manejar datos dinámicos, y mantener el equilibrio del árbol cuando la inserción o eliminación lleva tiempo O(log n). El método también se utiliza en árboles UB (equilibrados), ^[11] .

La libre elección facilita la incorporación del método a bases de datos existentes, a diferencia, por ejemplo, de los árboles R, donde se requieren consideraciones especiales.

La aplicación del método de forma jerárquica (según la estructura de datos en cuestión), opcionalmente en dirección creciente y decreciente, produce una búsqueda de rango multidimensional altamente eficiente que es importante tanto en aplicaciones comerciales como técnicas, por ejemplo, como un procedimiento subyacente a las búsquedas de vecinos más cercanos. El orden Z es uno de los pocos métodos de acceso multidimensional que se ha abierto camino en los sistemas de bases de datos comerciales. ^[12] El método se utiliza en varias aplicaciones técnicas de diferentes campos ^[13] y en sistemas de bases de datos comerciales. ^[14]

Ya en 1966, GMMorton propuso el orden Z para la secuenciación de archivos de una base de datos geográfica estática bidimensional. Las unidades de datos de área están contenidas en uno o unos pocos marcos cuadráticos representados por sus tamaños y valores Z en la esquina inferior derecha, los tamaños cumplen con la jerarquía de orden Z en la posición de la esquina. Con alta probabilidad, el cambio a un marco adyacente se realiza con uno o unos pocos pasos de escaneo relativamente pequeños. ^[3]

Como alternativa, se ha sugerido la curva de Hilbert , ya que tiene un mejor comportamiento de preservación del orden ^[5] y, de hecho, se utilizó en un índice optimizado, la geometría S2. ^[15]

El algoritmo de Strassen para la multiplicación de matrices se basa en dividir las matrices en cuatro bloques y luego dividir recursivamente cada uno de estos bloques en cuatro bloques más pequeños, hasta que los bloques sean elementos únicos (o más prácticamente: hasta alcanzar matrices tan pequeñas que el algoritmo trivial de secuencia de Moser-de Bruijn sea más rápido). La disposición de los elementos de la matriz en orden Z mejora la localidad y tiene la ventaja adicional (en comparación con la ordenación por filas o columnas) de que la subrutina para multiplicar dos bloques no necesita conocer el tamaño total de la matriz, sino solo el tamaño de los bloques y su ubicación en la memoria. Se ha demostrado el uso efectivo de la multiplicación de Strassen con orden Z, véase el artículo de Valsalam y Skjellum de 2002. ^[16]

Buluç et al. presentan una estructura de datos de matriz dispersa que ordena Z sus elementos distintos de cero para permitir la multiplicación paralela de matrices y vectores. ^[17]

Las matrices en álgebra lineal también se pueden recorrer utilizando una curva que llena el espacio. ^[18] Los bucles convencionales recorren una matriz fila por fila. El recorrido con la curva Z permite un acceso eficiente a la jerarquía de memoria . ^[19]

Algunas GPU almacenan mapas de textura en orden Z para aumentar la localidad espacial de referencia durante la rasterización de mapas de textura . Esto permite que las líneas de caché representen mosaicos rectangulares, lo que aumenta la probabilidad de que los accesos cercanos estén en la caché. A mayor escala, también disminuye la probabilidad de los costosos "saltos de página" (es decir, el costo de cambiar filas ) en SDRAM/DDRAM. Esto es importante porque la renderización 3D implica transformaciones arbitrarias (rotaciones, escalado, perspectiva y distorsión por superficies animadas).

Estos formatos suelen denominarse texturas swizzled o texturas twiddled . También se pueden utilizar otros formatos en mosaico.

El algoritmo de Barnes-Hut requiere la construcción de un octree. El almacenamiento de los datos como un árbol basado en punteros requiere muchas desreferencias de punteros secuenciales para iterar sobre el octree en orden de profundidad (algo costoso en una máquina con memoria distribuida). En cambio, si se almacenan los datos en una tabla hash , utilizando el algoritmo hash de octree, la curva de orden Z itera naturalmente el octree en orden de profundidad. ^[5]

• Geohash
• Árbol R de Hilbert
• Álgebra lineal
• Hashing que preserva la localidad
• Representación matricial
• Teorema de Netto
• Árbol de pH
• Índice espacial

• STANN: Una biblioteca para la búsqueda aproximada del vecino más cercano, utilizando una curva de orden Z
• Métodos para programar el entrelazado de bits, Sean Eron Anderson, Universidad de Stanford