===== Verteilte parallele Konstruktion von Wavelet-Trees (mithilfe von Thrill) =====

==== Beschreibung ====
Wavelet Trees sind eine platzeffiziente Datenstruktur mit einer Vielzahl von Anwendungen in der Text-Indexierung, algorithmischen Geometrie.
Die effiziente (sequentielle) Konstruktion ist bereits in einer [[fischer:abschlussarbeiten:wavelet|Bachelorarbeit]] untersucht worden.
Zudem haben wir die parallele Konstruktion (im Shared Memory) [[https://doi.org/10.1137/1.9781611975055.2|untersucht]].
Ziel dieser Abreit ist die Adaption und Weiterentwicklung der dort beschriebenen Algorithmen für den verteilten Speicher (Distributed Shared Memory).
Die Umsetzung erfolgt mithilfe von [[http://project-thrill.org/|Thrill]].

==== Typ ====
Masterarbeit.

==== Bearbeiter ====
[[staff:dinklage|Patrick Dinklage]]

==== Das sollten Sie mitbringen ====
  * Spaß an algorithmischen Problemstellungen
  * gute Programmierkenntnisse in C++
  * Erfahrungen im Umgang mit Thrill oder die Bereitschaft, sich selbständig einzuarbeiten

==== Betreuer ====
Bei Interesse wenden Sie sich bitte an [[staff:fischer|Johannes Fischer]] oder [[staff:kurpicz|Florian Kurpicz]]