¿Podría alguien decirme cuál es la diferencia entre KD-tree y R-tree

Question

Miro la definición de KD-tree y R-tree, parece que son casi lo mismo.

¿Alguien podría decirme cuál es la diferencia entre KD-tree y R-tree? Gracias

Answer 1

R-trees y kd-trees se basa en ideas similares (particionamiento espacio basa en regiones de eje alineados), pero las diferencias clave son:

• nodos en k d-árboles representan planos de separación, mientras que los nodos en árboles R representan cuadros delimitadores.
• k d-trees dividen la totalidad del espacio en regiones, mientras que los R-trees solo dividen el subconjunto de espacio que contiene los puntos de interés.
• k d-trees representan una partición disjunta (los puntos pertenecen a una sola región) mientras que las regiones en un árbol R pueden solaparse.

(Hay un montón de tipos similares de estructuras de árbol para el espacio de partición: quadtrees, BSP-árboles, R * -Los árboles, etc. etc.)

Answer 2

Una importante diferencia entre los dos no mencionado por Gareth Rees dice que los árboles de Kd solo son eficientes en situaciones de carga masiva. una vez construido, modificar o reequilibrar un árbol de KD no es trivial. Los árboles R no sufren de esto.

Answer 3

En realidad son bastante diferentes. Sirven para un propósito similar (consultas de región sobre datos espaciales), y ambos son árboles, pero eso es todo lo que tienen en común.

• R árboles son equilibradas, kd-árboles no son (a menos granel cargado). Esta es la razón por la que los árboles-R son preferidos para cambiar los datos, ya que los árboles-kD pueden necesitar ser reconstruidos para volver a optimizar.
• R-Trees son orientado a disco. De hecho, organizan los datos en áreas que se asignan directamente a la representación en disco. Esto los hace más útiles en bases de datos reales y para el funcionamiento sin memoria. Los kd-trees son orientados a memoria y no son triviales para poner en las páginas de disco
• Los R-Trees no cubren todo el espacio de datos. Las áreas vacías pueden estar descubiertas. los kd siempre cubren todo el espacio.
• kd-trees división binaria el espacio de datos, r-trees divide los datos en rectángulos. Las divisiones binarias son obviamente disjuntas; mientras que los rectángulos de un r-tree pueden superponerse (lo que a veces es bueno, aunque se intenta minimizar la superposición)
• kd-trees son mucho más fáciles de implementar en la memoria, que en realidad es su beneficio clave
• R- árboles pueden almacenar rectángulos y polígonos, KD-solo los árboles de tiendas apuntan vectores (como se necesita en paralelo de los polígonos)
• R-árboles vienen con varias estrategias de optimización, diferentes escisiones, a granel cargadoras, inserción y estrategias de reinserción etc.