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

Miré a la definición de KD-tree y el R-tree. A mí me parece que son casi la misma.

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

InformationsquelleAutor zjffdu | 2010-12-01

3 Kommentare

  1. 55

    R-árboles y kd-árboles se basan en ideas similares (espacio de particionamiento basado en la alineado al eje de las regiones), pero las diferencias clave son:

    • Nodos en kd-árboles representan la separación de los planos, mientras que los nodos de R-árboles representan las cajas de contorno.
    • kd-árboles de la partición de todo el espacio en regiones, mientras que la R-árboles sólo el subconjunto de la partición del espacio que contiene los puntos de interés.
    • kd-árboles representan un discontinuo de la partición (puntos pertenecen a una sola región), mientras que las regiones en un R-tree se pueden solapar.

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

  2. 97

    Que en realidad son muy diferentes. Sirven propósito similar (región de consultas sobre datos espaciales), y ambos son árboles, sino que es todo lo que tienen en común.

    • R-los Árboles son equilibrada, kd-trees no (a menos masiva cargado). Esta es la razón por la R-los árboles son los preferidos para la modificación de datos, como kd-trees puede ser necesario reconstruir para volver a optimizar.
    • R-los Árboles son disco orientado a. En realidad a organizar los datos en las áreas que se asignen directamente a la disco en la representación. Esto hace que sean más útiles en el real de las bases de datos y de operación de la memoria. kd-trees son de memoria orientada y no son triviales para poner en el disco de páginas
    • R-los Árboles no cubren todo el espacio de datos. Las áreas vacías puede ser descubierto. kd-trees siempre cubren todo el espacio.
    • kd-trees binario split en el espacio de datos, árboles r partición de los datos en rectángulos. El binario se divide obviamente son distintos; mientras que los rectángulos de un r-tree puede superponerse (que en realidad es a veces buena, a pesar de que uno 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
    • Árboles R puede almacenar rectángulos y polígonos, kd-trees solo almacena punto de los vectores (como la superposición es necesario para polígonos)
    • R-árboles vienen con diferentes estrategias de optimización, las diferentes divisiones, a granel-cargadoras, la inserción y la reinserción de las estrategias etc.
    • Kd-trees de apoyo a distancia Euclídea al cuadrado y Minkowski normas, mientras que Rtrees han demostrado también el apoyo geodésico distancia (para encontrar cerca de puntos de geodatos).
  3. 36

    Una diferencia importante entre los dos no se menciona en esta respuesta es que los KD-trees solo son eficientes en la masiva situaciones de carga. Una vez construido, modificar o reequilibrio un KD-tree no es trivial. R-los árboles no sufren de esto.

Kommentieren Sie den Artikel

Bitte geben Sie Ihren Kommentar ein!
Bitte geben Sie hier Ihren Namen ein

Pruebas en línea