Diplomarbeit
Erstellung einer inkrementellen Version von OPTICS
Inhalt
Problemstellung
Eine inkrementell arbeitende Version des OPTICS-Algorithmus soll erstellt
werden.
Lösungsansatz
Resoursenintensive Operationen sollten so selten wie möglich durchgeführt
werden.
Bei der Ausführung von OPTICS fallen insbesondere die zeitaufwendigen
Rangequeries ins Gewicht, die bei jedem nötigen Reachability - Update
über die gesamte Datenmenge ausgeführt werden müssen.
Um die Anzahl dieser rechenintensiven Operationen möglichst gering
zu halten wäre eine Materealisierung der Rangequeries denkbar. Gesetzt
den Fall, daß für jeden möglichen Anfragepunkt die Ergebnismenge
der Bereichsanfrage bereits bekannt wäre, dann würde sich die
Ausführung der sonst nötigen Rangequery auf die Suche einer bereits
bekannten Ergebnismenge aus einer eventuell sehr großen Datenmenge
beschränken.
Als geeignete DAtenstruktur zur Materealisierung der Rangequeries
wird ein B-Baum eingesetzt. In den jeweiligen Endknoten des B-Baumes befinden
sich Zeiger auf die Ergebnisliste der jeweiligen Rangequery.
Da die Datenmenge zur Abspeicherung aller Ergebnismengen möglicher
Bereichsanfragen erwartungsgemäß sehr groß ausfallen wird,
sollen geeignete Verfahren zur Komprimierung dieser Daten und die daraus
resultierende, geminderte Performance, untersucht werden.
Ziel
Aussage über eine mögliche Leistungssteigerung von OPTICS durch
Abspeicherung der Bereichsabfragen.
Steigerung der Effektivität durch Komprimierung der umfangreichen
Ergebnismengen.
Performancesteigerung des OPTICS-Verfahrens.
Tools
C++, SUSE Linux 6.0
Personen
Bearbeiter |
Christian Pooch |
Betreuer |
Markus Breunig |
Arbeitsplan
Arbeitsabschnitt |
Zeitbedarf |
Erstellung geeigneter Routinen zur Abspeicherung der Rangequeryergebnisse
in einem B-Baum |
5 |
"Korrekturen, Tests und Verbesserungen |
5-10 |
Tests mit verschiedenen Verfahren zur Komprimierung, evtl. Test mit
Datenbankanbindung |
|
Berücksichtigung der Reachability - Vorgänger |
|
Homepages:
DBS
Institut
LMU
09.12.1999 Christian Pooch