Differences
This shows you the differences between two versions of the page.
— |
fischer:abschlussarbeiten:special_cpu_wavelet_tree [2019-12-17 15:18] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ===== Wavelet-Tree-Konstruktion mit speziellen CPU-Instruktionen ===== | ||
+ | ==== Beschreibung ==== | ||
+ | Wavelet-Trees (WT) sind eine platzeffiziente Datenstruktur mit einer Vielzahl von Anwendungen in der Text-Indexierung, algorithmischen Geometrie. | ||
+ | Ziel dieser Arbeit ist die Konstruktion von WTs unter Ausnutzung spezieller CPU-Instruktionen (z.B. Packed Shuffle Bytes oder Parallel Bits Extract). | ||
+ | In der Praxis sollte dieser Algorithmus der schnellste sequentielle WT-Konstruktionsalgorithmus sein, siehe Kaneta (2018). | ||
+ | Der zu implementierende Algorithmus wurde von Babenko et al. (2015) und Munro et al. (2016) vorgestellt. | ||
+ | |||
+ | ==== Typ ==== | ||
+ | Masterarbeit | ||
+ | |||
+ | ==== Das sollten Sie mitbringen ==== | ||
+ | * Spaß an algorithmischen Problemstellungen | ||
+ | * Gute Programmierkenntnisse in C++ | ||
+ | * Kenntnisse in String-Algorithmen und idealerweise parallelen Algorithmen oder die Bereitschaft, sich selbständig einzuarbeiten | ||
+ | |||
+ | ==== Betreuer ==== | ||
+ | Die Arbeit wird betreut von [[staff:fischer|Johannes Fischer]] und [[staff:kurpicz|Florian Kurpicz]]. |