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 Johannes Fischer und Florian Kurpicz.

 
Last modified: 2019-12-17 15:18 (external edit)
DokuWikiRSS-Feed