Árbol R

Los árboles R son estructuras de datos en forma de árbol que se utilizan para métodos de acceso espacial , es decir, para indexar información multidimensional como coordenadas geográficas , rectángulos o polígonos . El árbol R fue propuesto por Antonin Guttman en 1984 ^[2] y ha encontrado un uso significativo tanto en contextos teóricos como aplicados. ^[3] Un uso común en el mundo real para un árbol R podría ser almacenar objetos espaciales como ubicaciones de restaurantes o los polígonos de los que están hechos los mapas típicos: calles, edificios, contornos de lagos, costas, etc. y luego encontrar respuestas rápidamente a consultas como "Buscar todos los museos a 2 km de mi ubicación actual", "recuperar todos los segmentos de carretera a 2 km de mi ubicación" (para mostrarlos en un sistema de navegación ) o "buscar la gasolinera más cercana" (aunque sin tener en cuenta las carreteras). El árbol R también puede acelerar la búsqueda del vecino más cercano ^[4] para varias métricas de distancia, incluida la distancia del gran círculo . ^[5]

Idea del árbol R

La idea clave de la estructura de datos es agrupar objetos cercanos y representarlos con su rectángulo delimitador mínimo en el siguiente nivel superior del árbol; la "R" en R-tree es de rectángulo. Dado que todos los objetos se encuentran dentro de este rectángulo delimitador, una consulta que no intersecte el rectángulo delimitador tampoco puede intersectar ninguno de los objetos contenidos. En el nivel de hoja, cada rectángulo describe un único objeto; en niveles superiores, la agregación incluye un número creciente de objetos. Esto también puede verse como una aproximación cada vez más burda del conjunto de datos.

Similar al árbol B , el árbol R también es un árbol de búsqueda balanceado (por lo que todos los nodos de hoja están a la misma profundidad), organiza los datos en páginas y está diseñado para el almacenamiento en disco (como se usa en bases de datos ). Cada página puede contener un número máximo de entradas, a menudo denotado como . También garantiza un llenado mínimo (excepto para el nodo raíz), sin embargo, el mejor rendimiento se ha experimentado con un llenado mínimo del 30% al 40% del número máximo de entradas (los árboles B garantizan el 50% de llenado de página y los árboles B* incluso el 66%). La razón de esto es el equilibrio más complejo requerido para los datos espaciales en comparación con los datos lineales almacenados en árboles B. ${\estilo de visualización M}$

Al igual que con la mayoría de los árboles, los algoritmos de búsqueda (por ejemplo, intersección , contención, búsqueda del vecino más cercano ) son bastante simples. La idea clave es utilizar los cuadros delimitadores para decidir si se debe buscar o no dentro de un subárbol. De esta manera, la mayoría de los nodos del árbol nunca se leen durante una búsqueda. Al igual que los árboles B, los árboles R son adecuados para grandes conjuntos de datos y bases de datos , donde los nodos se pueden paginar en la memoria cuando sea necesario y el árbol completo no se puede mantener en la memoria principal. Incluso si los datos se pueden colocar en la memoria (o almacenar en caché), los árboles R en la mayoría de las aplicaciones prácticas generalmente proporcionarán ventajas de rendimiento sobre la verificación ingenua de todos los objetos cuando el número de objetos es más de unos pocos cientos o más. Sin embargo, para aplicaciones en memoria, existen alternativas similares que pueden proporcionar un rendimiento ligeramente mejor o ser más simples de implementar en la práctica. ^{[ cita requerida ]} Para mantener la computación en memoria para R-tree en un clúster de computadoras donde los nodos de computación están conectados por una red, los investigadores han utilizado RDMA ( acceso directo a memoria remota ) para implementar aplicaciones intensivas en datos bajo R-tree en un entorno distribuido. ^[6] Este enfoque es escalable para aplicaciones cada vez más grandes y logra un alto rendimiento y un rendimiento de baja latencia para R-tree.

La dificultad clave de R-tree es construir un árbol eficiente que, por un lado, esté equilibrado (de modo que los nodos de las hojas estén a la misma altura) y, por otro lado, los rectángulos no cubran demasiado espacio vacío y no se superpongan demasiado (de modo que durante la búsqueda, se deban procesar menos subárboles). Por ejemplo, la idea original de insertar elementos para obtener un árbol eficiente es insertar siempre en el subárbol que requiera la menor ampliación de su cuadro delimitador. Una vez que esa página está llena, los datos se dividen en dos conjuntos que deberían cubrir el área mínima cada uno. La mayor parte de la investigación y las mejoras para R-trees apuntan a mejorar la forma en que se construye el árbol y se pueden agrupar en dos objetivos: construir un árbol eficiente desde cero (conocido como carga masiva) y realizar cambios en un árbol existente (inserción y eliminación).

Los árboles R no garantizan un buen rendimiento en el peor de los casos , pero generalmente funcionan bien con datos del mundo real. ^[7] Si bien tiene más interés teórico, la variante del árbol R de prioridad (cargada en masa) es óptima en el peor de los casos, ^[8] pero debido a la mayor complejidad, hasta ahora no ha recibido mucha atención en aplicaciones prácticas.

Cuando los datos se organizan en un árbol R, los vecinos dentro de una distancia dada r y los k vecinos más cercanos (para cualquier L ^p -Norm ) de todos los puntos se pueden calcular de manera eficiente utilizando una unión espacial. ^[9]^[10] Esto es beneficioso para muchos algoritmos basados en tales consultas, por ejemplo, el Local Outlier Factor . DeLi-Clu, ^[11] Density-Link-Clustering es un algoritmo de análisis de clústeres que utiliza la estructura del árbol R para un tipo similar de unión espacial para calcular de manera eficiente un agrupamiento OPTICS .

Variantes

Algoritmo

Disposición de los datos

Los datos en los árboles R se organizan en páginas que pueden tener una cantidad variable de entradas (hasta un máximo predefinido y, por lo general, por encima de un relleno mínimo). Cada entrada dentro de un nodo que no es una hoja almacena dos piezas de datos: una forma de identificar un nodo secundario y el cuadro delimitador de todas las entradas dentro de este nodo secundario. Los nodos hoja almacenan los datos necesarios para cada nodo secundario, a menudo un punto o cuadro delimitador que representa al nodo secundario y un identificador externo para el nodo secundario. Para los datos de puntos, las entradas de hoja pueden ser solo los puntos mismos. Para los datos de polígonos (que a menudo requieren el almacenamiento de polígonos grandes), la configuración común es almacenar solo el MBR (rectángulo delimitador mínimo) del polígono junto con un identificador único en el árbol.

Buscar

En la búsqueda de rango , la entrada es un rectángulo de búsqueda (Cuadro de consulta). La búsqueda es bastante similar a la búsqueda en un árbol B+ . La búsqueda comienza desde el nodo raíz del árbol. Cada nodo interno contiene un conjunto de rectángulos y punteros al nodo hijo correspondiente y cada nodo hoja contiene los rectángulos de objetos espaciales (el puntero a algún objeto espacial puede estar allí). Para cada rectángulo en un nodo, se debe decidir si se superpone al rectángulo de búsqueda o no. Si es así, también se debe buscar el nodo hijo correspondiente. La búsqueda se realiza de esta manera de manera recursiva hasta que se hayan atravesado todos los nodos superpuestos. Cuando se llega a un nodo hoja, los cuadros delimitadores contenidos (rectángulos) se prueban contra el rectángulo de búsqueda y sus objetos (si los hay) se colocan en el conjunto de resultados si se encuentran dentro del rectángulo de búsqueda.

Para la búsqueda prioritaria, como la búsqueda del vecino más próximo , la consulta consta de un punto o un rectángulo. El nodo raíz se inserta en la cola de prioridad. Hasta que la cola esté vacía o se haya devuelto la cantidad deseada de resultados, la búsqueda continúa procesando la entrada más cercana en la cola. Los nodos de árbol se expanden y sus hijos se vuelven a insertar. Las entradas de hoja se devuelven cuando se encuentran en la cola. ^[12] Este enfoque se puede utilizar con varias métricas de distancia, incluida la distancia del círculo máximo para datos geográficos. ^[5]

Inserción

Para insertar un objeto, se recorre el árbol recursivamente desde el nodo raíz. En cada paso, se examinan todos los rectángulos del nodo del directorio actual y se elige un candidato mediante una heurística, como elegir el rectángulo que requiera menos ampliación. Luego, la búsqueda desciende por esta página hasta llegar a un nodo hoja. Si el nodo hoja está lleno, debe dividirse antes de realizar la inserción. Nuevamente, como una búsqueda exhaustiva es demasiado costosa, se emplea una heurística para dividir el nodo en dos. Al agregar el nodo recién creado al nivel anterior, este nivel puede volver a desbordarse y estos desbordamientos pueden propagarse hasta el nodo raíz; cuando este nodo también se desborda, se crea un nuevo nodo raíz y el árbol aumenta su altura.

Elección del subárbol de inserción

El algoritmo debe decidir en qué subárbol insertar. Cuando un objeto de datos está completamente contenido en un solo rectángulo, la elección es clara. Cuando hay múltiples opciones o rectángulos que necesitan ser ampliados, la elección puede tener un impacto significativo en el rendimiento del árbol.

Los objetos se insertan en el subárbol que necesita la menor ampliación. Se emplea una heurística de mezcla en todo momento. Lo que sucede a continuación es que intenta minimizar la superposición (en caso de empates, prefiere la menor ampliación y luego la menor área); en los niveles superiores, se comporta de manera similar al árbol R, pero en caso de empates nuevamente prefiere el subárbol con un área más pequeña. La superposición reducida de rectángulos en el árbol R* es uno de los beneficios clave sobre el árbol R tradicional.

División de un nodo desbordado

Dado que la redistribución de todos los objetos de un nodo en dos nodos tiene un número exponencial de opciones, se debe emplear una heurística para encontrar la mejor división. En el árbol R clásico, Guttman propuso dos de estas heurísticas, llamadas QuadraticSplit y LinearSplit. En la división cuadrática, el algoritmo busca el par de rectángulos que sea la peor combinación que se pueda tener en el mismo nodo y los coloca como objetos iniciales en los dos nuevos grupos. Luego busca la entrada que tenga la mayor preferencia por uno de los grupos (en términos de aumento de área) y asigna el objeto a este grupo hasta que se asignen todos los objetos (satisfaciendo el relleno mínimo).

Existen otras estrategias de división, como la división de Greene ^[13], la heurística de división del árbol R* ^[14] (que nuevamente intenta minimizar la superposición, pero también prefiere páginas cuadráticas) o el algoritmo de división lineal propuesto por Ang y Tan ^[15] (que, sin embargo, puede producir rectángulos muy irregulares, que tienen un menor rendimiento para muchas consultas de rango y ventana del mundo real). Además de tener una heurística de división más avanzada, el árbol R* también intenta evitar la división de un nodo reinsertando algunos de los miembros del nodo, lo que es similar a la forma en que un árbol B equilibra los nodos desbordados. Se demostró que esto también reduce la superposición y, por lo tanto, aumenta el rendimiento del árbol.

Finalmente, el árbol X ^[16] puede verse como una variante del árbol R* que también puede decidir no dividir un nodo, sino construir un llamado supernodo que contenga todas las entradas adicionales, cuando no encuentra una buena división (en particular para datos de alta dimensión).

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

División cuadrática de Guttman. ^[2]
Las páginas de este árbol se superponen mucho.
División lineal de Guttman. ^[2]
Una estructura aún peor, pero también más rápida de construir.
La división de Greene. ^[13] Las páginas se superponen mucho menos que con la estrategia de Guttman.
División lineal de Ang-Tan. ^[15]
Esta estrategia produce páginas segmentadas, que a menudo dan como resultado un mal rendimiento de consulta.
División topológica del árbol R* . ^[14]
Las páginas se superponen mucho menos, 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 prefiere páginas cuadráticas, lo que produce un mejor rendimiento para aplicaciones de mapas comunes.
Árbol R* cargado en bloque utilizando Sort-Tile-Recursive (STR).
Las páginas de hoja no se superponen en absoluto y las páginas de directorio se superponen muy poco. Este es un árbol muy eficiente, pero requiere que los datos se conozcan completamente de antemano.
Los árboles M son similares a los árboles R, pero utilizan páginas esféricas anidadas.
Sin embargo, dividir estas páginas es mucho más complicado y las páginas suelen superponerse mucho más.

Supresión

Eliminar una entrada de una página puede requerir la actualización de los rectángulos delimitadores de las páginas principales. Sin embargo, cuando una página está llena por debajo de su capacidad máxima, no se equilibrará con sus vecinas. En cambio, la página se disolverá y todos sus elementos secundarios (que pueden ser subárboles, no solo objetos hoja) se volverán a insertar. Si durante este proceso el nodo raíz tiene un solo elemento, la altura del árbol puede disminuir.

Carga a granel

X más cercano: los objetos se ordenan por su primera coordenada ("X") y luego se dividen en páginas del tamaño deseado.
Árbol R de Hilbert empaquetado : variación de Nearest-X, pero ordenando utilizando el valor de Hilbert del centro de un rectángulo en lugar de usar la coordenada X. No hay garantía de que las páginas no se superpongan.
Sort-Tile-Recursive (STR): ^[17] Otra variación de Nearest-X, que estima la cantidad total de hojas requeridas como , el factor de división requerido en cada dimensión para lograr esto como , luego divide repetidamente cada dimensión sucesivamente en particiones de igual tamaño utilizando una clasificación unidimensional. Las páginas resultantes, si ocupan más de una página, se cargan nuevamente de manera masiva utilizando el mismo algoritmo. Para los datos puntuales, los nodos de hoja no se superpondrán y "teselarán" el espacio de datos en páginas de tamaño aproximadamente igual. $l=\lceil {\text{número de objetos}}/{\text{capacidad}}\rceil$ $s=\lceil l^{1/d}\rceil$ ${\estilo de visualización s}$
Minimización de superposición de arriba hacia abajo (OMT): ^[18] Mejora con respecto a STR al utilizar un enfoque de arriba hacia abajo que minimiza las superposiciones entre segmentos y mejora el rendimiento de las consultas.
Árbol R prioritario

Véase también

Árbol de segmentos
Árbol de intervalo : un árbol R degenerado para una dimensión (generalmente tiempo).
Árbol kd
Jerarquía de volumen delimitador
Índice espacial
Esencia

Referencias

^ Árbol R cs.sfu.ca
^ abc Guttman, A. (1984). "R-Trees: A Dynamic Index Structure for Spatial Searching" (PDF) . Actas de la conferencia internacional ACM SIGMOD de 1984 sobre gestión de datos – SIGMOD '84 . pág. 47. doi :10.1145/602259.602266. ISBN 978-0897911283.S2CID876601 .
^ Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). Árboles R: teoría y aplicaciones. Springer. ISBN 978-1-85233-977-7. Recuperado el 8 de octubre de 2011 .
^ Roussopoulos, N.; Kelley, S.; Vincent, FDR (1995). "Consultas de vecino más próximo". Actas de la conferencia internacional ACM SIGMOD de 1995 sobre gestión de datos – SIGMOD '95 . p. 71. doi : 10.1145/223784.223794 . ISBN 0897917316.
^ ab Schubert, E.; Zimek, A.; Kriegel, HP (2013). "Consultas de distancia geodésica en árboles R para indexar datos geográficos". Avances en bases de datos espaciales y temporales . Apuntes de clase en informática. Vol. 8098. pág. 146. doi :10.1007/978-3-642-40235-7_9. ISBN 978-3-642-40234-0.
^ Mengbai Xiao, Hao Wang, Liang Geng, Rubao Lee y Xiaodong Zhang (2022). "Una plataforma informática en memoria habilitada para RDMA para R-tree en clústeres" . Transacciones ACM sobre algoritmos y sistemas espaciales. págs. 1–26. doi : 10.1145/3503513 .{{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace )
^ Hwang, S.; Kwon, K.; Cha, SK; Lee, BS (2003). "Evaluación del rendimiento de las variantes del árbol R de la memoria principal" . Avances en bases de datos espaciales y temporales . Apuntes de clase en informática. Vol. 2750. págs. 10. doi :10.1007/978-3-540-45072-6_2. ISBN . 978-3-540-40535-1.
^ Arge, L. ; De Berg, M.; Haverkort, HJ; Yi, K. (2004). "El árbol R de prioridades" (PDF) . Actas de la conferencia internacional ACM SIGMOD de 2004 sobre gestión de datos – SIGMOD '04. p. 347. doi :10.1145/1007568.1007608. ISBN 978-1581138597. Número de identificación del sujeto 6817500.
^ Brinkhoff, T.; Kriegel, HP ; Seeger, B. (1993). "Procesamiento eficiente de uniones espaciales utilizando árboles R". ACM SIGMOD Record . 22 (2): 237. CiteSeerX 10.1.1.72.4514 . doi :10.1145/170036.170075. S2CID 7810650.
^ Böhm, Christian; Krebs, Florian (1 de septiembre de 2003). "Soporte de aplicaciones KDD mediante la unión de k-vecinos más cercanos". Aplicaciones de bases de datos y sistemas expertos . Apuntes de clase en informática. Vol. 2736. Springer, Berlín, Heidelberg. págs. 504–516. CiteSeerX 10.1.1.71.454 . doi :10.1007/978-3-540-45227-0_50. ISBN . 9783540408062.
^ Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Impulsando la robustez, la completitud, la usabilidad y la eficiencia de la agrupación jerárquica mediante una clasificación de pares más cercanos". En Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). Avances en el descubrimiento de conocimientos y la minería de datos, 10.ª Conferencia Pacífico-Asia, PAKDD 2006, Singapur, 9-12 de abril de 2006, Actas . Apuntes de clase en informática. Vol. 3918. Springer. págs. 119–128. doi :10.1007/11731139_16.
^ Kuan, J.; Lewis, P. (1997). "Búsqueda rápida del vecino más cercano k para la familia de árboles R". Actas de la ICICS, Conferencia internacional sobre información, comunicaciones y procesamiento de señales de 1997. Tema: Tendencias en ingeniería de sistemas de información y comunicaciones multimedia inalámbricas (Cat. No. 97TH8237) . p. 924. doi :10.1109/ICICS.1997.652114. ISBN 0-7803-3676-3.
^ ab Greene, D. (1989). "Análisis de la implementación y el rendimiento de los métodos de acceso a datos espaciales". [1989] Actas. Quinta Conferencia Internacional sobre Ingeniería de Datos . págs. 606–615. doi :10.1109/ICDE.1989.47268. ISBN 978-0-8186-1915-1.S2CID 7957624 .
^ 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" (PDF) . Actas de la conferencia internacional ACM SIGMOD de 1990 sobre gestión de datos – SIGMOD '90 . p. 322. CiteSeerX 10.1.1.129.3731 . doi :10.1145/93597.98741. ISBN 978-0897913652.S2CID11567855 .
^ ab Ang, CH; Tan, TC (1997). "Nuevo algoritmo de división de nodos lineal para árboles R". En Scholl, Michel; Voisard, Agnès (eds.). Actas del 5º Simposio Internacional sobre Avances en Bases de Datos Espaciales (SSD '97), Berlín, Alemania, 15-18 de julio de 1997. Lecture Notes in Computer Science. Vol. 1262. Springer. págs. 337-349. doi :10.1007/3-540-63238-7_38.
^ Berchtold, Stefan; Keim, Daniel A.; Kriegel, Hans-Peter (1996). "El árbol X: una estructura de índice para datos de alta dimensión". Actas de la 22.ª Conferencia VLDB . Bombay, India: 28-39.
^ Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (febrero de 1997). "STR: Un algoritmo simple y eficiente para empaquetamiento de árboles R".
^ Lee, Taewon; Lee, Sukho (junio de 2003). "OMT: algoritmo de carga masiva descendente que minimiza la superposición para R-tree" (PDF) .

Enlaces externos

Medios relacionados con R-tree en Wikimedia Commons