This is an old revision of the document!


PG PlaDs

Platzeffiziente Datenstrukturen (succinct data structures) sind solche, die Anfragen effizient beantworten können und deren Speicherplatzverbrauch dabei möglichst nah an der theoretischen unteren Schranke liegt. Ein einfaches Beispiel ist das Zählen von 0- oder 1-Bits in Bitstrings bis zu einer bestimmten Position: Ohne Vorverarbeitung ist dies einfach in linearer Zeit in der Länge des Strings möglich. Es gibt jedoch platzeffiziente Datenstrukturen, die diese so genannten rank-Anfragen in konstanter Zeit beantworten und dabei nur sublinear viel Speicherplatz benötigen. Diese bieten u. a. die Grundlage für platzeffiziente Darstellungen von Bäumen mit nur 2n + o(n) Bits (bei Knotenzahl n).

Ziel der PG

Ziel der Projektgruppe ist der Entwurf und die Implementierung einer hochperformanten, erweiterbaren C++-Bibliothek verschiedener platzeffizienter Datenstrukturen sowie das Benchmarking dieser Bibliothek im Rahmen typischer Anwendungsfälle der entwickelten Datenstrukturen.

Themenbereiche

Die zu implementierenden Datenstrukturen gehören zu folgenden Themenbereichen:

  • Document Retrieval
  • Finden von Wiederholungen in Strings
  • Grammatikbasiere Textkompression (z. B. Re-Pair)
  • Graphen
  • Perfekte Hashfunktionen
  • Suchbäume (z. B. Rot-Schwarz-Bäume)
  • Vorgängerdatenstrukturen (z. B. van-Emde-Boas-Trees)

News

  • Die Einzelpräsentation findet am 03.06.2019 um 14:00 Uhr um Raum OH14 202 statt.
 
Last modified: 2019-05-28 08:37 (external edit)
DokuWikiRSS-Feed