¿Cuál es la diferencia entre una KD-árbol y un árbol R?

Question

Me miró a la definición de la EK-árbol y árbol R. Me parece que son casi los mismos.

¿Cuál es la diferencia entre una KD-árbol y un árbol R?

Answer 1

R árboles y k D-árboles se basan en ideas similares (espacio de partición basada en regiones ejes alineados), pero las diferencias principales son:

• Nodos en k D-árboles representan planos de separación, mientras que los nodos de R-árboles representan cuadros delimitadores.
• k D-árboles partición de la totalidad del espacio en regiones mientras que R-árboles particionar solamente el subconjunto del espacio que contiene los puntos de interés.
• k D-árboles represento una partición disjuntos (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 particionar el espacio:. Quadtrees, BSP-árboles, * -Los árboles R, etc., etc.)

Answer 2

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

• R-árboles son balanceadas , kd-árboles no están (a menos granel cargado). Es por esto que se prefieren R-árboles para los datos cambiantes, como pueden necesitar ser reconstruido para optimizar la re-KD-árboles.
• R-árboles son orientada disco . Que en realidad se organizan los datos en las áreas que se asignan directamente a la representación en el disco. Esto hace que sean más útiles en bases de datos reales y para la operación fuera de la memoria. KD-árboles son memoria orientada y no son triviales para poner en páginas de disco
• R-árboles no cubren todo el espacio de datos. Las áreas vacías pueden ser descubiertos. KD-árboles siempre cubren todo el espacio.
• KD-árboles división binaria el espacio de datos, r-árboles dividir los datos en rectángulos . Las divisiones binarias son obviamente disjuntos; mientras que los rectángulos de un árbol R pueden solaparse (que en realidad es a veces bien, a pesar de que uno trata de minimizar la superposición)
• KD-árboles 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 señalan vectores (como se necesita en paralelo de los polígonos)
• R-árboles vienen con varias estrategias de optimización, diferentes divisiones, a granel-cargadores, inserción y estrategias de reinserción, etc.
• KD-árboles soportan las normas distancia euclídea al cuadrado y Minkowski, mientras Rtrees se ha demostrado que también apoyan la distancia geodésica (para encontrar cerca de los puntos de datos geográficos).

Answer 3

Una diferencia importante entre los dos no se menciona en esta respuesta es que KD-árboles sólo son eficientes en la carga masiva situaciones. Una vez construida, la modificación o el reequilibrio de una KD-árbol no es trivial. R-árboles no sufren de esto.