Unit 6: Succinct Data Structures

This unit covers:

• bitvectors
• compressed bitvectors
• succinct data structures for various objects

Material

• preliminary slides

• lecture notes

• Animationen:
  • Wavelet Trees
  • Wavelet Trees for Graphs
     
• Video 6-1 (2026-06-22): Computing over Compressed Data

• Video 6-2 (2026-06-22): Bitvectors

• Video 6-3 (2026-06-29): Rank-Index for Succinct Bitvectors

• Video 6-4 (2026-06-29): Select-Index for Succinct Bitvectors

Further sources

The presentation is my own, but takes inspiration from

• Navarro. Compact Data Structures (2016)
• Kurpicz. Lecture Advanced Data Structures (2024) KIT

---

Unit 5  ⋅  Syllabus  ⋅  Unit 7