R*-árbol

En el procesamiento de datos, los árboles R* son una variante de los árboles R que se utilizan para indexar información espacial. Los árboles R* tienen un costo de construcción ligeramente mayor que los árboles R estándar, ya que es posible que sea necesario reinsertar los datos; pero el árbol resultante normalmente tendrá un mejor rendimiento de consulta. Al igual que el R-tree estándar, puede almacenar datos tanto puntuales como espaciales. Fue propuesto por Norbert Beckmann, Hans-Peter Kriegel , Ralf Schneider y Bernhard Seeger en 1990. ^[1]

Diferencia entre árboles R* y árboles R

La minimización tanto de la cobertura como de la superposición es crucial para el rendimiento de los árboles R. Superposición significa que, al consultar o insertar datos, es necesario expandir más de una rama del árbol (debido a la forma en que los datos se dividen en regiones que pueden superponerse). Una cobertura minimizada mejora el rendimiento de la poda, lo que permite excluir páginas enteras de la búsqueda con mayor frecuencia, en particular para consultas de rango negativo. El árbol R* intenta reducir ambos, utilizando una combinación de un algoritmo de división de nodos revisado y el concepto de reinserción forzada en caso de desbordamiento de nodos. Esto se basa en la observación de que las estructuras de árbol R son muy susceptibles al orden en que se insertan sus entradas, por lo que una estructura construida por inserción (en lugar de cargada en masa) probablemente no sea óptima. La eliminación y reinserción de entradas les permite "encontrar" un lugar en el árbol que puede ser más apropiado que su ubicación original.

Cuando un nodo se desborda, una parte de sus entradas se eliminan del nodo y se reinsertan en el árbol. (Para evitar una cascada indefinida de reinserciones causada por el desbordamiento de nodos posterior, la rutina de reinserción puede llamarse sólo una vez en cada nivel del árbol al insertar una nueva entrada). Esto tiene el efecto de producir grupos de reinserciones más bien agrupados. entradas en los nodos, lo que reduce la cobertura de los nodos. Además, las divisiones de nodos reales a menudo se posponen, lo que provoca un aumento en la ocupación promedio de los nodos. La reinserción puede verse como un método de optimización incremental del árbol que se activa ante el desbordamiento del nodo.

El árbol R* describe tres métricas mediante las cuales se puede cuantificar la calidad de una división. Estos son superposiciones (comunes entre árboles R* y árboles R), definidos como el área de intersección de los cuadros delimitadores de dos grupos; Valor de área, que es la suma del área de dos cuadros delimitadores de grupo y Valor de margen, que es la suma de los perímetros de dos cuadros delimitadores de grupo.

Actuación

La heurística de división mejorada produce páginas que son más rectangulares y, por tanto, mejores para muchas aplicaciones.
El método de reinserción optimiza el árbol existente pero aumenta la complejidad.
Admite de manera eficiente datos puntuales y espaciales al mismo tiempo.

Efecto de diferentes heurísticas de división en una base de datos con distritos postales de Alemania

R-Tree con división cuadrática de Guttman. ^[2]
Hay muchas páginas que se extienden de este a oeste por toda Alemania y las páginas se superponen mucho. Esto no es beneficioso para la mayoría de las aplicaciones, que a menudo solo necesitan un área rectangular pequeña que se cruza con muchas rebanadas.
R-Tree con división lineal Ang-Tan. ^[3]
Si bien los cortes no se extienden tanto como en Guttman, el problema de corte afecta a casi todas las páginas de las hojas. Las páginas hoja se superponen poco, pero las páginas del directorio sí.
División topológica del árbol R*. ^[1]
Las páginas se superponen muy poco ya que el árbol R* intenta minimizar la superposición de páginas y las reinserciones optimizaron aún más el árbol. La estrategia de división tampoco prefiere los sectores, por lo que las páginas resultantes son mucho más útiles para aplicaciones de mapas comunes.

Algoritmo y complejidad

El árbol R* utiliza el mismo algoritmo que el árbol R normal para operaciones de consulta y eliminación.
Al insertar, el árbol R* utiliza una estrategia combinada. Para los nodos de hojas, se minimiza la superposición, mientras que para los nodos internos, se minimiza la ampliación y el área.
Al dividir, el árbol R* utiliza una división topológica que elige un eje de división según el perímetro y luego minimiza la superposición.
Además de una estrategia de división mejorada, el árbol R* también intenta evitar divisiones reinsertando objetos y subárboles en el árbol, inspirado en el concepto de equilibrar un árbol B.

Por lo tanto, la complejidad de consulta y eliminación en el peor de los casos es idéntica a la del R-Tree. La estrategia de inserción en el árbol R* es más compleja que la estrategia de división lineal ( ) del árbol R, pero menos compleja que la estrategia de división cuadrática ( ) para un tamaño de página de objetos y tiene poco impacto en la complejidad total. . La complejidad total de la inserción sigue siendo comparable a la del árbol R: las reinserciones afectan como máximo a una rama del árbol y, por lo tanto , las reinserciones son comparables a realizar una división en un árbol R normal. Entonces, en general, la complejidad del árbol R* es la misma que la de un árbol R normal. ${\mathcal {O}}(M\log M)$ ${\mathcal {O}}(M)$ ${\mathcal {O}}(M^{2})$ $M$ ${\mathcal {O}}(\log n)$

Una implementación del algoritmo completo debe abordar muchos casos extremos y situaciones vinculadas que no se analizan aquí.

Referencias

^ ab 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) . pag. 322. doi : 10.1145/93597.98741. ISBN 0897913655.
^ Guttman, A. (1984). "R-Trees: una estructura de índice dinámica para búsqueda espacial". Actas de la conferencia internacional ACM SIGMOD de 1984 sobre gestión de datos - SIGMOD '84 (PDF) . pag. 47. doi : 10.1145/602259.602266. ISBN 0897911288.
^ Ang, CH; Bronceado, TC (1997). "Nuevo algoritmo de división de nodos lineales para árboles R". En Scholl, Michel; Voisard, Agnès (eds.). Actas del Quinto Simposio Internacional sobre Avances en Bases de Datos Espaciales (SSD '97), Berlín, Alemania, 15 al 18 de julio de 1997 . Apuntes de conferencias sobre informática. vol. 1262. Saltador. págs. 337–349. doi :10.1007/3-540-63238-7_38.

enlaces externos

Medios relacionados con R*-tree en Wikimedia Commons