Differences
This shows you the differences between two versions of the page.
| — |
fischer:abschlussarbeiten:special_cpu_wavelet_tree [2019-12-17 15:18] (current) Florian Kurpicz created |
||
|---|---|---|---|
| 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]]. | ||