- Masterarbeit -

Beschreibung:
Patricia Tries sind (üblicherweise hauptspeicherbasierte) Suchbäume zur platzsparenden Speicherung von Zeichenketten (Strings), da gemeinsame Präfixe nur einmal abgelegt werden. Patricia steht dabei für practical algorithm to retrieve information coded in alphanumeric und Trie kommt von reTRIEval, dem Anwendungsgebiet von Patricia Tries, mit gleichzeitiger Anlehnung an tree. Zeichenketten mit großen gemeinsamen Präfixen findet man häufig in realen Datensätzen wie zum Beispiel Listen von URLs oder Semantic Web Daten.

Eine Variante des externen Merge Sorts für Daten, die nicht mehr in den Hauptspeicher passen, verwendet Patricia Tries, um Runs als sortierte Teilsequenzen der Eingaben zu erzeugen und anschliessend zu mischen (merge). Eine Idee ist nun, nicht die Runs als aus dem Patricia Trie materialisierte Zeichenketten zu mischen, sondern gleich die Knoten des Patricia Tries. Dadurch wird u.a. vermieden, dass gemeinsame Präfixe häufig (pro zu mischendem Zeichenkettenpaar) miteinander verglichen werden. Ausserdem wird auf diese Art ein festplattenbasierter Patricia Trie entwickelt, der als Indexstruktur mit Zeichenketten als Schlüssel verwendet werden kann (für zum Beispiel Wörterbücher, die Zeichenketten eindeutigen ganzzahligen IDs zuordnen).

Je nach Art der Arbeit (Bachelor- oder Masterarbeit) und Interesse des Studierenden kann nach Absprache die Arbeit noch um folgende Punkte erweitert werden:
- Theoretische Überlegungen zur Komplexität dieses Sortierverfahrens (im Bezug auf die Betrachtung von Zeichenketten mit gemeinsamen Präfixen) im Vergleich zu den traditionellen Sortierverfahren.
- Implementation auf einem FPGA mit verschiedenen Speicherhierarchien. Diese Hierarchien unterscheiden sich in Geschwindigkeit und Kapazität, so dass das Mischen von Patricia Tries aus den kleinen, schnellen in die langsameren, großen Speicherstrukturen erfolgen kann.
- Einsatz in Indexkonstruktion von Semantic Web Datenbanken.

Auf jeden Fall soll eine Performanzanalyse mit realen Daten erfolgen.

Anforderungen/Kenntnisse:
Java

Bearbeitung:
Florian Kalis

Ergebnis:
Die Ausarbeitung kann im Institut für Informationssysteme angefordert werden.

Betreuung:
Dipl.-Inf. Stefan Werner und
Privatdozent Dr. rer.nat. habil. Sven Groppe
Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 500 5706