Diskussion:R-Baum

R Baum und hochdimensionale Daten

Leider eignet sich der R Baum nicht für hochdimensionale Daten. Es ist ungefähr möglich bis Dimension 12. Danach kommt der Fluch der hohen Dimensionen und es müssen andere Indexstrukturen her. (Curse of Dimensionality)

Der R/R*-Baum eignet sich sogar nur bis zu 5 Dimensionen, die Passage im Artikel sollte man mal ueberarbeiten. Siehe dazu auch Berchtold S., Keim D., Kriegel H.-P.: The X-tree: An Index Structure for High-Dimensional Data.

Dann überarbeite es doch. Dies hier ist ein Wiki. -- sparti 14:14, 3. Feb. 2009 (CET)

Das ist sehr stark datenabhängig. Ich kann dir Datensätze konstruieren wo ein R-Baum auch auf 100 Dimensionen wunderbar arbeitet. Und wenn man keine Bulk-Loads und Optimierungsstrategien verwendet kann ich einem R-Baum schon in 3, 4 Dimensionen große Probleme bereiten. Auch der "Curse of Dimensionality" ist nicht so pauschal existent wie es gerne dargestellt wird. Das kommt ganz stark auf die Anwendung drauf an. Einfaches Beispiel: nimm einen 2-dimensionalen Datensatz, und setze x_(n+2)=x_n bis du 100 Dimensionen hast. Sind sind zwar faktisch 100 dimensional, intrinsisch aber maximal 2 Dimensional. --Chire 16:49, 20. Mär. 2010 (CET)

R* vs R+ Baum

Ist der hier beschriebene R*-Baum nicht eigentlich der R+-Baum? Der R*-Baum ist lediglich ein R-Baum mit einem verbesserten Split-Algorithmus, der so die Überlappungen verringert (jedoch nicht soweit ich glaube nicht komplett vermeidet). Treffe ich da auf Zustimmung und sollte der Beitrag daher dementsprechend geändert werden?
Siehe z.B. Härder, Rahm: Datenbanksysteme 2.Auflage S.284
--Mswiege 04:15, 14. Mär 2006 (CET)

Ja, das ist korrekt. Mich stoert das auch schon seit einiger Zeit. Das Thema ist aber leider zu komplex, als dass man es mal so in fuenf Minuten neuschreiben kann. Wenn ich mal mehr Zeit habe, dann wird er ueberarbeitet. -- sparti 15:01, 16. Mär 2006 (CET)

Besser jetzt? Langfristig könnten wir den Artikel auch teilen, wie es in der englischen Wikipedia ist. en:R* tree, en:R+ tree --Chire 16:51, 20. Mär. 2010 (CET)

R* Baum

Ich kenne den hier beschrieben Baum eigentlich nur als R+ Baum, aber selbst bei B, B* und B+ Bäumen ist sich die Literatur ja nicht direkt einig.

Ein echtes Problem habe ich aber mit der Aussage: "Entscheidend ist jedoch die größere Robustheit gegen Entarten der Baum-Struktur." Vermutlich ist eine größere Robustheit als bei dem R Baum gemeint. Die Aussage an sich ist aber meiner Meinung nach völlig überflüssig, da sowohl der R als auch der R* Baum auf dem B-Baum basieren und dessen Eigenschaften "geerbt" haben. Darunter fällt auch das es sich um voll balancierte Bäume handelt, bei denen sich die Anzahl der Knoten im rechten und linken Unterbaum um maximal 1 unterscheiden darf. Genau das verhindert jegliche Entartung.

Mit anderen Worten: Weder R noch R* können entarten. --Chaosdeckel 17:39, 28. Feb 2006 (CET)

Ist aber beides falsch. Leider ist der mehrdimensionale Fall im Gegensatz zum eindimensionalen erheblich komplexer. Die Rechteckverteilung kann recht unvorhersehbar wuchern; Margin und Overlap können sehr ungünstig werden. Das heisst, dass der Aufwandt zur Berechnung der Splits sehr hoch werden kann. Und insbesondere ist die Position eines Punktes im Baum nicht mehr eindeutig! Auf gut deutsch im Worst Case muessen alle Rechtecke durchsucht werden. Die Berechnung optimaler Rechtecke hingegen ist nicht mit vertretbarem Aufwandt möglich. Fuer Details einfach das Papier von Beckmann, Kriegel, Schneider und Seeger lesen. Gruss -- sparti 00:20, 1. Mär 2006 (CET)

Ich sehe gerade keinen Zusammenhang zwischen den beiden Beiträgen. Welchen Baum meinst Du überhaupt? Im R-Baum kann jedem Punkt genau ein Blatt zugordnet werden, nur im R*/+ Baum ist dies nicht gesichert. Aber wo ist der Zusammenhang zur Entartung? Gruß --Chaosdeckel 18:37, 1. Mär 2006 (CET)

Da ein R*-Baum ein R-Baum mit optimierter Splitting Strategie ist, trifft alles oben gesagte also auch auf den R*-Baum zu. Und natuerlich liegt ein Punkt bei einem R-Baum in genau in einem Blatt. Leider aber eben nicht in genau einem Umgebenden Rechteck. Das heisst der Suchpfad im Baum ist nicht eindeutig. Entarten tut der Baum also, wenn sich alle Rechtecke so ueberlappen, dass alle durchsucht werden muessen. Wie gesagt, das Paper erlaeutert das sehr ausfuehrlich. -- sparti 20:34, 1. Mär 2006 (CET)

Ihr habt beide irgendwo Recht: Der R-Baum kann zwar entarten, allerdings nur bezüglich des Suchaufwands (aufgrund von Überlappungen der Rechtecke), nicht die Baumstruktur als solche. Daher bin ich auch der Meinung, dass dies besser erläutert werden sollte, und der Satz "Entscheidend ist jedoch die größere Robustheit gegen Entarten der Baum-Struktur." falsch verstanden werden könnte - und daher geändert werden sollte. --Tafkadasoh 18:00, 30. Mär 2008 (CET)

Nur zu :) -- sparti 00:40, 31. Mär. 2008 (CEST)

Ich habe mal den Begriff "geometrisch entarten" gewählt. Der R-Baum bleibt natürlich balanciert, aber die unnötige Überlappung von Seiten (und die damit ansteigenden Suchkosten) kann man denke ich auch als eine Art "Entartung" bezeichnen. Oder hat jemand einen besseren Begriff? --Chire 16:53, 20. Mär. 2010 (CET)

Polygone

In der vorherigen Version war manches im Text auf die Speicherung von Polygonen geschrieben. Das ist natürlich eine Beispielanwendung, und nicht irrelevant (z.B. Geodaten). Jedoch ist ein R-Baum nicht pauschal zur Indizierung von Polygonen geeignet. Was er letztlich indiziert sind eben nur die MBRs. Ein R-Baum ist beispielsweise nicht geeignet, um "ähnliche Polygone" (!) zu suchen. Normalisiert man nämlich die Polygone vor der Indizierung -- und das ist für die Ähnlichkeitssuche durchaus sinnvoll -- dann werden ihre MBRs nicht besonders hilfreich. Ich habe den Text so angepasst dass die Polygone etwas später vorkommen, und versucht herauszuarbeiten dass der Index nur Kandidaten liefert, die anschließend dann verfeinert werden müssen. Vielleicht wäre es aber auch sinnvoll, einen eigenen Abschnitt "Speicherung von Polygonen in einem R-Baum" daraus zu machen. Da könnte man die hier angesprochene Problematik auch mit aufnehmen. --Chire 10:59, 21. Mär. 2010 (CET)

Plagiat?

Die Änderung https://de.wikipedia.org/w/index.php?title=R-Baum&diff=221375369&oldid=217380284 zeigt typische Merkmale einer Textübernahme. (nicht signierter Beitrag von 93.135.180.12 (Diskussion) 07:21, 22. Mär. 2022 (CET))