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 de 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 las consultas. como "Buscar todos los museos en un radio de 2 km de mi ubicación actual", "recuperar todos los tramos de carretera en un radio de 2 km de mi ubicación" (para mostrarlos en un sistema de navegación ) o "buscar la gasolinera más cercana" (aunque sin tomar carreteras hacia cuenta). 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 círculo máximo . [5]
Árbol R | |||||||||
---|---|---|---|---|---|---|---|---|---|
Tipo | árbol | ||||||||
Inventado | 1984 | ||||||||
Inventado por | Antonin Guttman | ||||||||
Complejidad del tiempo en notación O grande | |||||||||
|
Idea de á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 el árbol R es para rectángulo. Dado que todos los objetos se encuentran dentro de este rectángulo delimitador, una consulta que no interseca el rectángulo delimitador tampoco puede intersecar ninguno de los objetos contenidos. A nivel de 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 verse como una aproximación cada vez más burda del conjunto de datos.
Al igual que el á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 el almacenamiento en disco (como se usa en las bases de datos ). Cada página puede contener un número máximo de entradas, a menudo indicadas como. También garantiza un relleno mínimo (excepto para el nodo raíz); sin embargo, se ha obtenido el mejor rendimiento con un relleno mínimo del 30% al 40% del número máximo de entradas (los árboles B garantizan un relleno de página del 50% y B * - árboles incluso 66%). La razón de esto es el equilibrio más complejo requerido para los datos espaciales en contraposición a 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 simples. La idea clave es usar los cuadros delimitadores para decidir si buscar o no 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 la memoria cuando sea necesario y el árbol completo no se puede guardar en la memoria principal. Incluso si los datos pueden caber 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. Sin embargo, para las aplicaciones en memoria, existen alternativas similares que pueden proporcionar un rendimiento ligeramente mejor o ser más sencillas de implementar en la práctica.
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), por otro lado, los rectángulos no cubren demasiado espacio vacío y no se superponen demasiado ( de modo que durante la búsqueda se necesiten procesar menos subárboles). Por ejemplo, la idea original para 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 la 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 para los árboles R tienen como objetivo 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 supresión).
Los árboles R no garantizan un buen rendimiento en el peor de los casos , pero generalmente funcionan bien con datos del mundo real. [6] Si bien es más de interés teórico, la variante del árbol R de prioridad (de carga masiva) del árbol R es óptima en el peor de los casos, [7] pero debido a la mayor complejidad, no ha recibido mucha atención en aplicaciones prácticas, por lo que lejos.
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 usando una unión espacial. [8] [9] Esto es beneficioso para muchos algoritmos basados en tales consultas, por ejemplo, el factor de valor atípico local . DeLi-Clu, [10] 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 de manera eficiente un clúster OPTICS .
Variantes
Algoritmo
Disposición de datos
Los datos de 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 relleno mínimo). Cada entrada dentro de un nodo no hoja almacena dos piezas de 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 niño, a menudo un punto o cuadro delimitador que representa al niño y un identificador externo para el niño. Para los datos de puntos, las entradas de hoja pueden ser solo los puntos en sí. Para los datos de polígono (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 de un nodo, se debe decidir si se superpone al rectángulo de búsqueda o no. En caso afirmativo, también se debe buscar el nodo hijo correspondiente. La búsqueda se realiza así de forma recursiva hasta que se hayan atravesado todos los nodos superpuestos. Cuando se alcanza 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 de prioridad, como la búsqueda del vecino más cercano , 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 el número deseado de resultados, la búsqueda continúa procesando la entrada más cercana en la cola. Los nodos de los árboles se expanden y sus hijos se reinsertan. Las entradas hoja se devuelven cuando se encuentran en la cola. [11] Este enfoque se puede utilizar con varias métricas de distancia, incluida la distancia de círculo máximo para datos geográficos. [5]
Inserción
Para insertar un objeto, el árbol se recorre de forma recursiva desde el nodo raíz. En cada paso, se examinan todos los rectángulos en el nodo de directorio actual y se elige un candidato utilizando una heurística, como elegir el rectángulo que requiere la menor ampliación. La búsqueda luego desciende a 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 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 de altura.
Elegir el subárbol de inserción
En cada nivel, el algoritmo debe decidir en qué subárbol insertar el nuevo objeto de datos. Cuando un objeto de datos está completamente contenido en un solo rectángulo, la elección es clara. Cuando hay varias opciones o rectángulos que necesitan ampliaciones, la elección puede tener un impacto significativo en el rendimiento del árbol.
En el árbol R clásico, los objetos se insertan en el subárbol que necesita la menor ampliación. En el árbol R * más avanzado , se emplea una heurística mixta. A nivel de hoja, intenta minimizar el solapamiento (en caso de empates, prefiera el menor agrandamiento y luego el menor área); en los niveles más altos, se comporta de manera similar al árbol R, pero en los lazos nuevamente prefiere el subárbol con un área más pequeña. La menor superposición de rectángulos en el árbol R * es uno de los beneficios clave sobre el árbol R tradicional (esto también es una consecuencia de las otras heurísticas utilizadas, no solo de la elección del subárbol).
Dividiendo 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, 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, llamadas QuadraticSplit y LinearSplit. En la división cuadrática, el algoritmo busca el par de rectángulos que es la peor combinación para tener en el mismo nodo y los coloca como objetos iniciales en los dos nuevos grupos. Luego busca la entrada que tiene la preferencia más fuerte por uno de los grupos (en términos de aumento de área) y asigna el objeto a este grupo hasta que todos los objetos estén asignados (satisfaciendo el llenado mínimo).
Hay otras estrategias de división como Greene's Split, [12] la heurística de división de árboles R * [13] (que nuevamente intenta minimizar la superposición, pero también prefiere las páginas cuadráticas) o el algoritmo de división lineal propuesto por Ang y Tan [14] (que, sin embargo, puede producir rectángulos muy irregulares, que son menos eficaces para muchas consultas de ventana y rango 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 al reinsertar algunos de los miembros del nodo, 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 [15] 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 encuentre una buena división (en particular para datos de alta dimensión).
División cuadrática de Guttman. [2] Las
páginas de este árbol se superponen mucho.División lineal de Guttman. [2]
Estructura aún peor, pero también más rápida de construir.Greene está dividido. [12] Las páginas se superponen mucho menos que con la estrategia de Guttman.
División lineal Ang-Tan. [14]
Esta estrategia produce páginas divididas, que a menudo producen un mal rendimiento de las consultas.División topológica del árbol R * . [13]
Las páginas se superponen mucho menos ya que el árbol R * intenta minimizar la superposición de páginas y las reinserciones optimizan aún más el árbol. La estrategia dividida prefiere páginas cuadráticas, lo que ofrece un mejor rendimiento para aplicaciones de mapas comunes.Árbol R * cargado a granel usando Sort-Tile-Recursive (STR).
Las páginas finales no se superponen en absoluto y las páginas del directorio se superponen muy poco. Este es un árbol muy eficiente, pero requiere que los datos sean completamente conocidos de antemano.Los árboles M son similares al árbol R, pero usan 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 no está completa, 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 de hoja) se reinsertarán. Si durante este proceso el nodo raíz tiene un solo elemento, la altura del árbol puede disminuir.
Carga masiva
- Más 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 de la X más cercana, pero ordenando usando 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): [16] Otra variación de Ne más cercano-X, que estima el número 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 clasificación unidimensional. Las páginas resultantes, si ocupan más de una página, se cargan de nuevo de forma masiva utilizando el mismo algoritmo. Para los datos de puntos, los nodos de hoja no se superpondrán y "en mosaico" el espacio de datos en páginas de aproximadamente el mismo tamaño.
- Superposición minimizando de arriba hacia abajo (OMT): [17] Mejora sobre STR utilizando un enfoque de arriba hacia abajo que minimiza las superposiciones entre los sectores y mejora el rendimiento de las consultas.
- Árbol R de prioridad
Ver también
- Árbol de segmentos
- Árbol de intervalo: un árbol R degenerado para una dimensión (generalmente tiempo).
- Jerarquía de volumen delimitador
- Índice espacial
- Esencia
Referencias
- ^ https://www2.cs.sfu.ca/CourseCentral/454/jpei/slides/R-Tree.pdf
- ↑ a b c Guttman, A. (1984). "R-Trees: una estructura de índice dinámica para la búsqueda espacial" (PDF) . Actas de la conferencia internacional de 1984 ACM SIGMOD sobre Gestión de datos - SIGMOD '84 . pag. 47. doi : 10.1145 / 602259.602266 . ISBN 978-0897911283. S2CID 876601 .
- ^ Y. Manolopoulos; A. Nanopoulos; Y. Theodoridis (2006). Árboles R: teoría y aplicaciones . Saltador. ISBN 978-1-85233-977-7. Consultado el 8 de octubre de 2011 .
- ^ Roussopoulos, N .; Kelley, S .; Vincent, FDR (1995). "Consultas de vecinos más cercanos". Actas de la conferencia internacional ACM SIGMOD de 1995 sobre gestión de datos - SIGMOD '95 . pag. 71. doi : 10.1145 / 223784.223794 . ISBN 0897917316.
- ^ a b 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 conferencias en Ciencias de la Computación. 8098 . pag. 146. doi : 10.1007 / 978-3-642-40235-7_9 . ISBN 978-3-642-40234-0.
- ^ 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 conferencias en Ciencias de la Computación. 2750 . pp. 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 prioridad" (PDF) . Actas de la conferencia internacional 2004 ACM SIGMOD sobre Gestión de datos - SIGMOD '04 . pag. 347. doi : 10.1145 / 1007568.1007608 . ISBN 978-1581138597. S2CID 6817500 .
- ^ Brinkhoff, T .; Kriegel, HP ; Seeger, B. (1993). "Procesamiento eficiente de uniones espaciales utilizando árboles R". Registro ACM SIGMOD . 22 (2): 237. CiteSeerX 10.1.1.72.4514 . doi : 10.1145 / 170036.170075 .
- ^ Böhm, Christian; Krebs, Florian (1 de septiembre de 2003). Compatibilidad con aplicaciones KDD mediante la combinación de vecinos más cercanos k . Aplicaciones de bases de datos y sistemas expertos . Apuntes de conferencias en Ciencias de la Computación. 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, E .; Böhm, C .; Kröger, P. (2006). DeLi-Clu: Impulsar la robustez, la integridad, la usabilidad y la eficiencia de la agrupación jerárquica por un ranking de par más cercano . LNCS: avances en el descubrimiento de conocimientos y minería de datos . Apuntes de conferencias en Ciencias de la Computación. 3918 . págs. 119-128. doi : 10.1007 / 11731139_16 . ISBN 978-3-540-33206-0.
- ^ Kuan, J .; Lewis, P. (1997). "Búsqueda rápida del vecino más cercano k para la familia del árbol R". Proceedings of ICICS, 1997 International Conference on Information, Communications and Signal Processing. Tema: Tendencias en Ingeniería de Sistemas de Información y Comunicaciones Multimedia Inalámbricas (Cat. No.97TH8237) . pag. 924. doi : 10.1109 / ICICS.1997.652114 . ISBN 0-7803-3676-3.
- ^ a b Greene, D. (1989). "Una implementación y análisis de desempeño de métodos de acceso a datos espaciales". [1989] Actas. V Congreso Internacional de Ingeniería de Datos . págs. 606–615. doi : 10.1109 / ICDE.1989.47268 . ISBN 978-0-8186-1915-1. S2CID 7957624 .
- ^ a b Beckmann, N .; Kriegel, HP ; Schneider, R .; Seeger, B. (1990). "El árbol R *: un método de acceso eficaz y robusto para puntos y rectángulos" (PDF) . Actas de la conferencia internacional ACM SIGMOD de 1990 sobre Gestión de datos - SIGMOD '90 . pag. 322. CiteSeerX 10.1.1.129.3731 . doi : 10.1145 / 93597.98741 . ISBN 978-0897913652. S2CID 11567855 .
- ^ a b Ang, CH; Tan, TC (1997). "Nuevo algoritmo de división de nodos lineales 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 al 18 de julio de 1997 . Apuntes de conferencias en Ciencias de la Computación. 1262 . Saltador. 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 . Mumbai, India: 28–39.
- ^ Leutenegger, Scott T .; Edgington, Jeffrey M .; Lopez, Mario A. (febrero de 1997). "STR: un algoritmo simple y eficiente para el embalaje R-Tree" . Cite journal requiere
|journal=
( ayuda ) - ^ Lee, Taewon; Lee, Sukho (junio de 2003). "OMT: Superposición que minimiza el algoritmo de carga masiva de arriba hacia abajo para R-tree" (PDF) . Cite journal requiere
|journal=
( ayuda )
enlaces externos
- Medios relacionados con R-tree en Wikimedia Commons