Árbol R de Hilbert

Un árbol R de Hilbert , una variante de un árbol R , es una indexación de objetos multidimensionales como líneas, regiones bidimensionales, objetos tridimensionales u objetos parametrizados de dimensiones superiores. Pueden entenderse como una extensión de árboles B+ a objetos multidimensionales.

El rendimiento de los árboles R depende de la calidad del algoritmo que agrupa los datos en rectángulos. Los árboles R usan curvas que llenan el espacio , más específicamente las curvas de Hilbert , para organizar objetos linealmente en rectángulos.

Hay dos tipos de Hilbert R-Trees, uno para datos estáticos y otro para datos dinámicos. En ambos casos, se utilizan curvas de Hilbert que llenan el espacio para obtener un mejor ordenamiento de objetos multidimensionales. Este orden es "bueno" en el sentido de que debe agrupar datos "similares" en rectángulos, minimizando el área y el perímetro de estos Rectángulos delimitadores mínimos (MBR) Los árboles R de Hilbert empaquetados son adecuados para datos estáticos que se actualizan con muy poca frecuencia o no se actualizan en absoluto.

Dynamic Hilbert R-Trees son adecuados para datos mutables donde las inserciones, eliminaciones o actualizaciones ocurren en tiempo real. Además, los árboles R dinámicos de Hilbert utilizan un mecanismo flexible de división diferida, que mejora el manejo del espacio. Cada nodo tiene un conjunto bien definido de nodos hermanos (padre único). Al ajustar la política de división, con la ayuda de los árboles R de Hilbert, puede obtener el grado de procesamiento espacial al nivel deseado. Los árboles R de Hilbert clasifican los rectángulos de acuerdo con las distancias de Hilbert de los centros de los rectángulos (MBR). (La distancia de Hilbert de un punto es igual a la longitud de la curva de Hilbert desde el comienzo de la curva hasta el punto). Por el contrario, otras variantes de árboles R no tienen mecanismos para controlar el manejo del espacio.

Idea principal

Aunque el siguiente ejemplo se refiere a un entorno estático, explica los principios intuitivos detrás de la construcción de buenos árboles R. Estos principios son válidos tanto para datos estáticos como dinámicos. Roussopoulos y Leifker propusieron un método para construir un árbol R empaquetado que logra un procesamiento de casi el 100%. La idea es ordenar los datos por coordenadas x o y desde una esquina del rectángulo. Ordenar por cualquiera de las cuatro esquinas produce resultados similares. En este artículo, los puntos y los rectángulos se ordenan en relación con la coordenada x de la esquina inferior izquierda del rectángulo, y el método de Roussopoulos y Leifker se denominará "árbol R empaquetado en x". El método recorre una lista ordenada de rectángulos. Se asignan rectángulos sucesivos a la misma hoja del árbol R hasta que el nodo está lleno. Luego se crea una nueva hoja y continúa la exploración de la lista ordenada. Así, los nodos del árbol R resultante estarán completamente empaquetados, con la posible excepción del último nodo de cada nivel. Por lo tanto, el procesamiento espacial está cerca del 100%. Los niveles más altos del árbol se crean de manera similar.

La figura 1 muestra los problemas de los árboles R empaquetados en x. La figura (derecha) muestra los nodos del árbol R obtenidos por este método para los puntos que se muestran a la izquierda. El hecho de que los nodos principales resultantes cubran un área pequeña explica la rápida degradación de las solicitudes de puntos. Sin embargo, el gran perímetro de los rectángulos explica por qué las consultas de áreas se degradan rápidamente. Esto es coherente con las fórmulas analíticas para el rendimiento de los árboles R [1] . Es intuitivamente claro que el algoritmo de empaquetado debe asignar puntos cercanos al mismo nodo. Ignorar la coordenada y por un "árbol R empaquetado en x" viola esta regla general.

Figura 1: [Izquierda] 200 puntos espaciados uniformemente. [Derecha] MBR de nodos generados por el algoritmo " R-tree x-packing "

Curva de Hilbert

La curva de Hilbert inicial en una red de 2x2, indicada como H 1 , se muestra en la Figura 2. Para obtener una curva de orden i, cada vértice de la curva principal se reemplaza por una curva de orden i - 1, rotada y/o reflejada como necesario. La Figura 2 también muestra las curvas de Hilbert de orden dos y tres. Como el orden de la curva tiende al infinito, como otras curvas que llenan el espacio, la curva se convierte en un fractal con una dimensión fractal de dos [1] [2] . La curva de Hilbert se puede generalizar a dimensiones superiores. Un algoritmo para dibujar una curva bidimensional de un orden dado se puede encontrar en Griffiths [3] y Jagadish [2] . Bialli [4] proporcionó un algoritmo para dimensiones más altas .

La curva que llena el espacio crea un orden lineal de los puntos de la red. Esta ruta se puede construir comenzando desde un extremo de la curva al otro, pasando todos los puntos hasta el final de la curva. La Figura 2 muestra uno de esos pedidos para una red de 4x4 (ver la curva H 2 ). Por ejemplo, el punto (0,0) en la curva H 2 tiene una distancia de 0 y el punto (1,1) tiene una distancia de 2. La distancia de Hilbert de un rectángulo es, por definición, la distancia de Hilbert de su centro.

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

Árboles R de Hilbert empaquetados

La curva de Hilbert define un orden lineal en los rectángulos de datos. Recorriendo la lista ordenada, asignamos cada conjunto de rectángulos a un nodo en el árbol R. Como resultado, muchos rectángulos de datos en el mismo nodo estarán cerca uno del otro en orden lineal, y lo más probable es que se cierren en el espacio natural. Por lo tanto, los nodos resultantes del R-tree tendrán un área pequeña. La figura 2 muestra las razones por las que los métodos basados ​​en las curvas de Hilbert conducen a un buen rendimiento. Los datos consisten en puntos (igual que en la Figura 1). Al agrupar los puntos según sus distancias de Hilbert, los MBR de los nodos del árbol R resultantes suelen ser pequeños rectángulos casi cuadrados. Esto significa que es probable que los nodos tengan áreas y perímetros pequeños. Los valores de área pequeña dan como resultado un buen rendimiento de consulta de puntos. Las áreas pequeñas y los perímetros pequeños dan como resultado un buen rendimiento para consultas grandes.

Algoritmo de empaquetado de Hilbert-Pack

(Algoritmo de empaquetado de rectángulos R-tree)
Paso 1. Calcular la distancia de Hilbert para cada rectángulo de datos
Paso 2. Ordenar los rectángulos por distancia de Hilbert ascendente
Paso 3. /* Crear hojas (nivel l = 0) */

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

Esto supone que los datos son estáticos o cambian con poca frecuencia. El algoritmo es un algoritmo heurístico simple para construir un árbol R con un manejo de espacio del 100 % y también tiene un buen tiempo de respuesta.

Árboles R dinámicos de Hilbert

El rendimiento de los árboles R depende de la calidad del algoritmo para agrupar datos en rectángulos en un nodo. Los árboles R de Hilbert utilizan curvas que llenan el espacio con una ordenación lineal de rectángulos. La distancia de Hilbert de un rectángulo es por definición igual a la distancia de su centro.

Estructura de árbol

El árbol R de Hilbert tiene la siguiente estructura. La hoja contiene un máximo de C l elementos, cada uno de la forma (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 high ), y obj-id es un puntero a la entrada de descripción del objeto. La principal diferencia entre un árbol R de Hilbert y un árbol R* [5] es que los nodos que no son hojas contienen información LHV (valor más grande de Hilbert). Por lo tanto, los nodos que no son hojas en el árbol R contienen como máximo C n elementos de la forma (R, ptr, LHV), donde C n es la capacidad del nodo que no es hoja, R es el MBR que incluye a todos los descendientes de este nodo, ptr es el puntero por hijo, y LHV es la distancia de Hilbert más grande de los datos en el cuadro delimitador R. Tenga en cuenta que dado que un nodo que no es una hoja tiene como su LHV la distancia de Hilbert de uno de sus hijos, no hay costo para calcular las distancias de Hilbert MBR de nodos no hoja. La figura 3 ilustra algunas cajas organizadas en un árbol R de Hilbert. Las distancias de Hilbert de los centros son los números alrededor de los símbolos "x" (que se muestran solo para el nodo principal "II"). Los valores de LHV se dan entre [paréntesis]. La Figura 4 muestra cómo se almacena en el disco el árbol de la Figura 3. El contenido del nodo padre "II" se muestra con más detalle. Cualquier rectángulo de datos del nodo "I" tiene un valor de v ≤33. Asimismo, cualquier rectángulo de nodo "II" tiene una distancia de Hilbert mayor que 33 y menor que 107, y así sucesivamente.

Figura 3: Cuadros de datos organizados en un árbol R de Hilbert (las distancias de Hilbert y los valores de LHV están entre paréntesis)

Un árbol R simple rompe un nodo en caso de desbordamiento, creando dos nodos. Esta política se denomina política de división de 1 a 2. Puede diferir la división y convertir dos nodos en tres. Tenga en cuenta que esta política es similar a la política de partición del árbol B*. Este método se denomina política de división de 2 a 3. En el caso general, podemos hablar de la política de desdoblamiento s-in-(s+1), donde s es el orden de la política de desdoblamiento. Para implementar la política de división de orden s, un nodo abarrotado intenta poner algunos nodos en uno de sus parientes s - 1 (nodos en el mismo nivel). Si están todos llenos, entonces necesita dividir s-into-(s+1). Estos parientes s -1 se denominan nodos cooperantes. Los algoritmos de manejo de búsqueda, inserción y desbordamiento se describen en detalle a continuación.

Buscar

El algoritmo de búsqueda es similar a los algoritmos en otras variantes de R-trees. Comenzando desde la raíz, el algoritmo desciende por el árbol y verifica todos los arcos que intersecan el rectángulo de búsqueda. En la hoja, el algoritmo incluye todos los elementos de la ventana de consulta que se encontraron.

Procedimiento Buscar(nodo Raíz, rectángulo w):
S1. Buscando nudos que no sean hojas:

Iniciamos la búsqueda de cada elemento cuyo MBR cae en la ventana de consulta w.

S2. Búsqueda de hojas:

Enumeramos todos los elementos que caen en la ventana de consulta como candidatos.

Figura 4: Estructura del archivo R-tree de Hilbert

Insertar

Para insertar un nuevo rectángulo r en el árbol R de Hilbert, se utiliza como clave la distancia de Hilbert h del centro del nuevo rectángulo. En cada nivel, entre todos los elementos del nivel, se selecciona un nodo con un valor LHV mínimo mayor que h. Si se alcanza la hoja, se inserta en ella el rectángulo r en el orden correcto según el valor de h. Después de insertar el nuevo rectángulo en la hoja N, se ejecuta el procedimiento Tree Reconciliation para cambiar los valores de MBR y LHV en los nodos de nivel superior.

Procedimiento Insertar (Nodo raíz, rectángulo r) : /* Inserta un nuevo rectángulo r en el árbol R de Hilbert.
h es la distancia de Hilbert del rectángulo*/
I1. Encontrar la hoja correcta:

CallSearchList (r, h) para seleccionar la hoja L en la que incluir r.

I2. Inserte r en la hoja L:

Si L tiene una ranura vacía, inserte r en L a un lugar adecuado según el orden de distancias de Hilbert y regreso. Si L está lleno, llame al procedimiento Manejar desbordamiento (L,r), que devuelve una nueva hoja si es necesario dividir,

I3. Propagando los cambios:

Formamos un conjunto S que contiene L, nodos cooperativos y una hoja nueva (si la hay) Iniciamos el procedimiento Matching the Tree (S).

I4. Aumentar la altura del árbol:

Si la propagación de cambios provoca divisiones de raíz, cree una nueva raíz cuyos hijos son los dos nodos resultantes de dividir la raíz.

Procedimiento FindSheet(rectangle r, integer h) :
/* Devuelve la hoja en la que colocar el nuevo rectángulo r. */
C1. Inicialización:

Establezca N como la raíz.

C2. Comprobación de hoja:

Si N es una hoja, devuelve N.

C3. Selección de un subárbol:

Si N no es una hoja, seleccione el elemento (R, ptr, LHV) con un LHV mínimo superior a h.

C4. Bajamos hasta llegar a la hoja:

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

Reconciliación del árbol de procedimientos (conjunto S) :
/* S es el conjunto de nodos que contiene los nodos que se cambiarán,
sus nodos cooperantes (si se produjo un desbordamiento)
y el nodo NN creado (si se realizó una división de nodos).
El procedimiento asciende desde la hoja hasta la raíz, cambiando el MBR y el LHV de los nodos que cubren los nodos en S.
El procedimiento maneja las divisiones de nodos (si las hay) */
A1. Si llegamos a la raíz, nos detenemos.
A2. División de nodos de procesamiento:

Sea Np el padre del nodo N. Si el nodo N se ha dividido, sea NN el nuevo nodo. Inserte NN en Np en el orden correcto de acuerdo con su distancia de Hilbert, si hay espacio. De lo contrario, llamamos al procedimiento Overflow Handling (Np, NN). Si el nodo Np se ha dividido, sea PP el nuevo nodo.

A3. Cambie los valores de MBR y LHV en el nivel principal:

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

A4. Pasando al siguiente nivel:

S se convierte en el conjunto de nodos padres P, NN = PP si se dividió Np. ir a A1.

Eliminación

En un árbol R de Hilbert, no es necesario volver a insertar los nodos colgantes hasta que desaparezca el nodo principal. En cambio, las claves que se pueden tomar de los nodos subyacentes se fusionan con elementos del mismo nivel. Esto es posible porque los nodos tienen un ordenamiento claro (según LHV). Por el contrario, no existe tal concepto para los árboles R. Tenga en cuenta que la operación de eliminación requiere s nodos cooperantes, mientras que la operación de inserción requiere s - 1 elementos.

Procedimiento Borrar(r) :
D1. Encontrar una hoja:

Buscamos la ocurrencia exacta de la hoja L, que contiene r.

D2. Quitar r :

Retire r del nodo L.

D3. Si L está vacío

tomamos algunos elementos de los nodos cooperantes. si no existen tales elementos, traer s + 1 nodos a s nodos, recalcular los nodos recibidos.

D4. Cambiamos los valores de MBR y LHV en los niveles padre.

forman un conjunto S que contiene L y su cooperativa nodos (si se produce un desbordamiento). llama a MatchTree(S).

Manejo de desbordamiento

El procedimiento de manejo de desbordamiento en un árbol R de Hilbert maneja los nodos de desbordamiento moviendo algunos elementos a uno de los nodos cooperativos s - 1 o dividiendo los nodos s en nodos s + 1.

Manejo de desbordamiento del procedimiento (nodo N, rectángulo r) :
/* devuelve un nuevo nodo si se ha producido una división. */
H1. Sea ε un conjunto que contiene todos los elementos de N

y sus s - 1 nodos cooperantes.

H2. Sumamos r a ε.
H3. Si al menos uno de los s - 1 nodos cooperantes no está lleno,

distribuir ε uniformemente sobre s según las distancias de Hilbert.

H4. Si todos los nodos cooperativos están llenos,

crea el nodo NN y distribuye ε uniformemente sobre s + 1 nodos según distancias de Hilbert volver N. N.

Notas

  1. ↑ 1 2 Kamel, Faloutsos, 1993 , p. 490-499.
  2. ↑ 1 2 Jagadish, 1990 , pág. 332-342.
  3. ↑ Griffiths, 1986 , pág. 403-411.
  4. ↑ Bially, 1969 , pág. 658-664.
  5. ↑ Beckmann, Kriegel, Schneider, Seeger 1990 , pág. 322.

Literatura