Lehr- und Forschungseinheit für Datenbanksysteme Datenbanksysteme Database Systems

Projektarbeit

M-Tree - Eine Indexstruktur

Inhalt

"Indizierung des metrischen Raumes" heißt effizientes Antwortverhalten auf Ähnlichkeitsanfragen zur Verfügung zu stellen. Der Zweck dieser Anfragen ist es, DB-Objekte zu erhalten, die ähnlich zu einem gegebenen Anfrageobjekt sind. Dabei wird die (Un)Ähnlichkeit mit einer spez. metrischen Distanzfunktion gemessen. Diese Funktion erfüllt die Eigenschaften der Metrik, nämlich:

  • Positivheit
  • Symetrie
  • Dreiecksungleichheit

    • M-Tree ist dabei eine Indexstruktur, die einen metrischen Raum nach oben genannten Vorgaben indiziert.

    Aufgabenstellung

    Implememtierung der Indexstruktur M-Tree mit den Operationen insert und split für den Baumaufbau und pointQuery, rangeQuery und knn-Query für die Ähnlichkeitsanfragen.

    Tools

    Java

    Personen

    Bearbeiter Oliver Dragićević
    Betreuer Stefan Schönauer

    Arbeitsplan

    Arbeitsabschnitt Zeitbedarf
    Einarbeitung in die Thematik 5 Tage
    Implementierung des Strukturgerüsts 14 Tage
    Implementierung der Methoden 14 Tage
    Evaluierung und Dokumentation 7 Tage

    Ergebnis

    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.

    Homepages:  homeDBS homeInstitut homeLMU
    12.2.2003 Stefan Schönauer