Qual è la differenza tra un KD-albero e una R-tree?

Question

ho guardato la definizione di KD-albero e R-tree. Mi sembra che sono quasi la stessa cosa.

Qual è la differenza tra un KD-albero e un R-albero?

Answer 1

R-alberi e k D-trees si basano su idee simili (spazio partizionamento basata su regioni assi allineati), ma le differenze principali sono:

• nodi k d-alberi rappresentano piani di separazione, mentre i nodi R-alberi rappresentano riquadri di delimitazione.
• k d-alberi partizionare l'intero spazio in regioni che R-alberi partizionare solo il sottoinsieme dello spazio che comprende i punti di interesse.
• k d-alberi rappresentano una partizione disgiunto (punti appartengono ad una sola regione), mentre le regioni in un albero R possono sovrapporsi.

(Ci sono un sacco di tipi simili di strutture ad albero per la ripartizione dello spazio:. Quadtree, BSP-alberi, R * -Alberi, etc. etc)

Answer 2

sono in realtà molto diversi. Servono scopi simili (query regione su dati spaziali), ed entrambi sono alberi, ma che è tutto quello che hanno in comune.

• R-alberi sono bilanciati , KD-alberi non sono (a meno che bulk-caricato). Questo è il motivo R-alberi sono preferiti per i dati che cambiano, come kd-alberi possono avere bisogno di essere ricostruito a ri-optimize.
• R-alberi sono disco-oriented . In realtà organizzano i dati in aree che mappano direttamente alla rappresentazione su disco. Questo li rende più utile in basi di dati reali e per il funzionamento out-of-memoria. kd-alberi sono di memoria orientato e sono non banale di mettere in pagine del disco
• R-alberi non coprono l'intero spazio dei dati. aree vuote possono essere scoperti. kd-alberi coprono sempre tutto lo spazio.
• kd-alberi Split binario lo spazio dei dati, R-alberi partizionare i dati in rettangoli . Le suddivisioni binarie sono ovviamente disgiunti; mentre i rettangoli di un R-albero possono sovrapporsi (che in realtà è a volte buona, anche se si cerca di ridurre al minimo la sovrapposizione)
• KD-alberi sono molto più facili da implementare in memoria, che in realtà è il loro vantaggio chiave
• R-alberi possono memorizzare rettangoli e poligoni , kd-alberi solo memorizza il punto vettori (come è necessario per sovrapposizione poligoni)
• R-alberi sono dotati di varie strategie di ottimizzazione, diverse scissioni, bulk-caricatori, di inserimento e le strategie di reinserimento, ecc.
• KD-alberi supportano norme quadrato della distanza euclidea e Minkowski, mentre Rtrees hanno dimostrato di sostenere anche la distanza geodetica (per la ricerca vicino a punti su dati geografici).

Answer 3

Una delle principali differenze tra i due non menzionato in questa risposta è che KD-alberi sono efficaci solo in massa-loading situazioni. Una volta costruito, modificando o riequilibrare una KD-albero non è banale. R-alberi non soffrono di questo.