En análisis matemático y la informática , funciones que son orden Z , curva de Lebesgue , curva de llenado de espacio Morton , [1] orden Morton o Morton código mapa de datos multidimensionales a una dimensión , preservando localidad de los puntos de datos. Lleva el nombre de Guy Macdonald Morton , quien aplicó por primera vez la orden para la secuenciación de archivos en 1966. [2] El valor z de un punto en múltiples dimensiones se calcula simplemente intercalando el binariorepresentaciones de sus valores de coordenadas. Una vez que los datos se clasifican en este orden, se puede utilizar cualquier estructura de datos unidimensional, como árboles de búsqueda binaria , árboles B , listas de omisión o (con bits de baja significancia 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 .
Valores de coordenadas
La siguiente figura muestra los valores Z para el caso bidimensional con coordenadas enteras 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (mostrados tanto en decimal como en binario). El entrelazado de los valores de las coordenadas binarias produce valores z binarios como se muestra. La conexión de los valores z en su orden numérico produce la curva en forma de Z recursiva. Los valores Z bidimensionales también se denominan quadkey.
Los valores Z de x se describen como números binarios de la secuencia 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 x se calculan mediante operaciones bit a bit :
x [i + j] = ((x [i] | 0b10101010) + x [j]) & 0b01010101x [ij] = ((x [i] & 0b01010101) - x [j]) & 0b01010101 si i> = j
Esta propiedad se puede utilizar para compensar un valor Z, por ejemplo, en dos dimensiones, las coordenadas hacia la parte superior (y decreciente), inferior (y creciente), izquierda (x decreciente) y derecha (x creciente) del valor Z actual z son:
arriba = (((z & 0b10101010) - 1) & 0b10101010) | (z y 0b01010101)abajo = (((z | 0b01010101) + 1) & 0b10101010) | (z y 0b01010101)izquierda = (((z & 0b01010101) - 1) & 0b01010101) | (z y 0b10101010)derecha = (((z | 0b10101010) + 1) & 0b01010101) | (z y 0b10101010)
Y en general para sumar dos valores de Z bidimensionales w y z :
suma = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)
Construyendo cuadrboles y octrees de manera eficiente
El ordenamiento Z se puede utilizar para construir de manera eficiente un árbol cuádruple (2D) u octárbol (3D) para un conjunto de puntos. [3] [4] La idea básica es ordenar el conjunto de entrada según el orden Z. Una vez ordenados, los puntos pueden almacenarse en un árbol de búsqueda binario y usarse directamente, lo que se llama un árbol cuádruple lineal, [5] o pueden usarse para construir un árbol cuádruple basado en punteros.
Los puntos de entrada generalmente se escalan 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 correspondientes al tamaño de la palabra de la máquina. Ambas representaciones son equivalentes y permiten encontrar el bit distinto de cero de mayor orden en tiempo constante. Cada cuadrado del árbol cuádruple tiene una longitud de lado que es una potencia de dos y coordenadas de esquina que son múltiplos de la longitud de lado. Dados dos puntos cualesquiera, el cuadrado derivado de los dos puntos es el cuadrado más pequeño que cubre ambos puntos. El entrelazado de bits de los componentes xey de cada punto se denomina mezcla de xey, y puede extenderse a dimensiones superiores. [3]
Los puntos se pueden clasificar de acuerdo con su 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 para esa dimensión. La dimensión para la cual el bit más significativo es el más grande se usa luego para comparar los dos puntos para determinar su orden aleatorio.
La operación exclusiva o enmascara los bits de orden superior para los que las dos coordenadas son idénticas. Dado que el orden aleatorio intercala bits de orden superior a orden inferior, la identificación de la coordenada con el bit más grande y más significativo identifica el primer bit del orden aleatorio que difiere, y esa coordenada se puede utilizar para comparar los dos puntos. [6] Esto se muestra en el siguiente código de Python:
def cmp_zorder ( izda , dcha ) -> bool : "" "Comparación de orden z" "" # Suponga izda y dcha matriz de objetos como de los índices. afirmar len ( lhs ) == len ( rhs ) # Contendrá la dimensión más significativa. msd = 0 # Bucle sobre las otras dimensiones. para dim in range ( 1 , len ( lhs )): # Compruebe si la dimensión actual es más significativa # comparando los bits más significativos. si less_msb ( LHS [ msd ] ^ RHS [ msd ], LHS [ dim ] ^ rhs [ dim ]): msd = dim retorno LHS [ msd ] < rhs [ msd ]
Una forma de determinar si el bit más significativo es más pequeño es comparar el piso del logaritmo en base 2 de cada punto. Resulta que la siguiente operación es equivalente y solo requiere operaciones exclusivas o: [6]
def less_msb ( x : int , y : int ) -> bool : return x < y y x < ( x ^ y )
También es posible comparar números de coma flotante utilizando la misma técnica. La función less_msb se modifica para comparar primero los exponentes. Solo cuando son iguales se usa la función estándar less_msb en las mantisas. [7]
Una vez que los puntos están ordenados, dos propiedades facilitan la construcción de un árbol cuádruple: la primera es que los puntos contenidos en un cuadrado del árbol cuádruple forman un intervalo contiguo en el orden ordenado. La segunda es que si más de un hijo 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á delimitado por el primer cuadrado más grande a la derecha y a la izquierda en orden ordenado. [3] Cada uno de estos intervalos corresponde a un cuadrado en el quadtree. El resultado de esto es un quadtree comprimido, donde solo están presentes los nodos que contienen puntos de entrada o dos o más hijos. Se puede construir un quadtree no comprimido restaurando los nodos faltantes, si se desea.
En lugar de construir un árbol cuádruple basado en punteros, los puntos se pueden mantener ordenados en una estructura de datos como un árbol de búsqueda binaria. Esto permite agregar y eliminar puntos en tiempo O (log n). Se pueden fusionar dos quadtrees fusionando los dos conjuntos ordenados de puntos y eliminando los duplicados. La ubicación de los puntos se puede realizar buscando los puntos que preceden y siguen al punto de consulta en el orden ordenado. Si el quadtree 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 antecesor del antepasado menos común del punto de consulta y la hoja encontrada. [8]
Úselo con estructuras de datos unidimensionales para la búsqueda de rango
Aunque se preserva bien la localidad, para búsquedas de rango eficientes es necesario un algoritmo para calcular, desde un punto encontrado en la estructura de datos, el siguiente valor Z que está en el rango de búsqueda multidimensional:
En este ejemplo, el rango que se consulta ( 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 cuando se busca una estructura de datos en la dirección del 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 buscaría en el intervalo entre BIGMIN y MAX (valores en negrita), omitiendo así la mayoría de los sombreados. área. 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 inferior a F. El problema BIGMIN se ha establecido primero y su solución se muestra en Tropf y Herzog. [9] Esta solución también se utiliza en árboles UB ("GetNextZ-address"). Como el enfoque no depende de la estructura de datos unidimensional elegida, todavía existe la libre elección de estructurar los datos, por lo que se pueden usar métodos bien conocidos como árboles balanceados para hacer frente a datos dinámicos (en contraste, por ejemplo, con árboles R donde son necesarias consideraciones especiales). Del mismo modo, esta independencia facilita la incorporación del método en las bases de datos existentes.
La aplicación del método jerárquicamente (según la estructura de datos en cuestión), opcionalmente tanto en dirección ascendente como descendente, 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 introducido en los sistemas de bases de datos comerciales ( base de datos Oracle 1995, [10] Transbase 2000 [11] ).
Ya en 1966, GMMorton propuso el orden Z para la secuenciación de archivos de una base de datos geográfica bidimensional estática. 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 de 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.
Estructuras relacionadas
Como alternativa, se ha sugerido la curva de Hilbert ya que tiene un mejor comportamiento de preservación del orden, [4] y, de hecho, se usó en un índice optimizado, la geometría S2. [12]
Aplicaciones
Álgebra lineal
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 llegar a matrices tan pequeñas que el Moser – de El algoritmo trivial de secuencia de Bruijn es más rápido). Organizar los elementos de la matriz en orden Z mejora la localidad y tiene la ventaja adicional (en comparación con el orden principal de 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 eficaz de la multiplicación de Strassen con orden Z, ver el artículo de 2002 de Valsalam y Skjellum. [13]
Buluç et al. presentan una estructura de datos de matriz dispersa que ordena en Z sus elementos distintos de cero para permitir la multiplicación de matriz-vector en paralelo . [14]
Mapeado de texturas
Algunas GPU almacenan mapas de texturas en orden Z para aumentar la localidad espacial de referencia durante la rasterización del mapa de texturas . 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 costosos, así llamados, "saltos de página" (es decir, el costo de cambiar filas ) en SDRAM / DDRAM. Esto es importante porque el renderizado 3D implica transformaciones arbitrarias (rotaciones, escalado, perspectiva y distorsión por superficies animadas).
Estos formatos se denominan a menudo texturas swizzled o texturas hizo girar . También se pueden utilizar otros formatos de mosaico.
Problema de cuerpo N
El algoritmo de Barnes-Hut requiere la construcción de un árbol oct. Almacenar los datos como un árbol basado en punteros requiere muchas desreferencias de puntero secuenciales para iterar sobre el árbol oct en orden de profundidad (costoso en una máquina de memoria distribuida). En cambio, si uno almacena los datos en una tabla hash , usando el hash del árbol oct , la curva de orden Z itera naturalmente el árbol oct en orden de profundidad. [4]
Ver también
- Curva de llenado de espacio
- UB-árbol
- Curva de Hilbert
- Árbol R de Hilbert
- Índice espacial
- Geohash
- Localidad de referencia
- Localidad preservando el hash
- Representación matricial
- Álgebra lineal
Referencias
- ^ "Especificación abstracta de sistemas de red globales discretos" (PDF) . Consorcio Geoespacial Abierto . 2017.
- ^ Morton, GM (1966), una base de datos geodésica orientada por computadora; and a New Technique in File Sequencing (PDF) , Informe técnico, Ottawa, Canadá: IBM Ltd.
- ^ a b c Berna, M .; Eppstein, D .; Teng, S.-H. (1999), "Construcción paralela de cuadrboles y triangulaciones de calidad", Int. J. Comput. Geom. Apl. , 9 (6): 517–532, CiteSeerX 10.1.1.33.4634 , doi : 10.1142 / S0218195999000303.
- ^ a b c Warren, MS; Salmón, JK (1993). "Un algoritmo de cuerpo N de árbol de octubre con hash paralelo" . Actas de la conferencia ACM / IEEE de 1993 sobre Supercomputación - Supercomputación '93 . Portland, Oregon, Estados Unidos: ACM Press: 12–21. doi : 10.1145 / 169627.169640 . ISBN 978-0-8186-4340-8.
- ^ Gargantini, I. (1982), "Una manera eficaz de representar quadtrees", Comunicaciones del ACM , 25 (12): 905–910, doi : 10.1145 / 358728.358741 , S2CID 14988647.
- ^ a b Chan, T. (2002), "Problemas más cercanos simplificados en la RAM", Simposio ACM-SIAM sobre algoritmos discretos.
- ^ Connor, M .; Kumar, P (2009), "Construcción rápida de gráficos de vecinos k-más cercanos para nubes de puntos", Transacciones IEEE sobre visualización y gráficos por computadora (PDF)
- ^ Har-Peled, S. (2010), Estructuras de datos para aproximación geométrica (PDF)
- ^ Tropf, H .; Herzog, H. (1981), "Búsqueda de rango multidimensional en árboles dinámicamente equilibrados" (PDF) , Angewandte Informatik , 2 : 71–77.
- ^ Gaede, Volker; Guenther, Oliver (1998), "Métodos de acceso multidimensional" (PDF) , ACM Computing Surveys , 30 (2): 170–231, CiteSeerX 10.1.1.35.3473 , doi : 10.1145 / 280277.280279 , S2CID 7075919.
- ^ Ramsak, Frank; Markl, Volker; Fenk, Robert; Zirkel, Martin; Elhardt, Klaus; Bayer, Rudolf (2000), "Integración del árbol UB en un núcleo de sistema de base de datos", Int. Conf. sobre bases de datos muy grandes (VLDB) (PDF) , págs. 263–272, archivado desde el original (PDF) el 4 de marzo de 2016.
- ^ "Geometría S2" .
- ^ Vinod Valsalam, Anthony Skjellum: un marco para la multiplicación de matrices de alto rendimiento basado en abstracciones jerárquicas, algoritmos y núcleos optimizados de bajo nivel. Simultaneidad y cálculo: práctica y experiencia 14 (10): 805-839 (2002) [1] [2]
- ^ Buluç, Aydin; Fineman, Jeremy T .; Frigo, Matteo; Gilbert, John R .; Leiserson, Charles E. (2009). Multiplicación en paralelo de matriz-vector dispersa y matriz-transposición-vector utilizando bloques dispersos comprimidos (PDF) . ACM Symp. sobre paralelismo en algoritmos y arquitecturas. CiteSeerX 10.1.1.211.5256 .
enlaces externos
- STANN: una biblioteca para la búsqueda aproximada de vecinos más cercanos, utilizando la curva de orden Z
- Métodos para programar entrelazado de bits , Sean Eron Anderson, Universidad de Stanford