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
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.
Die Arbeit wird betreut von Johannes Fischer und Patrick Dinklage.