Der Lehrstuhl Personen Anschrift und Anfahrt Raum- und Gebäudeplan Interna Lehre Lehrveranstaltungen Skripten Abschlussarbeiten, SEPs Doktorandenausbildung Forschung Schwerpunkte DFG/BMBF-Projekte Publikationen Konferenzen Dienste LEABib Schein-Tool Freie Stellen

Heuristische Optimierung von kd-Trees

Hintergrund

kd-Trees ermöglichen effiziente Bereichssuchen in mehrdimensionalen Datensätzen. In unserem Beispiel handelt es sich hierbei um ganzzahlige Vektoren relativ kleiner Dimension (ca. 10 Komponenten). Dabei sind Einfüge-, Löschoperationen und Suchanfragen bunt durcheinandergemischt.

Projekt

Für diese Projekt werden ca. 10 große Datensätze vorgegeben. Für diese soll die Effizienz von kd-Trees und einer alternativen vorgegebenen Datenstruktur mit heuristischen Methoden optimiert werden. Parameter dafür sind z.B. die Ordnung der Variablen.

Voraussetzungen

• Kentnisse in C++
• Grundlagen: Algorithmen und Datenstrukturen (GAD) und/oder
• Effiziente Algorithmen und Datenstrukturen I (EADS)

Referenzen

Diese Referenzen sind nur geeignet, sich schnell eine Vorstellung von dem Projekt zu machen. Für die Einarbeitung wird detailliertere Literatur empfohlen werden.

• http://en.wikipedia.org/wiki/Kd-tree

Kontakt

Bei Interesse wenden Sie sich bitte an Stephan Ritscher.