Was ist der Unterschied zwischen einem KD-Baum und einem R-Baum?

Question

schaute ich auf der Definition von KD-Baum und R-Baum. Es scheint mir, dass sie fast die gleichen sind.

Was ist der Unterschied zwischen einem KD-Baum und einem R-Baum?

Answer 1

R-Bäume und k d-Bäume auf ähnliche Ideen basieren (Raum auf der Achse ausgerichteten Regionen basierend Partitioning), aber die wichtigsten Unterschiede sind:

• Knoten in k D-Bäume repräsentieren Trennebene, während der Knoten in R-Bäumen Bounding Boxen darstellen.
• k d-Bäume den ganzen Raum in Regionen aufzuteilen, während R-Bäume nur die Teilmenge von Platz partitionieren, die Punkte von Interesse enthält.
• k D-Bäume eine disjunkte Partition darstellen (Punkte gehören nur eine Region), während die Bereiche in einem R-Baum überlappen können.

(Es gibt viele ähnliche Arten von Baumstrukturen zum Partitionieren Raum. Quadtrees, BSP-Bäume, R * -Bäume, usw. usw.)

Answer 2

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

• R-Bäume sind ausgewogen , kd-Bäume sind nicht (es sei denn, bulk-geladen). Aus diesem Grunde ist R-Bäume zum Ändern Daten bevorzugt werden, als kd-Bäume müssen möglicherweise re-optimize wieder aufgebaut werden.
• R-Bäume sind scheiben orientiert . Sie organisieren die Daten tatsächlich in Bereichen, die für die On-Disk-Darstellung direkt abzubilden. Das macht sie nützlich in realen Datenbanken und für Out-of-Memory-Betrieb. kd-Bäume sind Speicher orientiert und sind nicht trivial in den Disk-Seiten setzen
• R-Bäume decken nicht den gesamten Datenraum. Leere Bereiche können aufgedeckt werden. kd-Bäume immer den ganzen Raum abdecken.
• kd-Bäume binäres Split der Datenraum, partitionieren r-Bäume, die Daten in Rechtecken . Die binären Splits sind offensichtlich disjunkt; während die Rechtecke eines r-Baum überlappen können (was tatsächlich manchmal gut ist, obwohl man versucht zu minimieren Überlappung)
• kd-Bäume sind viel leichter im Gedächtnis zu implementieren, die eigentlich ihr entscheidender Vorteil ist
• R-Bäume können speichern Rechtecke und Polygone , kd-Bäume nur speichert Vektoren zeigen (als Überlappung für Polygone erforderlich)
• R-Bäume kommen mit verschiedenen Optimierungsstrategien, verschiedenen Splits, Bulk-Lader, Einfügen und Wiedereingliederungsstrategien etc.
• Kd-Bäume unterstützen squared euklidische Distanz und Minkowski-Normen, während Rtrees hat auch geodätische Entfernung zu unterstützen (für die Suche in der Nähe von Punkten auf Geodaten) gezeigt.

Answer 3

Ein wesentlicher Unterschied zwischen den beiden nicht in diese Antwort ist, dass KD-Bäume nur effizient sind in bulk-Laden Situationen. Einmal aufgebaut, Modifizieren oder einen kd-Baum Neugewichtung ist nicht-trivial. R-Bäume leiden nicht an diesem.