Hispanopedia Wiki
Articulo de referencia

Árbol R

M n'')"},"search_worst":{"wt":"O(''n'') [https://www2.cs.sfu.ca/CourseCentral/454/jpei/slides/R-Tree.pdf R Tree] cs.sfu.ca "},"insert_avg":{"wt":""},"insert_worst":{"wt":"O(''n'...

Hispanopedia WikiContenido en espanolLectura gratuita
Ejemplo sencillo de un árbol R para rectángulos 2D.
Visualización de un árbol R* para puntos 3D usando ELKI (los cuboides son páginas de directorio).

Los árboles R son estructuras de datos de árbol utilizadas 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 que componen los mapas típicos: calles, edificios, contornos de lagos, costas, etc., y luego encontrar respuestas rápidas a consultas como "Encontrar todos los museos dentro de 2 km de mi ubicación actual", "recuperar todos los segmentos de carretera dentro de 2 km de mi ubicación" (para mostrarlos en un sistema de navegación ) o "encontrar 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 de círculo máximo . [ 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 árbol R significa rectángulo. Dado que todos los objetos se encuentran dentro de este rectángulo delimitador, una consulta que no lo interseque tampoco puede intersecar ninguno de los objetos contenidos. En el nivel hoja, cada rectángulo describe un solo objeto; en niveles superiores, la agregación incluye un número creciente de objetos. Esto también puede interpretarse como una aproximación cada vez más burda del conjunto de datos.

De forma similar al árbol B , el árbol R también es un árbol de búsqueda equilibrado (por lo que todos los nodos hoja están a la misma profundidad), organiza los datos en páginas y está diseñado para su almacenamiento en disco (como se utiliza en las bases de datos ). Cada página puede contener un número máximo de entradas, a menudo denotado comoMETRO{\displaystyle M}También garantiza un llenado mínimo (excepto en el nodo raíz); sin embargo, el mejor rendimiento se ha obtenido con un llenado mínimo del 30 % al 40 % del número máximo de entradas (los árboles B garantizan un llenado de página del 50 %, y los árboles B* incluso del 66 %). Esto se debe al equilibrio más complejo que requieren los datos espaciales en comparación con los datos lineales almacenados en árboles B.

Como ocurre 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 sencillos. La idea clave es utilizar los cuadros delimitadores para decidir si se debe buscar dentro de un subárbol. De esta forma, 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 memoria cuando sea necesario y no se puede mantener todo el árbol en la memoria principal. Incluso si los datos caben en la memoria (o en caché), los árboles R en la mayoría de las aplicaciones prácticas suelen ofrecer ventajas de rendimiento sobre la comprobación ingenua de todos los objetos cuando el número de objetos supera los pocos cientos. Sin embargo, para aplicaciones en memoria, existen alternativas similares que pueden ofrecer un rendimiento ligeramente mejor o ser más sencillas de implementar en la práctica. Para mantener la computación en memoria para árboles R 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 árboles R en un entorno distribuido. [ 6 ] Este enfoque es escalable para aplicaciones cada vez más grandes y logra un alto rendimiento y baja latencia para R-tree.

La principal dificultad de los árboles R radica en construir un árbol eficiente que, por un lado, esté equilibrado (de modo que los nodos hoja tengan la misma altura) y, por otro, cuyos rectángulos no ocupen demasiado espacio vacío ni se superpongan en exceso (de manera que, durante la búsqueda, se procesen menos subárboles). Por ejemplo, la idea original para insertar elementos y obtener un árbol eficiente consiste en insertarlos 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 deben cubrir el área mínima cada uno. La mayor parte de la investigación y las mejoras en los árboles R se centran en optimizar su construcción 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 ] La variante Priority R-tree (cargada en bloque) del árbol R es óptima en el peor de los casos, [ 8 ] pero debido a su mayor complejidad se ha mantenido confinada al estudio teórico y 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 norma L p ) de todos los puntos se pueden calcular eficientemente usando una unión espacial. [ 9 ] [ 10 ] Esto es beneficioso para muchos algoritmos basados ​​en tales consultas, por ejemplo el Factor de Atípicos Locales . DeLi-Clu, [ 11 ] Density-Link-Clustering es un algoritmo de análisis de clústeres que utiliza la estructura de árbol R para un tipo similar de unión espacial para calcular eficientemente un clúster OPTICS .

Variantes

Algoritmo

Diseño de datos

Los datos en los árboles R se organizan en páginas que pueden tener un número variable de entradas (hasta un máximo predefinido y, por lo general, por encima de un mínimo). Cada entrada dentro de un nodo que no es una hoja almacena dos datos: una forma de identificar un nodo hijo y el cuadro delimitador de todas las entradas dentro de este nodo hijo. Los nodos hoja almacenan los datos necesarios para cada hijo, a menudo un punto o cuadro delimitador que representa al hijo y un identificador externo para el hijo. Para datos de puntos, las entradas de las hojas pueden ser simplemente los puntos mismos. Para 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.

El proceso de búsqueda en un árbol R incorpora un enfoque de dos fases que se ajusta al Principio de Filtrado y Refinamiento (PFR) . En esta estructura, los nodos internos actúan como un filtro inicial al excluir rápidamente las regiones del espacio que no se intersecan con la consulta, mientras que los nodos hoja proporcionan una evaluación refinada y precisa al almacenar los objetos espaciales reales.

Específicamente, en la búsqueda por 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 los objetos espaciales (puede haber un puntero a algún objeto espacial). Para cada rectángulo en un nodo, se debe decidir si se superpone o no al rectángulo de búsqueda. Si es así, también se debe buscar en el nodo hijo correspondiente. La búsqueda se realiza de esta manera de forma recursiva hasta que se hayan recorrido todos los nodos superpuestos. Cuando se llega a un nodo hoja, los cuadros delimitadores (rectángulos) contenidos se comparan con el rectángulo de búsqueda y sus objetos (si los hay) se agregan al conjunto de resultados si se encuentran dentro del rectángulo de búsqueda.

Para búsquedas prioritarias como la búsqueda del vecino más cercano , la consulta consiste en un punto o rectángulo. El nodo raíz se inserta en la cola de prioridad. Hasta que la cola esté vacía o se haya devuelto el número deseado de resultados, la búsqueda continúa procesando la entrada más cercana en la cola. Los nodos del árbol se expanden y sus hijos se reinsertan. Las entradas hoja se devuelven cuando se encuentran en la cola. [ 12 ] Este enfoque se puede utilizar con varias métricas de distancia, incluida la distancia geodésica para datos geográficos. [ 5 ]

Inserción

Para insertar un objeto, el árbol se recorre 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 seleccionar el rectángulo que requiere menor ampliación. La búsqueda desciende entonces 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, dado que 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 desbordarse nuevamente, 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 de altura.

Selecció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 obvia. Cuando hay varias opciones o rectángulos que necesitan ampliarse, la elección puede tener un impacto significativo en el rendimiento del árbol.

Los objetos se insertan en el subárbol que requiere menor ampliación. Se emplea una heurística de mezcla en todo el proceso. A continuación, se intenta minimizar la superposición (en caso de empate, se prioriza la menor ampliación y, por lo tanto, la menor área); en los niveles superiores, el comportamiento es similar al del árbol R, pero en caso de empate, se vuelve a priorizar el subárbol con menor área. La menor superposición de rectángulos en el árbol R* es una de las principales ventajas sobre el árbol R tradicional.

Dividir un nodo desbordado

Dado que redistribuir todos los objetos de un nodo en dos nodos implica un número exponencial de opciones, es necesario emplear una heurística para encontrar la mejor división. En el árbol R clásico, Guttman propuso dos heurísticas de este tipo: QuadraticSplit y LinearSplit. En la división cuadrática, el algoritmo busca el par de rectángulos que constituye la peor combinación posible en el mismo nodo y los coloca como objetos iniciales en los dos nuevos grupos. A continuación, 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 dicho grupo hasta que todos los objetos estén asignados (satisfaciendo el llenado 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 también intenta minimizar la superposición, pero 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 son menos eficientes 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 sus miembros, de forma similar a como un árbol B equilibra los nodos desbordados. Se ha demostrado 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 contiene todas las entradas adicionales, cuando no encuentra una buena división (en particular para datos de alta dimensión).

Supresión

Eliminar una entrada de una página puede requerir actualizar los rectángulos delimitadores de las páginas principales. Sin embargo, cuando una página está incompleta, no se equilibrará con sus vecinas. En su lugar, la página se disolverá y todos sus elementos secundarios (que pueden ser subárboles, no solo hojas) se reinsertarán. Si durante este proceso el nodo raíz tiene un solo elemento, la altura del árbol puede disminuir.

Carga a granel

  • Cercano-X: 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 del algoritmo Nearest-X, pero ordenando mediante el valor de Hilbert del centro de un rectángulo en lugar de la coordenada X. No se garantiza que las páginas no se superpongan.
  • Sort-Tile-Recursive (STR): [ 17 ] Otra variación de Nearest-X, que estima el número total de hojas requeridas comol=⌈número de objetos/capacidad⌉{\displaystyle l=\lceil {\text{número de objetos}}/{\text{capacidad}}\rceil }, el factor de división requerido en cada dimensión para lograr esto comos=⌈l1/d⌉{\displaystyle s=\lceil l^{1/d}\rceil }, luego divide repetidamente cada dimensión sucesivamente ens{\displaystyle s}Particiones de igual tamaño mediante ordenación unidimensional. Si las páginas resultantes ocupan más de una página, se cargan de nuevo en bloque utilizando el mismo algoritmo. Para datos puntuales, los nodos hoja no se superpondrán y dividirán el espacio de datos en páginas de tamaño aproximadamente igual.
  • Minimización de superposición de arriba hacia abajo (OMT): [ 18 ] Mejora con respecto a STR mediante un enfoque de arriba hacia abajo que minimiza las superposiciones entre segmentos y mejora el rendimiento de la consulta.
  • Árbol R de prioridad

Véase también

Referencias

  1. ↑ Árbol R cs.sfu.ca
  2. 1 2 3 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. S2CID 876601 . 
  3. ↑ Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). Árboles R: Teoría y aplicaciones . Springer. ISBN 978-1-85233-977-7. Consultado el 8 de octubre de 2011 .
  4. ↑ Roussopoulos, N.; Kelley, S.; Vincent, FDR (1995). «Consultas del vecino más cercano». Actas de la conferencia internacional ACM SIGMOD de 1995 sobre gestión de datos – SIGMOD '95 . pág. 71. doi : 10.1145/223784.223794 . ISBN  0897917316.
  5. 1 2 Schubert, E.; Zimek, A.; Kriegel, HP (2013). "Consultas de distancia geodésica en árboles R para la indexación de datos geográficos". Avances en bases de datos espaciales y temporales . Notas de clase en ciencias de la computación. Vol. 8098. pág. 146. doi : 10.1007/978-3-642-40235-7_9 . ISBN   978-3-642-40234-0.
  6. ↑ Mengbai Xiao, Hao Wang, Liang Geng, Rubao Lee y Xiaodong Zhang (2022). "Una plataforma de computación en memoria habilitada para RDMA para R-tree en clústeres" . ACM Transactions on Spatial Algorithms and Systems. págs. 1–26 . doi : 10.1145/3503513 . {{cite conference}}: CS1 maint: varios nombres: lista de autores ( enlace )
  7. ↑ Hwang, S.; Kwon, K.; Cha, SK; Lee, BS (2003). "Evaluación del rendimiento de variantes de árboles R en memoria principal" . Avances en bases de datos espaciales y temporales . Notas de clase en ciencias de la computación. Vol. 2750. pp. 10. doi : 10.1007 /978-3-540-45072-6_2 . ISBN   978-3-540-40535-1.
  8. ↑ Arge, L.; De Berg, M.; Haverkort, HJ; Yi, K. (2004). "El árbol R de prioridad" (PDF) . Actas de la conferencia internacional ACM SIGMOD de 2004 sobre gestión de datos – SIGMOD '04 . pág. 347. doi : 10.1145/1007568.1007608 . ISBN  978-1581138597. S2CID 6817500 . 
  9. ↑ Brinkhoff, T.; Kriegel, HP ; Seeger, B. (1993). "Procesamiento eficiente de uniones espaciales mediante árboles R". ACM SIGMOD Record . 22 (2): 237. CiteSeerX 10.1.1.72.4514 . doi : 10.1145/170036.170075 . S2CID 7810650 .  
  10. ↑ Böhm, Christian; Krebs, Florian (1 de septiembre de 2003). «Apoyo a las aplicaciones KDD mediante la unión de k vecinos más cercanos». Aplicaciones de bases de datos y sistemas expertos . Notas 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.
  11. ↑ Achtert, Elke; Böhm, Christian; Kröger, Peer (2006). "DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking". En Ng, Wee Keong; Kitsuregawa, Masaru; Li, Jianzhong; Chang, Kuiyu (eds.). Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference, PAKDD 2006, Singapur, 9-12 de abril de 2006, Proceedings . Lecture Notes in Computer Science. Vol. 3918. Springer. pp. 119–128 . doi : 10.1007/11731139_16 .  
  12. ↑ Kuan, J.; Lewis, P. (1997). "Búsqueda rápida de k vecinos más cercanos para la familia de árboles R". Actas de ICICS, Conferencia Internacional de 1997 sobre Información, Comunicaciones y Procesamiento de Señales. Tema: Tendencias en Ingeniería de Sistemas de Información y Comunicaciones Multimedia Inalámbricas (Cat. No. 97TH8237) . pág. 924. doi : 10.1109/ICICS.1997.652114 . ISBN  0-7803-3676-3.
  13. 1 2 Greene, D. (1989). "Análisis de la implementación y el rendimiento de los métodos de acceso a datos espaciales". [1989] Actas de la 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 . 
  14. 1 2 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ág. 322. CiteSeerX 10.1.1.129.3731 . doi : 10.1145/93597.98741 . ISBN   978-0897913652. S2CID 11567855 . 
  15. 1 2 Ang, CH; Tan, TC (1997). "Nuevo algoritmo de división lineal de nodos 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. pp. 337-349 . doi : 10.1007/3-540-63238-7_38 .  
  16. ↑ 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 .
  17. ↑ Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A. (febrero de 1997). "STR: Un algoritmo simple y eficiente para el empaquetamiento de árboles R" .
  18. ↑ Lee, Taewon; Lee, Sukho (junio de 2003). "OMT: Algoritmo de carga masiva descendente que minimiza la superposición para R-tree" (PDF) .
  • Logotipo de Wikimedia CommonsContenido multimedia relacionado con R-tree en Wikimedia Commons