Projektbeschreibung:

In der Forschungsgruppe NEXUS wird eine offene Plattform für Location Based Services entwickelt. Durch die Offenheit können beliebige Datenanbieter ihre Daten durch die Plattform bereitstellen. Eine Föderations-Middleware soll die Verteilung der Daten vor einer Anwendung verbergen und die Daten verschiedener Anbieter in geeigneter Weise kombinieren.

Zur Beschleunigung des Zugriffs auf die Daten werden an verschiedenen Stellen der Plattform bereits Indexstrukturen eingesetzt: im räumlichen Verzeichnisdienst, bei der Verwaltung von Ergebnismengen oder bei der Verwaltung des Cache-Inhalts. Bisher sind diese Indexe jedoch immer nur auf ein Attribut eines Objekts bezogen. Typischerweise filtern Anfragen sowohl nach dem Ort eines Objekts als auch nach dessen Typ, so dass in dieser Arbeit untersucht werden soll, wie ein kombinierter Index aus Position und Typ eines Objekts erstellt werden kann, und wie groß die Effizienzsteigerungen dadurch sind.

Aufgabenstellung:

Ausgehend von bekannten Indexstrukturen für 1-D Daten (Binärbaum, B*-Baum, ...) und 2-D Daten (R*-Baum, Quad-Tree, ...) soll als Basis für weitere Vergleiche ein kombinierter Index entwickelt werden, der entweder einen bekannten 1-D bzw. 2-D Index verwendet, um Kandidaten zu ermitteln, welche anschließend von Hand in den noch fehlenden Dimensionen gefiltert werden. Alternativ können auch Kandidaten aus getrennten 1-D und 2-D Indexen ermittelt werden. Die Schnittmenge der Kandidaten stellt dann das Endergebnis dar. Die Typen der Objekte sind hierbei in einer baum-artigen Hierarchie ohne Mehrfachvererbung angeordnet. Die Typen werden entweder in den |R1 abgebildet, oder es wird ein speziell auf diskrete hierarchische Wertebereiche zugeschnittener Index eingesetzt. Anschließend soll ein kombinierter Index entwickelt werden, bei dem Position und Typ als Vektor bzw. ausgedehntes Objekt im 3-D Raum repräsentiert sind. Dieser kombinierte Index soll mit den zuvor entwickelten Basis-Varianten sowohl bezüglich der Anfragezeiten als auch der Aktualisierungszeiten verglichen werden.

In einer zweiten Phase soll die Typ-Hierarchie um Mehrfachvererbung erweitert und die kombinierte Indexstruktur entsprechend angepasst werden. Es sollen verschiedene Alternativen für diese Anpassung erarbeitet und analysiert werden. Im Ausblick kann aufgezeigt werden, wie auch eine Level-of-Detail-Dimension oder eine Zeit-Dimension in einen kombinierten Index integriert werden können.