Motivation:

Zur Konstruktion von Kohlenstoffnanoröhren wurde ein neuartiges, Graph Algebra basiertes Verfahren entwickelt. Aus diesem resultieren Graphen, deren Knoten nicht wie in traditionellen Ansätzen mittels Ganzzahlwerten oder Zeichenketten identifiziert sind, sondern mittels n-dimensionalen Tupel (xn, xn-1, …, x1, x0). Dieses System erlaubt pro Knoten eine Kodierung wichtiger Informationen wie Verlauf des Konstruktionsprozesses, Symmetrieeigenschaften und Geometrie. Somit liegt es nahe dieses Tupel-System auch als Basis des Speicherformates zu benutzen. Die während und nach der Konstruktion vorkommenden Tupel sind nicht vollständig besetzt, das heißt, es sind nicht alle denkbaren Kombinationen vorhanden.

Beschreibung der Arbeit:

Im Rahmen dieser Arbeit soll eine neue Speicherstruktur für Tupel-basierte Graphen konzipiert und implementiert werden. Für viele Speicherstrukturen wie Baum-basierte Ansätze oder Hash-Tabellen existieren verschiedene Varianten, die für verschiedene Datensätze unterschiedlich gut funktionieren. Vor allem perfektes Hashing stellt, in seinen verschiedenen Formen, einen viel versprechenden Ansatzpunkt dar. Allerdings wird hierzu eine schnell zu berechnende, konfliktfreie Hash-Funktion benötigt wird. Daher sollen in einem ersten Schritt bestehende Verfahren analysiert und auf ihre Tauglichkeit hin bewertet werden. Anschließend soll mit den dort gewonnenen Erkenntnissen die neue Lösung entworfen, implementiert und getestet werden.

Die Arbeit kann als Bachelor- oder Master-Thesis bearbeitet werden, wobei im Rahmen einer Masterarbeit zusätzlich eine genaue Analyse des Verhaltens und der Leistungsfähigkeit der neuen Lösung mittels Softwaretools, sowie gegebenenfalls weiteres Tuning gefordert wird. Ebenso soll ein existierendes Verfahren zum räumlichen, perfekten Hashing implementiert und bezüglich der Geschwindigkeit mit der neu entworfenen Lösung verglichen werden.

Empfohlene Vorkenntnisse:

• Gute Programmierkenntnisse in C/C++,

• Kenntnisse der Speicherarchitektur moderner Rechner

• Grundkenntnisse im Bereich Graphentheorie

• Gute Englisch-Lesekenntnisse (zum Verständnis der Literatur)

Publikationen

• Christian Schröppel and Jens Wackerfuß: Algebraic graph theory and its applications for mesh generation. PAMM, 12(1):663–664, 2012.
• Sylvain Lefebvre and Hugues Hoppe : Perfect spatial hashing. Microsoft Research