M-Tree ist dabei eine Indexstruktur, die einen metrischen Raum nach oben genannten Vorgaben indiziert.
Bearbeiter | Oliver Dragićević |
Betreuer | Stefan Schönauer |
Arbeitsabschnitt | Zeitbedarf |
Einarbeitung in die Thematik | 5 Tage |
Implementierung des Strukturgerüsts | 14 Tage |
Implementierung der Methoden | 14 Tage |
Evaluierung und Dokumentation | 7 Tage |
Die Implementierung der Indexstruktur M-Tree funktioniert einwandfrei bzgl. der Baumlogik beim
Einfügen und Splitten und bzgl. der Ähnlichkeitsanfragen.
Das Wie des Splittens wird beim M-Tree durch die split-policy gegeben.
Diese bestimmt einerseits, welche zwei Objekte des zu splittenden Knotens in den Vaterknoten wandern
(promote genannt), und andererseits, welche Objekte in den neu allokierten Knoten eingefügt werden, bzw.
im zu splittenden Knoten verbleiben (partition genannt).
Da es dafür viele, verschiedene Strategien gibt, soll an dieser Stelle angemerkt werden, daß
in dieser Implementierung für das Promoten die sogenannte mM_Rad-Strategie (bestimme aus dem zu
splittenden Knoten das Pärchen deren maximaler Radius im Vergleich zum maximalen Radius eines
anderen Pärchens minimal ist) angewendet wurde. Diese ist beim Baumaufbau vergleichsweise
teuer, was sich aber bei den Anfragen durch besseres Antwortverhalten mehr als relativiert. Für
das Partition wurde Generalized Hyperplane verwendet, d.h. für alle Objekte Oj
des zu splittenden Knotens ist zu prüfen:
wenn d(Oj,Op1) ≤ d(Oj,Op2) dann
verbleibt Oj im zu splittenden Knoten, ansonsten ordne Oj dem neuen
Knoten zu, wobei Op1 und Op2 die Väter sind.