Wavelet Trees sind eine Datenstruktur, die einen Eingabestring so kodieren, dass effizient die Vorkommen eines Zeichens bis zu einer beliebigen Position gezählt (rank) sowie ein beliebiges Vorkommens im String lokalisiert werden kann (select). Überdies kann der Eingabestring für alle Positionen wiederhergestellt werden, so dass dieser nicht mehr explizit gespeichert werden muss.

Die Konstruktion eines Wavelet Trees kann effizient mit einem Divide-and-Conquer-Verfahren (Domain Decomposition) parallelisiert werden, wobei jede Einheit (z.B. ein Prozessorkern) zunächst den Wavelet Tree für ihren Teil des Eingabestrings konstruiert und die Ergebnisse anschließend zusammengeführt werden (merge). Neuere Forschung befasst sich mit der Konstruktion in den Modellen

• shared memory, wo jeder Prozessorkern einen Teil der Eingabe erhält und der Merge-Schritt über geteilten Speicher durchgeführt wird, sowie
• distributed memory, wo jeder Rechner in einem Netzwerk einen Teil der Eingabe erhält und der Merge-Schritt über Netzwerkkommunikation durchgeführt wird.

In dieser Arbeit soll ein Hybrid entwickelt werden: Jeder Rechner im Netzwerk erhält einen Teil der Eingabe, und dort erhält jeweils jeder Prozessorkern einen Teil des Eingabeteils und berechnet zunächst den lokalen Wavelet Tree parallel im shared memory. Danach folgt schließlich ein Merge-Schritt mittels Netzwerkkommunikation.

Bachelorarbeit.

• Spaß an algorithmischen Problemstellungen
• Gute Programmierkenntnisse in C++
• Kenntnisse in String-Algorithmen und idealerweise parallelen Algorithmen oder die Bereitschaft, sich selbständig einzuarbeiten

Die Arbeit wird betreut von Johannes Fischer und Patrick Dinklage.