Succinct data structures

Place
IT University of Copenhagen
Rued Langgaards Vej 7
DK-2300 Copenahagen S
Room 2A20

Date & Time
18th & 19th of May; 10-12 & 13-15

Lecturers
S. Srinivasa Rao (SSR) & Rasmus Pagh (RP)

Contents & tentative schedule:
Thursday morning (SSR):
  • Introduction and Motivation
  • Rank/Select on bit vectors
  • Ordered tree representations
    Thursday afternoon (SSR):
  • Dictionaries
  • Text indexing
    Friday morning (RP):
  • Data compression via BDDs
    Friday afternoon (SSR):
  • Labeled tree representations
  • Other succinct data structures

    Literature:

  • Succinct representation of data structures
    J. Ian Munro and S. Srinivasa Rao
    Chapter 37 in Handbook of Data Structures and Applications
  • Representing trees of higher degree
    David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman and S. Srinivasa Rao
    Algorithmica, 2005. PDF

  • Universal Lossless Data Compression Via Binary Decision Diagrams
    J. Kiefer, P. Flajolet and E-h. Yang