Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

Der HS-Algorithmus verwendet statt einer Tiefensuche eine global sortierte Warteschlange mit Knoten, Blätter und Feature-Objekten mit minimaler Distanz lb zum Anfragepunkt:

1. Mit Wurzel initialisieren
2. Wenn entnommenes Kopfelement Knoten, dann werden Kinder eingefügt.
2. Wenn entnommenes Kopfelement Blatt, dann werden Feature-Objekte eingefügt.
2. Wenn entnommenes Kopfelement Feature-Objekt, dann fertig

Gut für getNext-Anfragen geeignet, aber viel Speicher nötig und keine Tiefen/Breitensuche und daher kein sequentieller Festplattenzugriff
Aufwand, um alle FOs auszugeben ist O(n * log(n))

Ist eine Erweiterung des B-Baums um mehrere Dimensionen. FOs können beliebige räumliche Ausdehnung haben.

Cluster-Bildung: lokal gruppierend.
Cluster-Überlappung: Können überlappen, führt zu weniger effizienter Suche
Balance: Ist balanciert durch Split-Algorithmus beim Seitenüberlauf und Seitenzusammenfassung beim Unterlauf.
Objektspeicherung: Nur in den Blättern.
Geometrie: MBR
Anzahl der Kindknoten: An Seitengröße angepasst.

Einfügen:

• Von der Wurzel ausgehend den Kindknoten suchen, dessen Volumen nur minimal erweitert werden müsste.
• Ist dies nicht eindeutig, den Kindknoten wählen, dessen Volumen das kleinste ist.
• Objekt einfügen und Vaterknoten anpassen.
• Wenn ein Knoten überläuft, MBR in zwei kleinere MBR mit minimaler Volumensumme zerlegen. Es gibt verschiedene Algorithmen, üblicherweise nimmt man den linearen.

Suche geht über BaB, HS- und RKV-Algorithmen. Bei Bereichsanfragen muss man in jeden Unterbaum navigieren, dessen MBR den Suchbereich schneidet. Ab Dimension 10 ist NN-Suche nicht mehr effizient. Ausserdem bei hohen Dimensionen stärkere Überlappung -> hoher Suchaufwand

Der R+-Baum ist ein R-Baum ohne Überlappung und erfordert daher einen neuen Einfügealgorithmus. Ein Einfügen kann die Anpassung mehrerer Blätter erfordern. Wenn kein umfassender MBR gefunden werden kann, müssen Einträge mehrfach vorkommen. Ist trotzdem effizienter als R-Baum aber in hohen Dimensionen immer noch ineffizient.

Der X-Baum ist ein hybrider Baum, der mit hohen Dimensionen umgehen können soll. Die Idee ist, dass bei starker Überlappung ein sequentieller Durchlauf schneller ist als ein Baum. Dann werden Superknoten eingefügt, die beliebig viele DB-Seiten umfassen können und sequentiell durchsucht werden.

Jeder MBR verwaltet eine Split-Historie, die alle bereits verwendeten Zerlegungsdimensionen speichert.

Beim Überlauf wird nun
1. zuerst eine herkömmliche topologische Zerlegung gemacht.
2. wird ein vordefinierter Überlappungsgrad überschritten, so wird unter Ausnutzung der Split-Historie eine Zerlegungsdimension ausgesucht.
3. wird dadurch die Balance-Bedingung verletzt (Mindestfüllgrad), wird ein Superknoten erzeugt.

Ab etwa 15 Dimensionen wird der X-Baum zu einem einzigen Superknoten.

Bei der Suche sind RKV und HS möglich. Die minimale Distanz (d(Op, Q)-d(O, Op)) gibt es in angenäherter Form als schnellen Filter. Cluster können mit der minimalen Distanz (d(o, Q) - r) und der Hilfe der Dreiecksungleichung ausgeschlossen werden.

Beim Einfügen analog zum R-Baum: Geeignetes Blatt ist das, dessen Radius nicht vergrößert werden muss (bei Gleichstand das mit dem nächstgelegenen Routing Object nehmen). Ansonsten das mit der minimalen Vergrößerung nehmen. Falls Radius verändert wurde, müssen die Radien auf dem Pfad bis zur Wurzel verändert werden.

Beim Überlauf muss ein Cluster in zwei neue Cluster mit eigenen Routing Objects zerlegt werden. Das Ziel ist, Volumen und Überlappung zu minimieren. Danach werden die FOs abwechselnd zugeordnet, um gleichgroße Cluster zu entwickeln.

Ab 20 Dimensionen versagt NN-Suche in Indexbäumen, es werden keine Teilbäume mehr ausgeschlossen, und ein sequentieller Durchlauf wäre effizienter: Der Fluch der hohen Dimensionen. Der Grund liegt in steigenden Approximationsfehlern und konstantem Abstand zwischen größter und kleinster Distanz. Das gilt auch für Metrik-Bäume wie den M-Baum.

Man kann versuchen:
Komplexe Distanzfunktionen durch einfache Distanzfunktion substituieren, solange diese Objekte korrekt ausschließt.
FastMap etwa bildet eine Metrik (Objekte und Distanzen) approximativ auf k-dimensionale Punkte und euklidische Distanzfunktionen ab.