Jaka jest różnica między drzewem KD a R-drzewem?

Przyjrzałem się definicji drzewa KD i R-drzewa. Wydaje mi się, że są prawie takie same.

Jaka jest różnica między drzewem KD a R-drzewem?

R-drzewa i k d-drzewa opierają się na podobnych pomysłach (podział przestrzeni na podstawie regionów wyrównanych do osi), ale kluczowe różnice to:

• Węzły w k d-drzew reprezentują oddzielające płaszczyzny, podczas gdy węzły w R-drzewach reprezentują granice.
• k d-drzew dzieli całą przestrzeń na regiony, podczas gdy R-drzewa dzielą tylko podzbiór przestrzeni zawierającej interesujące miejsca.
• k d-drzewa reprezentują rozłączny podział (punkty należą tylko do jednego regionu), podczas gdy regiony w R-drzewie mogą się pokrywać.

(Istnieje wiele podobnych struktur drzewiastych do podziału przestrzeni: czworonogi, drzewa BSP, drzewa R *, itp.)

W rzeczywistości są zupełnie inne. Służą podobnemu celowi (zapytania regionalne w danych przestrzennych) i oba są drzewami (i oba należą do rodziny indeksów hierarchii objętości ograniczających), ale to wszystko, co je łączy.

• R-Drzewa są zrównoważone , kd-drzewa nie (chyba że są ładowane zbiorczo). Właśnie dlatego R-drzewa są preferowane do zmiany danych, ponieważ kd-drzewa mogą wymagać przebudowy w celu ponownej optymalizacji.
• R-Drzewa są zorientowane na dysk . W rzeczywistości organizują dane w obszarach, które są bezpośrednio odwzorowywane na reprezentację na dysku. To sprawia, że ​​są bardziej przydatne w rzeczywistych bazach danych i przy operacjach związanych z brakiem pamięci. kd-drzewa są zorientowane na pamięć i nie są łatwe do umieszczenia na stronach dysku
• Drzewa kd są eleganckie, gdy są ładowane zbiorczo (pochwała dla SingleNegationElimination za wskazanie tego), podczas gdy R-drzewa są lepsze do zmiany danych (chociaż korzystają z ładowania zbiorczego, gdy są używane z danymi statycznymi).
• R-Drzewa nie obejmują całej przestrzeni danych. Puste obszary mogą zostać odkryte. drzewa kd zawsze pokrywają całą przestrzeń.
• kd-trees binarne dzielą przestrzeń danych, R-trees dzielą dane na prostokąty . Podziały binarne są oczywiście rozłączne; podczas gdy prostokąty drzewa R mogą się nakładać (co w rzeczywistości czasami jest dobre, chociaż próbuje się zminimalizować nakładanie się)
• Drzewa kd są dużo łatwiejsze do zaimplementowania w pamięci, co w rzeczywistości jest ich kluczową zaletą
• R-drzewa mogą przechowywać prostokąty i wielokąty , kd-drzewa przechowują tylko wektory punktowe (ponieważ zachodzenie jest potrzebne dla wielokątów)
• R-drzewa zawierają różne strategie optymalizacji, różne podziały, ładowanie zbiorcze, strategie wstawiania i ponownego umieszczania itp.
• drzewa kd wykorzystują jednowymiarową odległość do oddzielającej hiperpłaszczyzny jako związaną; R-drzewa używają minimalnej odległości d-wymiarowej do hiperprostokąta ograniczającego do ograniczania (mogą również używać maksymalnej odległości dla niektórych zapytań zliczających, aby filtrować prawdziwe pozytywy).
• Kd-drzewa obsługują kwadratową odległość euklidesową i normy Minkowskiego, podczas gdy Rtrees okazały się również wspierać odległość geodezyjną (do znajdowania bliskich punktów na geodanych).

Główną różnicą między dwoma niewymienionymi w tej odpowiedzi jest to, że drzewa KD są wydajne tylko w sytuacjach ładowania zbiorczego. Raz zbudowane, modyfikowanie lub równoważenie drzewa KD jest nietrywialne. R-drzewa nie cierpią z tego powodu.