Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
fischer:teaching:pg-plads [2019-05-28 08:37]
Patrick Dinklage
fischer:teaching:pg-plads [2019-10-16 15:59] (current)
Patrick Dinklage
Line 1: Line 1:
-====== ​PG PlaDs ======+====== ​Projektgruppe ​PlaDs ====== 
 + 
 +===== News ===== 
 + 
 +  * Das wöchentliche PG-Treffen wurde in der ersten Sitzung auf **Mittwoch, 10-12 Uhr (c.t.)** verlegt. Der neue Termin gilt ab dem 23.10.2019 
 +  * <color #​888888>​Das wöchentliche PG-Treffen wurde festgelegt auf **Mittwoch, 14-16 Uhr (c.t.)** und findet erstmalig am **16.10.2019** statt.</​color>​ 
 +  * <color #​888888>​Das PG-Blockseminar findet am **Do, 10.10.2019** (OH12, Raum 3.030) und **Fr., 11.10.2019** (OH14, Raum 202) jeweils **ab 10:00 Uhr (s.t.)** statt.</​color>​ 
 +  * <color #​888888>​Die Einreichung der Implementierungen für die Bit Vector Coding Challenge soll bis **Mo, 07.10.2019 um 08:00 Uhr** erfolgen.</​color>​ 
 +  * <color #​888888>​Der Ersttermin der Projektgruppe findet am **09.07.2019** um **10:00** Uhr im Raum **OH12 3.030** statt.</​color>​ 
 +  * <color #​888888>​Die Einzelpräsentation findet am **03.06.2019** um **14:00** Uhr im Raum **OH14 202** statt.</​color>​ 
 + 
 +===== 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//). **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 ​=== 
 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. 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.
  
Line 16: Line 28:
   * Vorgängerdatenstrukturen (z. B. van-Emde-Boas-Trees)   * Vorgängerdatenstrukturen (z. B. van-Emde-Boas-Trees)
  
-===== News ===== +===== Seminar ​===== 
-  * Die Einzelpräsentation ​findet am **03.06.2019** ​um **14:00** Uhr um Raum **OH14 202** statt.+ 
 +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. 
 + 
 +Der Vortrag dient hauptsächlich dem Zweck, den anderen PG-Mitgliedern einen Überblick über das erarbeitete Thema zu geben. Es geht hier also weniger um die formale Vollständigkeit (Beweise usw.) als um eine didaktisch wertvolle Darbietung des Themas, so dass die anderen Mitglieder die Funktionsweise verstehen. Versetzen Sie sich in diese und überlegen Sie, welche Informationen wirklich zum Verständnis notwendig sind. Die Ausarbeitung sollte dann etwas tiefgreifender werden. Grundsätzlich richten Sie sich am besten an unsere {{:​fischer:​teaching:​allgemeine_seminarhinweise_ads.pdf |allgemeinen Seminarhinweise}} (Abschnitte 5-7, wobei der Vortrag eben nur rund 25 Minuten dauern soll). 
 + 
 +Die folgenden Punkte sollten rüberkommen:​ 
 + 
 +  * Was ist die Problemstellung (informell und formal)? 
 +  * Welche Anfragen beantwortet die vorgestelle Datenstruktur?​ 
 +  * Welche Zeit- und Platzschranken gelten für Konstruktion,​ Datenstruktur und Anfragen? 
 +  * Was sind herauszustellende Teilprobleme und Teildatenstrukturen?​ 
 +  * Welche vergleichbaren Datenstrukturen gibt es und wie unterscheiden sie sich (grob)? 
 +  * Gibt es bereits Implementierungen?​ Welche Eigenschaften haben diese, wie schneiden sie in bereits durchgeführten Vergleichen ab? 
 +  * Sind bereits besondere Herausforderungen für eine Implementierung erkennbar?​ 
 + 
 +Die Ausarbeitungen sollen mit LaTeX geschrieben werden. Verwenden Sie hierzu den LIPIcs-Stil - eine Vorlage befindet sich [[https://​www.dagstuhl.de/​en/​publications/​lipics/​instructions-for-authors/​|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 | [[https://​www.sciencedirect.com/​science/​article/​pii/​S1570866715001057|Fischer & Peters: GLOUDS - Representing tree-like graphs]] | LOUDS, Wavelet Tree | M.F. | 
 +|2| Document Retrieval | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-642-40273-9_22|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) | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-642-38905-4_23|Tabei et al.: A Succinct Grammar Compression]] | Dictionary, Wavelet Tree | J.T. | 
 +|5| Grammatikkompression | [[https://​ieeexplore.ieee.org/​document/​8712661|Furuya et al.: MR-RePair Grammar Compression based on Maximal Repeats]] | Maximaler Repeat, Re-Pair | J.M. | 
 +|6| Minimal Perfect Hashing | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-07959-2_12|Müller et al.: Retrieval and Perfect Hashing Using Fingerprinting]] | Hashing, Karp-Rabin-Fingerprint | A.H. | 
 +|7| Minimal Perfect Hashing | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-38851-9_23|Genuzio et al.: Fast Scalable Construction of (Minimal Perfect Hash) Functions]] | Broadword Programming,​ Gaussian Elimination | H.D.D. | 
 +|8| Planare Graphen | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-62127-2_33|Ferres et al.: Fast and Compact Planar Embeddings]] | Duale Graphen, Spannbäume,​ Turán-Repräsentation | A.K. | 
 +|9| <​del>​Range Minimum Queries</​del>​ | Kowalski & Gabrowski: Faster range minimum queries | kartesischer Baum | //(nicht vergeben)// | 
 +|:::| ::: | Gawrychowski et al.: Compressed Range Minimum Queries | Sparse Table | ::: | 
 +|10| <​del>​Vorgängerdatenstrukturen</​del>​ | [[https://​link.springer.com/​chapter/​10.1007%2F978-3-319-19929-0_30|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 | //(nicht vergeben)// | 
 +|:::| ::: | [[http://​algo2.iti.kit.edu/​dementiev/​files/​veb.pdf|Dementiev et al.: Engineering a Sorted List Data Structure for 32 Bit Keys]] | van Emde Boas Tree, Hashing | ::: | 
 + 
 +=== Ablauf === 
 + 
 +== Donnerstag, 10.10.2019 == 
 + 
 +Ort: OH12 3.030 
 + 
 +^ Zeit (s.t.) ^ Vortrag ^ 
 +| 10:00 - 10:15 | Einführung | 
 +| 10:15 - 11:00 | Document Retrieval (M.T.) | 
 +| 11:00 - 11:45 | Baumähnliche Graphen (M.F.) | 
 +| 11:45 - 12:30 | Planare Graphen (A.K.) | 
 +| 12:30 - 13:30 | Mittagspause | 
 +| 13:30 - 14:15 | Dynamische Bitvektoren mit Rank/Select (J.-P.T.) | 
 + 
 +== Freitag, 11.10.2019 == 
 + 
 +Ort: OH14 202 
 + 
 +^ Zeit (s.t.) ^ Vortrag ^ 
 +| 10:00 - 10:45 | Minimal Perfect Hashing 1 (A.H.) | 
 +| 10:45 - 11:30 | Minimal Perfect Hashing 2 (H.D.D.) | 
 +| 11:30 - 12:15 | Grammatikkompression (J.M.) | 
 +| 12:15 - 13:00 | Grammatiken / SLPs (J.T.) | 
 +| 13:00 - 14:00 | Mittagspause | 
 +| 14:00 - 15:00 | Bit Vector Coding Challenge | 
 + 
 +===== Coding Challenge ===== 
 + 
 +In der Bit Vector Coding Challenge soll die Programmierung mit C++ im Rahmen von platzeffizienten Datenstrukturen aufgebaut bzw. aufgefrischt und vertieft werden. 
 + 
 +Der Code-Rahmen und die Aufgabenstellung befinden sich hier: [[https://​github.com/​pdinklag/​bvcc]] 
 + 
 +Die Aufgaben sind zum Blockseminar zu erarbeiten, wo dann ein Benchmark durchgeführt wird, um den oder die Sieger zu ermitteln. Der Code-Rahmen enthält eine funktionale,​ aber wenig platzeffiziente Implementierung für Bitvektoren,​ Rank und Select, die durch eine eigene ersetzt werden soll. 
 + 
 +Folgendes Bild hatten wir in der ersten PG-Sitzung zur Rank1-Datenstruktur nach dem Buch von Navarro (Compact Data Structures) produziert:​ 
 +{{ :​fischer:​teaching:​pg-rank.pdf |}}
 
Last modified: 2019-05-28 08:37 by Patrick Dinklage
DokuWikiRSS-Feed