Unit 6: Succinct Data Structures

This unit covers:

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

Material

• slides

• lecture notes

• Animationen:
  • Wavelet Trees
  • Wavelet Trees for Graphs
     
• Video 6-1 (2026-06-22, 12:25): Computing over Compressed Data
  
• Video 6-2 (2026-06-22, 12:03): Bitvectors
  
• Video 6-3 (2026-06-29, 39:27): Rank-Index for Succinct Bitvectors
  
• Video 6-4 (2026-06-29, 30:19): Select-Index for Succinct Bitvectors
  
• Video 6-5 (2026-06-30, 48:09): Compressed Bitvectors
  
• Video 6-6 (2026-06-30, 16:53): MMPHF & Elias-Fano
  
• Video 6-7 (2026-06-30, 16:20): Wavelet trees
  
• Video 6-8 (2026-07-06, 49:41): Succinct Trees
  
• Video 6-9 (2026-07-06, 11:23): Graphs via Wavelet Trees
  

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