Kann mir jemand sagen, was ist der Unterschied zwischen KD-Baum und R-Baum

Question

Ich schaue auf die Definition von KD-Baum und R-Baum, es scheint, dass sie fast gleich sind.

Kann mir jemand sagen, was ist der Unterschied zwischen KD-Baum und R-Baum? Dank

Answer 1

R-trees und kd-trees basieren auf ähnlichen Ideen (Raumaufteilung basierend auf der Achse ausgerichteten Regionen), aber die Hauptunterschiede sind:

• Nodes in k d Bäume darstellen Trennebenen, während Knoten in R-Bäumen repräsentieren Begrenzungsboxen.
• k d-Bäume teilen den gesamten Raum in Regionen ein, während R-Bäume nur die Teilmenge von Raum partitionieren, die die Punkte von Interesse enthält.
• k d-Bäume stellen eine disjunkte Partition dar (Punkte gehören nur zu einer Region), während sich die Regionen in einem R-Baum überlappen können.

(Es gibt viele ähnliche Arten von Baumstrukturen für die Partitionierung Raum: Quadtrees, BSP-Bäume, R * -Bäume, etc. etc.)

Answer 2

Ein wesentlicher Unterschied zwischen den beiden nicht von Gareth erwähnt Rees ist, dass Kd-Bäume nur in Massenladungssituationen effizient sind. einmal gebaut, Modifizieren oder Rebalancing eines Kd-Baumes ist nicht trivial. R Bäume leiden nicht darunter.

Answer 3

Sie sind eigentlich ganz anders. Sie dienen einem ähnlichen Zweck (Gebietsabfragen zu räumlichen Daten), und sie sind beide Bäume, aber das ist alles, was sie gemeinsam haben.

• R-Bäume sind ausgeglichene, kd-Bäume nicht (es sei denn, bulk belastetes). Aus diesem Grund werden R-Bäume bevorzugt, um Daten zu ändern, da kd-Bäume möglicherweise neu aufgebaut werden müssen, um sie zu optimieren.
• R-Bäume sind disk-orientierte. Sie organisieren die Daten tatsächlich in Bereichen, die direkt der Darstellung auf der Festplatte entsprechen. Dies macht sie in realen Datenbanken und bei nicht ausreichendem Arbeitsspeicher sinnvoller. kd-Bäume sind speicherorientiert und sind nicht-trivial, in Plattenseiten zu setzen
• R-Bäume decken nicht den ganzen Datenraum ab. Leere Bereiche können aufgedeckt werden. kd-Bäume bedecken immer den ganzen Raum.
• kd-Bäume binäre Teilung der Datenraum, R-Bäume Partition die Daten in Rechtecke. Die binären Splits sind offensichtlich disjunkt; während die Rechtecken eines r-Baum überlappen können (was tatsächlich manchmal gut ist, obwohl eine Überlappung zu minimieren versucht)
• kd-Bäume sind viel leichter im Gedächtnis zu implementieren, die eigentlich ihr entscheidender Vorteil
• R- Bäume können Rechtecke und Polygone, kd-Bäume speichern nur speichert Vektoren zeigen
• R-Bäume sind mit verschiedenen Optimierungsstrategien, unterschiedliche Teilungen, bulk Ladern, Insertion und Reinsertion Strategien usw. (als Überlappung für Polygone erforderlich)