Hispanopedia Wiki
Articulo de referencia

Hilbert R-tree

El árbol R de Hilbert , una variante del árbol R , es un índice para objetos multidimensionales como líneas, regiones, objetos 3D u objetos paramétricos basados ​​en característ...

Hispanopedia WikiContenido en espanolLectura gratuita

El árbol R de Hilbert , una variante del árbol R , es un índice para objetos multidimensionales como líneas, regiones, objetos 3D u objetos paramétricos basados ​​en características de alta dimensión. Puede considerarse una extensión del árbol B+ para objetos multidimensionales.

El rendimiento de los árboles R depende de la calidad del algoritmo que agrupa los rectángulos de datos en un nodo. Los árboles R de Hilbert utilizan curvas que llenan el espacio , y específicamente la curva de Hilbert , para imponer un orden lineal a los rectángulos de datos.

Existen dos tipos de árboles R de Hilbert: uno para bases de datos estáticas y otro para bases de datos dinámicas . En ambos casos, se utilizan curvas de Hilbert que llenan el espacio para lograr un mejor ordenamiento de los objetos multidimensionales en el nodo. Este ordenamiento debe ser óptimo, es decir, debe agrupar rectángulos de datos similares para minimizar el área y el perímetro de los rectángulos delimitadores mínimos (MBR) resultantes. Los árboles R de Hilbert compactos son adecuados para bases de datos estáticas con actualizaciones muy poco frecuentes o sin actualizaciones.

El árbol R de Hilbert dinámico es adecuado para bases de datos dinámicas donde las inserciones, eliminaciones o actualizaciones pueden ocurrir en tiempo real. Además, los árboles R de Hilbert dinámicos emplean un mecanismo de división diferida flexible para aumentar la utilización del espacio. Cada nodo tiene un conjunto bien definido de nodos hermanos. Esto se logra proponiendo un ordenamiento en los nodos del árbol R. El árbol R de Hilbert ordena los rectángulos según el valor de Hilbert del centro de los rectángulos (es decir, MBR). (El valor de Hilbert de un punto es la longitud de la curva de Hilbert desde el origen hasta el punto). Dado el ordenamiento, cada nodo tiene un conjunto bien definido de nodos hermanos; por lo tanto, se puede utilizar la división diferida. Al ajustar la política de división, el árbol R de Hilbert puede lograr un grado de utilización del espacio tan alto como se desee. Por el contrario, otras variantes de árboles R no tienen control sobre la utilización del espacio.

La idea básica

Aunque el siguiente ejemplo corresponde a un entorno estático, explica los principios intuitivos para un buen diseño de árboles R. Estos principios son válidos tanto para bases de datos estáticas como dinámicas.

Roussopoulos y Leifker propusieron un método para construir un árbol R compacto que logra una utilización del espacio cercana al 100%. La idea consiste en ordenar los datos según la coordenada x o y de una de las esquinas de los rectángulos. Ordenar según cualquiera de las cuatro coordenadas produce resultados similares. En este análisis, los puntos o rectángulos se ordenan según la coordenada x de la esquina inferior izquierda del rectángulo, lo que se conoce como un "árbol R compacto lowx". La lista ordenada de rectángulos se recorre; los rectángulos sucesivos se asignan al mismo nodo hoja del árbol R hasta que este se llena; entonces se crea un nuevo nodo hoja y se continúa recorriendo la lista ordenada. De esta forma, los nodos del árbol R resultante estarán completamente compactos, con la posible excepción del último nodo de cada nivel. Esto da como resultado una utilización del espacio cercana al 100%. Los niveles superiores del árbol se crean de forma similar.

La Figura 1 resalta el problema del árbol R empaquetado lowx. La Figura 1 [Derecha] muestra los nodos hoja del árbol R que el método de empaquetado lowx creará para los puntos de la Figura 1 [Izquierda]. El hecho de que los nodos padre resultantes cubran un área pequeña explica por qué el árbol R empaquetado lowx logra un rendimiento excelente para consultas de puntos. Sin embargo, el hecho de que los padres tengan perímetros grandes explica la degradación del rendimiento para consultas de regiones. Esto es consistente con las fórmulas analíticas para el rendimiento del árbol R. [ 1 ] Intuitivamente, el algoritmo de empaquetado debería idealmente asignar puntos cercanos al mismo nodo hoja. La ignorancia de la coordenada y por parte del árbol R empaquetado lowx tiende a violar esta regla empírica.

figura1 izquierdafigura1 derecha

Figura 1: [Izquierda] 200 puntos distribuidos uniformemente; [Derecha] MBR de nodos generados por el algoritmo "lowx packed R-tree".

La siguiente sección describe dos variantes de los árboles R de Hilbert. El primer índice es adecuado para bases de datos estáticas donde las actualizaciones son muy poco frecuentes o inexistentes. Los nodos del árbol R resultante estarán completamente empaquetados, con la posible excepción del último nodo de cada nivel. Por lo tanto, la utilización del espacio es de aproximadamente el 100 %; esta estructura se denomina árbol R de Hilbert empaquetado. El segundo índice, denominado árbol R de Hilbert dinámico, admite inserciones y eliminaciones, y es adecuado para entornos dinámicos.

Árboles R de Hilbert compactos

A continuación se presenta una breve introducción a la curva de Hilbert . La curva de Hilbert básica en una cuadrícula de 2x2, denotada por H 1, se muestra en la Figura 2. Para derivar una curva de orden i, cada vértice de la curva básica se reemplaza por la curva de orden i – 1, que puede rotarse y/o reflejarse adecuadamente. La Figura 2 también muestra las curvas de Hilbert de orden dos y tres. Cuando el orden de la curva tiende a infinito, como otras curvas que llenan el espacio, la curva resultante es un fractal, con una dimensión fractal de dos. [ 1 ] [ 2 ] La curva de Hilbert puede generalizarse para dimensionalidades superiores. Los algoritmos para dibujar la curva bidimensional de un orden dado se pueden encontrar en [ 3 ] y [ 2 ] . Un algoritmo para dimensionalidades superiores se presenta en [ 4 ] .

La trayectoria de una curva que llena el espacio impone un ordenamiento lineal en los puntos de la cuadrícula; esta trayectoria se puede calcular comenzando en un extremo de la curva y siguiéndola hasta el otro extremo. Se pueden calcular los valores de coordenadas reales de cada punto. Sin embargo, para la curva de Hilbert esto es mucho más difícil que, por ejemplo, para la curva de orden Z. La figura 2 muestra un ejemplo de dicho ordenamiento para una cuadrícula de 4x4 (véase la curva H2 ) . Por ejemplo, el punto (0,0) en la curva H2 tiene un valor de Hilbert de 0, mientras que el punto (1,1) tiene un valor de Hilbert de 2. El valor de Hilbert de un rectángulo se define como el valor de Hilbert de su centro.

Curvas de Hilbert de orden 1, 2 y 3

Figura 2: Curvas de Hilbert de orden 1, 2 y 3.

La curva de Hilbert impone un orden lineal a los rectángulos de datos y luego recorre la lista ordenada, asignando cada conjunto de rectángulos C a un nodo en el árbol R. El resultado final es que el conjunto de rectángulos de datos en el mismo nodo estará cerca entre sí en el orden lineal, y muy probablemente en el espacio nativo; por lo tanto, los nodos del árbol R resultantes tendrán áreas más pequeñas. La Figura 2 ilustra las razones intuitivas por las que nuestros métodos basados ​​en Hilbert darán como resultado un buen rendimiento. Los datos están compuestos por puntos (los mismos puntos que se muestran en la Figura 1). Al agrupar los puntos según sus valores de Hilbert, los MBR de los nodos del árbol R resultantes tienden a ser pequeños rectángulos cuadrados. Esto indica que es probable que los nodos tengan áreas y perímetros pequeños. Los valores de área pequeños dan como resultado un buen rendimiento para las consultas de puntos; los valores de área y perímetro pequeños conducen a un buen rendimiento para consultas más grandes.

Algoritmo de Hilbert-Pack

(Empaqueta rectángulos en un árbol R) Paso 1. Calcula el valor de Hilbert para cada rectángulo de datos. Paso 2. Ordena los rectángulos de datos según sus valores de Hilbert ascendentes. Paso 3. /* Crea nodos hoja (nivel l=0) */

  • Mientras (hay más rectángulos)
    • generar un nuevo nodo de árbol R
    • asignar los siguientes rectángulos C a este nodo

Paso 4. /* Crear nodos en el nivel superior (l + 1) */

  • Mientras (hay > 1 nodo en el nivel l)
    • ordenar nodos en nivel l ≥ 0 en tiempo de creación ascendente
    • Repita el paso 3.

Aquí se parte de la premisa de que los datos son estáticos o que la frecuencia de modificación es baja. Se trata de una heurística sencilla para construir un árbol R con una utilización del espacio cercana al 100%, que a su vez tendrá un buen tiempo de respuesta.

Árboles R de Hilbert dinámicos

El rendimiento de los árboles R depende de la calidad del algoritmo que agrupa los rectángulos de datos en un nodo. Los árboles R de Hilbert utilizan curvas que llenan el espacio, y específicamente la curva de Hilbert, para imponer un orden lineal a los rectángulos de datos. El valor de Hilbert de un rectángulo se define como el valor de Hilbert de su centro.

Estructura del árbol

El árbol R de Hilbert tiene la siguiente estructura. Un nodo hoja contiene como máximo C l entradas, cada una de la forma (R, obj_id), donde C l es la capacidad de la hoja, R es el MBR del objeto real (x_low , x_high , y_low , y_high ) y obj_id es un puntero al registro de descripción del objeto. La principal diferencia entre el árbol R de Hilbert y el árbol R* [ 5 ] es que los nodos que no son hojas también contienen información sobre los LHV (Valor de Hilbert más grande). Así, un nodo no hoja en el árbol R de Hilbert contiene como máximo C n entradas de la forma (R, ptr, LHV), donde C n es la capacidad de un nodo no hoja, R es el MBR que encierra a todos los hijos de ese nodo, ptr es un puntero al nodo hijo y LHV es el mayor valor de Hilbert entre los rectángulos de datos encerrados por R. Nótese que, dado que el nodo no hoja elige uno de los valores de Hilbert de los hijos como valor de su propio LHV, no hay coste adicional por calcular los valores de Hilbert del MBR de los nodos no hoja. La figura 3 ilustra algunos rectángulos organizados en un árbol R de Hilbert. Los valores de Hilbert de los centros son los números junto a los símbolos "x" (mostrados solo para el nodo padre "II"). Los LHV están entre corchetes. La figura 4 muestra cómo se almacena en disco el árbol de la figura 3; el contenido del nodo padre "II" se muestra con más detalle. Cada rectángulo de datos en el nodo "I" tiene un valor de Hilbert v ≤33; de manera similar, cada rectángulo en el nodo "II" tiene un valor de Hilbert mayor que 33 y ≤ 107, etc.

Rectángulos de datos organizados en un árbol R de Hilbert

Figura 3: Rectángulos de datos organizados en un árbol R de Hilbert (los valores de Hilbert y los valores de Hilbert más grandes (LHV) están entre corchetes).

Un árbol R simple divide un nodo al producirse un desbordamiento, creando dos nodos a partir del original. Esta política se denomina división 1 a 2. También es posible aplazar la división, esperando hasta que dos nodos se dividan en tres. Cabe destacar que esto es similar a la política de división del árbol B*. Este método se conoce como división 2 a 3.

En general, esto se puede extender a una política de división de s a (s+1), donde s es el orden de la política de división. Para implementar la política de división de orden s, el nodo desbordado intenta enviar algunas de sus entradas a uno de sus s - 1 hermanos; si todos están llenos, entonces se debe realizar una división de s a (s+1). Los s - 1 hermanos se denominan hermanos cooperadores.

A continuación, se describen en detalle los algoritmos para la búsqueda, la inserción y el manejo de desbordamientos.

Búsqueda

El algoritmo de búsqueda es similar al utilizado en otras variantes de R-tree. Partiendo de la raíz, desciende por el árbol y examina todos los nodos que intersecan el rectángulo de consulta. En el nivel de las hojas, informa que todas las entradas que intersecan la ventana de consulta son elementos de datos calificados.

Algoritmo de búsqueda (nodo raíz, rectángulo w): S1. Buscar nodos no hoja:

Invocar la búsqueda para cada entrada cuyo MBR se cruce con la ventana de consulta w.

S2. Buscar nodos hoja:

Informar como candidatos todas las entradas que se crucen con la ventana de consulta.

Rectángulos de datos organizados en un árbol R de Hilbert

Figura 4: Estructura de archivos para el árbol R de Hilbert

Inserción

Para insertar un nuevo rectángulo r en el árbol R de Hilbert, se utiliza como clave el valor de Hilbert h del centro del nuevo rectángulo. En cada nivel, se elige el nodo con el valor LHV mínimo mayor que h entre todos sus hermanos. Al llegar a un nodo hoja, el rectángulo r se inserta en el orden correcto según h. Después de insertar un nuevo rectángulo en un nodo hoja N, se llama a AdjustTree para corregir el MBR y los valores de Hilbert más grandes en los nodos de nivel superior.

Algoritmo Insertar(nodo Raíz, rectángulo r): /* Inserta un nuevo rectángulo r en el árbol R de Hilbert. h es el valor de Hilbert del rectángulo */ I1. Encuentra el nodo hoja apropiado:

Invoca ChooseLeaf(r, h) para seleccionar un nodo hoja L en el que colocar r.

I2. Insertar r en un nodo hoja L:

Si L tiene una ranura vacía, inserte r en L en el
lugar apropiado según el orden de Hilbert y regreso.
Si L está lleno, invoca HandleOverflow(L,r), que
volverá a empezar si la separación era inevitable,

I3. Propagar los cambios hacia arriba:

Forma un conjunto S que contenga a L y sus hermanos cooperadores.
y la hoja nueva (si la hay)
Invocar AdjustTree(S).

I4. Hacer crecer el árbol más alto:

Si la propagación de la división del nodo provocó que la raíz se dividiera, cree
una nueva raíz cuyos hijos son los dos nodos resultantes.

Algoritmo ChooseLeaf(rect r, int h): /* Devuelve el nodo hoja en el que colocar un nuevo rectángulo r. */ C1. Inicializar:

Establezca N como el nodo raíz.

C2. Revisión de hojas:

Si N es una hoja, devuelve N.

C3. Seleccione el subárbol:

Si N no es un nodo hoja, elija la entrada (R, ptr, LHV).
con un valor mínimo de LHV mayor que h.

C4. Descienda hasta llegar a una hoja:

Establezca N en el nodo al que apunta ptr y repita desde C2.

Algoritmo AdjustTree(conjunto S): /* S es un conjunto de nodos que contiene el nodo que se está actualizando, sus hermanos cooperantes (si se ha producido un desbordamiento) y el nodo recién creado NN (si se ha producido una división). La rutina asciende desde el nivel de hoja hacia la raíz, ajustando MBR y LHV de los nodos que cubren los nodos en S. Propaga las divisiones (si las hay) */ A1. Si se alcanza el nivel raíz, detenerse. A2. Propaga la división del nodo hacia arriba:

Sea Np el nodo padre de N.
Si N se ha dividido, sea NN el nuevo nodo.
Inserta NN en Np en el orden correcto según su Hilbert.
valor si hay espacio. De lo contrario, invoque HandleOverflow(Np , NN ).
Si Np se divide, sea PP el nuevo nodo.

A3. Ajuste los MBR y LHV en el nivel superior:

Sea P el conjunto de nodos padres para los nodos en S.
Ajuste adecuadamente los valores correspondientes de MBR y LHV de los nodos en P.

A4. Pasa al siguiente nivel:

Sea S el conjunto de nodos padres P, con
NN = PP, si Np se dividió.
repetir desde A1.

Supresión

En el árbol R de Hilbert, no es necesario reinsertar los nodos huérfanos cuando un nodo padre presenta un desbordamiento. En su lugar, se pueden tomar prestadas claves de los nodos hermanos o el nodo con desbordamiento se fusiona con ellos. Esto es posible porque los nodos tienen un orden claro (según el mayor valor de Hilbert, VHL); en cambio, en los árboles R no existe tal concepto con respecto a los nodos hermanos. Cabe destacar que las operaciones de eliminación requieren s hermanos que cooperen, mientras que las de inserción requieren s - 1 hermanos.

Algoritmo Eliminar(r): D1. Encontrar la hoja del host:

Realiza una búsqueda de coincidencia exacta para encontrar el nodo hoja L.
que contiene r.

D2. Eliminar r  :

Eliminar r del nodo L.

D3. Si L tiene un flujo inferior

Tomando prestadas algunas entradas de hermanos colaboradores.
si todos los hermanos están listos para desbordarse.
fusionar s + 1 a s nodos,
Ajustar los nodos resultantes.

D4. Ajustar MBR y LHV en los niveles parentales.

formen un conjunto S que contiene a L y sus cooperadores
hermanos (si se ha producido un desbordamiento).
invocar AdjustTree(S).

Manejo de desbordamientos

El algoritmo de manejo de desbordamiento en el árbol R de Hilbert trata los nodos desbordados moviendo algunas de las entradas a uno de los s - 1 hermanos cooperantes o dividiendo s nodos en s + 1 nodos.

Algoritmo HandleOverflow(nodo N, rectángulo r): /* devuelve el nuevo nodo si se produjo una división. */ H1. Sea ε un conjunto que contiene todas las entradas de N

y sus hermanos cooperadores s-1.

H2. Sumar r a ε. H3. Si al menos uno de los s - 1 hermanos cooperadores no está completo,

Distribuye ε uniformemente entre los s nodos según los valores de Hilbert.

H4. Si todos los hermanos cooperadores s están llenos,

crear un nuevo nodo NN y
distribuir ε uniformemente entre los s + 1 nodos según
a los valores de Hilbert
devolver NN.

Notas

  1. 1 2 I. Kamel y C. Faloutsos, Sobre el empaquetado de árboles R, Segunda Conferencia Internacional ACM sobre Gestión de Información y Conocimiento (CIKM), páginas 490 – 499, Washington DC, 1993.
  2. 1 2 H. Jagadish. Agrupamiento lineal de objetos con múltiples atributos. En Actas de la Conferencia ACM SIGMOD, páginas 332 – 342, Atlantic City, NJ, mayo de 1990.
  3. ↑ J. Griffiths. Un algoritmo para mostrar una clase de curvas que llenan el espacio, Software-Practice and Experience 16(5), 403 – 411, mayo de 1986.
  4. ↑ T. Bially. Curvas que llenan el espacio. Su generación y su aplicación a la reducción del ancho de banda. IEEE Trans. on Information Theory. IT15(6), 658 – 664, noviembre de 1969.
  5. ↑ Beckmann, N.; Kriegel, HP ; Schneider, R.; Seeger, B. (1990). "El árbol R*: un método de acceso eficiente y robusto para puntos y rectángulos". Actas de la conferencia internacional ACM SIGMOD de 1990 sobre gestión de datos - SIGMOD '90 (PDF) . pág.  322. doi : 10.1145/93597.98741 . ISBN 0897913655. S2CID 11567855 . Archivado del original (PDF) el 17-04-2018 . Recuperado el 02-09-2015 . 

Referencias

  • I. Kamel y C. Faloutsos. Árboles R paralelos. En Actas de la Conferencia ACM SIGMOD, páginas 195-204, San Diego, CA, junio de 1992. También disponible como Informe Técnico UMIACS TR 92-1, CS-TR-2820.
  • I. Kamel y C. Faloutsos. Árbol R de Hilbert: Un árbol R mejorado mediante fractales. En Actas de la Conferencia VLDB, páginas 500-509 , Santiago, Chile, septiembre de 1994. También disponible como Informe Técnico UMIACS TR 93-12.1 CS-TR-3032.1.
  • N. Koudas, C. Faloutsos e I. Kamel. Desagrupamiento de bases de datos espaciales en una arquitectura multicomputadora, Conferencia Internacional sobre la Extensión de la Tecnología de Bases de Datos (EDBT), páginas 592 – 614, 1996.
  • N. Roussopoulos y D. Leifker. Búsqueda espacial directa en bases de datos pictóricas mediante árboles R empaquetados. En Actas de ACM SIGMOD, páginas 17-31 , Austin, Texas, mayo de 1985.
  • M. Schroeder. Fractales, caos, leyes de potencia: minutos desde un paraíso infinito. WH Freeman and Company, Nueva York, 1991.
  • T. Sellis, N. Roussopoulos y C. Faloutsos. El árbol R+: un índice dinámico para objetos multidimensionales. En Actas de la 13.ª Conferencia Internacional sobre Bases de Datos Multidimensionales, páginas 507-518 , Inglaterra, septiembre de 1987.