Árbol R de Hilbert - Hilbert R-tree

El árbol R de Hilbert , una variante del árbol R , es un índice para objetos multidimensionales como líneas, regiones, objetos 3-D u objetos paramétricos basados ​​en características de alta dimensión. Se puede considerar como 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 de relleno de espacio , y específicamente la curva de Hilbert , para imponer un orden lineal en los rectángulos de datos.

Hay 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, las curvas de llenado de espacio de Hilbert se utilizan para lograr un mejor orden de los objetos multidimensionales en el nodo. Este orden tiene que ser "bueno", en el sentido de que 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 empaquetados son adecuados para bases de datos estáticas en las que las actualizaciones son muy raras o en las que no hay ninguna actualización.

El árbol R dinámico de Hilbert es adecuado para bases de datos dinámicas donde pueden ocurrir inserciones, eliminaciones o actualizaciones en tiempo real. Además, los árboles R dinámicos de Hilbert emplean un mecanismo de división diferido flexible para aumentar la utilización del espacio. Cada nodo tiene un conjunto bien definido de nodos hermanos. Esto se hace proponiendo un orden en los nodos del árbol R. El árbol R de Hilbert ordena los rectángulos de acuerdo con 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 orden, cada nodo tiene un conjunto bien definido de nodos hermanos; por 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 del árbol R no tienen control sobre la utilización del espacio.

La idea basica

Aunque el siguiente ejemplo es para un entorno estático, explica los principios intuitivos para un buen diseño de árbol 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 empaquetado que logra casi el 100% de utilización del espacio. La idea es ordenar los datos en la coordenada xoy de una de las esquinas de los rectángulos. Ordenar en cualquiera de las cuatro coordenadas da resultados similares. En esta discusión, los puntos o rectángulos se ordenan en la coordenada x de la esquina inferior izquierda del rectángulo, lo que se conoce como "árbol R empaquetado lowx". Se escanea la lista ordenada de rectángulos; los rectángulos sucesivos se asignan al mismo nodo de hoja del árbol R hasta que ese nodo está lleno; A continuación, se crea un nuevo nodo hoja y continúa el escaneo de la lista ordenada. Por lo tanto, los nodos del árbol R resultante estarán completamente empaquetados, con la posible excepción del último nodo en cada nivel. Esto conduce a una utilización del espacio ≈100%. Los niveles superiores del árbol se crean de forma similar.

La Figura 1 destaca el problema del árbol R empaquetado lowx. La Figura 1 [Derecha] muestra los nodos de hojas del árbol R que el método de empaque 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 puntuales. Sin embargo, el hecho de que los padres tengan grandes perímetros explica la degradación del rendimiento de las consultas regionales. Esto es consistente con las fórmulas analíticas para el desempeño del árbol R. Intuitivamente, el algoritmo de empaquetamiento idealmente debería asignar puntos cercanos al mismo nodo hoja. La ignorancia de la coordenada y por el árbol R empaquetado lowx tiende a violar esta regla empírica.

figura 1 izquierda figura 1 derecha

Figura 1: [Izquierda] 200 puntos distribuidos uniformemente; [Derecha] MBR de nodos generados por el algoritmo "árbol R empaquetado lowx"

La siguiente sección describe dos variantes de los árboles R de Hilbert. El primer índice es adecuado para la base de datos estática en la que las actualizaciones son muy raras o en las que no hay ninguna actualización. Los nodos del árbol R resultante estarán completamente empaquetados, con la posible excepción del último nodo en cada nivel. Por tanto, la utilización del espacio es ≈100%; esta estructura se denomina árbol R de Hilbert empaquetado. El segundo índice, llamado Dynamic Hilbert R-tree, admite inserciones y eliminaciones, y es adecuado para un entorno dinámico.

Árboles R Hilbert empaquetados

A continuación se proporciona 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 apropiadamente y / o reflejado. La Figura 2 también muestra las curvas de Hilbert de orden dos y tres. Cuando el orden de la curva tiende al infinito, como otras curvas de relleno de espacio, la curva resultante es un fractal, con una dimensión fractal de dos. La curva de Hilbert se puede generalizar para dimensiones más altas. Los algoritmos para dibujar la curva bidimensional de un orden dado se pueden encontrar en y. Se proporciona un algoritmo para dimensiones superiores.

La trayectoria de una curva de llenado de espacio impone un orden lineal en los puntos de la cuadrícula; esta ruta puede calcularse comenzando en un extremo de la curva y siguiendo la ruta hasta el otro extremo. Se pueden calcular los valores reales de las coordenadas de cada punto. Sin embargo, para la curva de Hilbert esto es mucho más duro que, por ejemplo, la curva de orden Z . La Figura 2 muestra uno de estos pedidos para una cuadrícula 4x4 (ver curva H 2 ). Por ejemplo, el punto (0,0) en la curva H 2 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 en los rectángulos de datos y luego atraviesa 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 uno del otro en el orden lineal, y muy probablemente en el espacio nativo; por lo tanto, los nodos de á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 se componen de puntos (los mismos puntos que se dan en la Figura 1). Al agrupar los puntos de acuerdo con 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 un área pequeña y perímetros pequeños. Los valores de área pequeña dan como resultado un buen rendimiento para consultas puntuales; Los valores de área pequeña y perímetro pequeño generan un buen rendimiento para consultas más grandes.

Algoritmo Hilbert-Pack

(empaqueta rectángulos en un árbol R)
Paso 1. Calcule el valor de Hilbert para cada rectángulo de datos.
Paso 2. Ordene los rectángulos de datos en valores de Hilbert ascendentes.
Paso 3. / * Cree nodos de hojas (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 un nivel superior (l + 1) * /

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

El supuesto aquí es que los datos son estáticos o que la frecuencia de modificación es baja. Esta es una heurística simple para construir un árbol R con ~ 100% de utilización del espacio que al mismo tiempo tendrá un buen tiempo de respuesta.

Árboles R dinámicos de Hilbert

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 de relleno de espacio, y específicamente la curva de Hilbert, para imponer un orden lineal en los rectángulos de datos. El valor de Hilbert de un rectángulo se define como el valor de Hilbert de su centro.

Estructura de árbol

El árbol R de Hilbert tiene la siguiente estructura. Un nodo hoja contiene como máximo entradas C l , cada una de las formas (R, obj _id) donde C l es la capacidad de la hoja, R es el MBR del objeto real (x bajo , x alto , y bajo , y alto ) 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 * es que los nodos que no son hojas también contienen información sobre los LHV (mayor valor de Hilbert). Por lo tanto, 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 todas las hijos de ese nodo, ptr es un puntero al nodo hijo, y LHV es el valor de Hilbert más grande entre los rectángulos de datos encerrados por R. Observe 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 un costo adicional para 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 cerca de 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 el árbol de la figura 3 en el disco; 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 paréntesis)

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

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

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

buscando

El algoritmo de búsqueda es similar al utilizado en otras variantes del árbol R. Comenzando desde la raíz, desciende por el árbol y examina todos los nodos que se cruzan con el rectángulo de consulta. En el nivel de hoja, informa todas las entradas que se cruzan con la ventana de consulta w como elementos de datos calificados.

Búsqueda de algoritmo (raíz de nodo, rect w):
S1. Buscar nodos sin hojas:

Invoque Buscar para cada entrada cuyo MBR se cruce con la ventana de consulta w.

S2. Buscar nodos hoja:

Informe todas las entradas que se cruzan con la ventana de consulta como candidatos.

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

Figura 4: La 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 mínimo de LHV mayor que h de todos sus hermanos. Cuando se alcanza un nodo hoja, el rectángulo r se inserta en su orden correcto de acuerdo con h. Después de insertar un nuevo rectángulo en un nodo hoja N, se llama a AdjustTree para fijar el MBR y los valores de Hilbert más grandes en los nodos de nivel superior.

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

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

I2. Inserte r en un nodo hoja L:

Si L tiene una ranura vacía, inserte r en L en el
lugar apropiado de acuerdo con el pedido de Hilbert y devolución.
Si L está lleno, invoque HandleOverflow (L, r), que
devolverá una nueva hoja si la división fue inevitable,

I3. Propagar cambios hacia arriba:

Forme un conjunto S que contenga a L, sus hermanos cooperantes
y la nueva hoja (si la hay)
Invoque AdjustTree (S).

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

Si la propagación de la división del nodo hizo 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 para que sea el nodo raíz.

C2. Verificación de hojas:

Si N es una hoja_ devuelve N.

C3. Elija subárbol:

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

C4. Desciende hasta alcanzar una hoja:

Establezca N en el nodo señalado por ptr y repita desde C2.

Algoritmo AdjustTree (conjunto S):
/ * S es un conjunto de nodos que contiene el nodo que se actualiza, sus hermanos que cooperan (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 hoja hacia la raíz, ajustando MBR y LHV de los nodos que cubren los nodos en S. Propaga splits (si los hay) * /
A1. Si se alcanza el nivel de la raíz, deténgase.
A2. Propagar el nodo dividido hacia arriba:

Sea Np el nodo padre de N.
Si N se ha dividido, sea NN el nuevo nodo.
Inserte NN en Np en el orden correcto de acuerdo con su Hilbert
valor si hay espacio. De lo contrario, invoque HandleOverflow (Np, NN).
Si Np está dividido, sea PP el nuevo nodo.

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

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

A4. Subir al siguiente nivel:

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

Supresión

En el árbol R de Hilbert, no es necesario volver a insertar nodos huérfanos cada vez que un nodo padre se desborda. En cambio, las claves se pueden tomar prestadas de los hermanos o el nodo subdesarrollado se fusiona con sus hermanos. Esto es posible porque los nodos tienen un orden claro (de acuerdo con el mayor valor de Hilbert, LHV); por el contrario, en los árboles R no existe tal concepto con respecto a los nodos hermanos. Tenga en cuenta que las operaciones de eliminación requieren s hermanos que cooperen, mientras que las operaciones de inserción requieren s - 1 hermanos.

Eliminación de algoritmo (r):
D1. Encuentra la hoja anfitriona:

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

D2. Eliminar r:

Quite r del nodo L.

D3. Si L se desborda

prestadas algunas entradas de los hermanos colaboradores.
si todos los hermanos están dispuestos a desbordar.
fusionar s + 1 con s nodos,
ajustar los nodos resultantes.

D4. Ajuste MBR y LHV en los niveles de los padres.

formar un conjunto S que contiene L y su cooperante
hermanos (si se ha producido un desbordamiento).
invocar AdjustTree (S).

Manejo de desbordamiento

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

Algoritmo HandleOverflow (nodo N, rect 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 colaboradores s - 1.

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

distribuir ε uniformemente entre los nodos s de acuerdo con los valores de Hilbert.

H4. Si todos los hermanos colaboradores están completos,

crear un nuevo nodo NN y
distribuir ε uniformemente entre los nodos s + 1 de acuerdo con
a los valores de Hilbert
return NN.

Notas

Referencias

  • I. Kamel y C. Faloutsos. Árboles R paralelos. En Proc. of ACM SIGMOD Conf., páginas 195–204 San Diego, CA, junio de 1992. También disponible como Tech. Informe UMIACS TR 92-1, CS-TR-2820.
  • I. Kamel y C. Faloutsos. Árbol R de Hilbert: un árbol R mejorado que utiliza fractales. En Proc. of VLDB Conf., páginas 500–509, Santiago, Chile, septiembre de 1994. También disponible como Tech_ Report UMIACS TR 93-12.1 CS-TR-3032.1.
  • N. Koudas, C. Faloutsos e I. Kamel. Declustering Spatial Databases on a Multi-Computer Architecture, International Conference on Extender 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 utilizando árboles R empaquetados. En Proc. de ACM SIGMOD, páginas 17–31, Austin, TX, mayo de 1985.
  • M. Schroeder. Fractales, caos, leyes de poder: minutos de 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 Proc. 13ª Conferencia Internacional sobre VLDB, páginas 507–518, Inglaterra, septiembre de 1987.