This is an old revision of the document!
Table of Contents
Projektgruppe PlaDs
News
- Das wöchentliche PG-Treffen wurde festgelegt auf Mittwoch, 14-16 Uhr (c.t.) und findet erstmalig am 16.10.2019 statt.
- Das PG-Blockseminar findet am Do, 10.10.2019 und Fr., 11.10.2019 jeweils ab 10:00 Uhr (s.t.) statt.
- Der Ersttermin der Projektgruppe findet am 09.07.2019 um 10:00 Uhr im Raum OH12 3.030 statt.
- Die Einzelpräsentation findet am 03.06.2019 um 14:00 Uhr im Raum OH14 202 statt.
Info
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 Projektgruppe
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)
Seminar und Coding Challenge
Aufgabe im Seminar ist das Zusammentragen der in der vorgegebenen Literatur vorgestellten platzeffizienten Datenstrukturen. Dies umfasst
- einen 25-30-minütigen Vortrag im Blockseminar und
- eine 8-10-seitige Ausarbeitung mit der Idee, dass sie später in den PG-Bericht übernommen werden kann.
Die Ausarbeitungen sollen mit LaTeX geschrieben werden. Verwenden Sie hierzu den LIPIcs-Stil - eine Vorlage befindet sich hier (lipics-v2019-authors.zip
).
Das PG-Blockseminar findet einmalig am Do, 10.10.2019 und Fr., 11.10.2019 jeweils ab 10:00 Uhr statt.
Themen und Zuordnung
Das Seminar umfasst folgende Themen. Die Literatur wird bereitgestellt, ist aus dem Uninetz aber auch unter den angegebenen Links abrufbar.
# | Thema | Literatur | Stichworte | Zugewiesen an |
---|---|---|---|---|
1 | Baumähnliche Graphen | Fischer & Peters: GLOUDS - Representing tree-like graphs | LOUDS, Wavelet Tree | M.F. |
2 | Document Retrieval | Hon et al: Indexes for Document Retrieval with Relevance (ohne External Memory) | Suffixbaum, Compressed Suffix Array | M.T. |
3 | Dynamische Bitvektoren mit Rank/Select | Navarro: Compact Data Structures (Kapitel 12.1) | komprimierter Bitvektor, balancierter Suchbaum | J.-P.T. |
4 | Grammatiken (SLPs) | Tabei et al.: A Succinct Grammar Compression | Dictionary, Wavelet Tree | J.T. |
5 | Grammatikkompression | Furuya et al.: MR-RePair Grammar Compression based on Maximal Repeats | Maximaler Repeat, Re-Pair | J.M. |
6 | Minimal Perfect Hashing | Müller et al.: Retrieval and Perfect Hashing Using Fingerprinting | Hashing, Karp-Rabin-Fingerprint | A.H. |
7 | Minimal Perfect Hashing | Genuzio et al.: Fast Scalable Construction of (Minimal Perfect Hash) Functions | Broadword Programming, Gaussian Elimination | H.D.D. |
8 | Planare Graphen | Ferres et al.: Fast and Compact Planar Embeddings | Duale Graphen, Spannbäume, Turán-Repräsentation | A.K. |
9 | Range Minimum Queries | Kowalski & Gabrowski: Faster range minimum queries | kartesischer Baum | (nicht vergeben) |
Gawrychowski et al.: Compressed Range Minimum Queries | Sparse Table | |||
10 | Vorgängerdatenstrukturen | Matsuoka et al.: Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree (nur Abschnitt 3) | van Emde Boas Tree, b-Bäume | F.B.L. |
Dementiev et al.: Engineering a Sorted List Data Structure for 32 Bit Keys | van Emde Boas Tree, Hashing |
Bit Vector Coding Challenge
In der Coding Challenge soll die Programmierung mit C++ im Rahmen von platzeffizienten Datenstrukturen aufgebaut bzw. aufgefrischt und vertieft werden.
Der Code-Rahmen befindet sich hier: https://github.com/pdinklag/bvcc
Er enthält funktionale, aber naive Implementierungen für Bitvektoren, Rank und Select, die durch durch eigene Lösungen ersetzt werden sollen. Die Aufgaben sind ebenfalls zum Blockseminar zu erarbeiten, wo ein Benchmark durchgeführt wird, um den oder die Sieger zu ermitteln.
Folgendes Bild hatte ich in der ersten PG-Sitzung zur Rank1-Datenstruktur produziert: pg-rank.pdf