Was zeichnet den M-Baum aus?
Andere Bäume gehen davon aus, dass die FOs Elemente des euklidischen Raums sind. Nicht so der M-Baum. Die Distanzfunktion muss auch nur die Dreiecksungleichung erfüllen.
Cluster-Bildung: lokal gruppierend
Cluster-Überlappung: Erlaubt, wie beim R-Baum.
Balance: Balanciert wie R-Baum.
Objektspeicherung: Nur in Blättern.
Geometrie: Kugeln, also Punkte samt Radius.
Jeder innere Knoten hat folgende Struktur:
Blätter haben stattdessen ein FO, einen Zeiger auf das Medienobjekt und die Distanz vom FO zum o des Vater-Knotens.
Cluster-Bildung: lokal gruppierend
Cluster-Überlappung: Erlaubt, wie beim R-Baum.
Balance: Balanciert wie R-Baum.
Objektspeicherung: Nur in Blättern.
Geometrie: Kugeln, also Punkte samt Radius.
Jeder innere Knoten hat folgende Struktur:
- Zeiger zum Kindknoten
- Routing object o: FO, das Kugelzentrum ist
- Radius r. Maximal erlaubter Radius von o zu allen FOs im Teilbaum
- Distanz von o zum Routing Object des Vaterknotens.
Blätter haben stattdessen ein FO, einen Zeiger auf das Medienobjekt und die Distanz vom FO zum o des Vater-Knotens.
Tags: baum, m-baum, mehrdimensional
Quelle: MMDB 2009 Kapitel 7
Quelle: MMDB 2009 Kapitel 7
Wie arbeitet man mit dem M-Baum?
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.
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.
Tags: baum, m-baum, mehrdimensional
Quelle: MMDB 2009 Kapitel 7
Quelle: MMDB 2009 Kapitel 7
Kartensatzinfo:
Autor: kread
Oberthema: Informatik
Thema: Semantic Web
Schule / Uni: Universität Koblenz-Landau
Ort: Koblenz
Veröffentlicht: 22.10.2010
Schlagwörter Karten:
Alle Karten (35)
baum (9)
eigenschaften (1)
hs (1)
indexstruktur (1)
m-baum (2)
mehrdimensional (10)
modelle (1)
objektrelational (1)
oodbms (1)
probleme (1)
r-baum (3)
x-baum (2)
