Smaller and faster: Succinct data structures

Jérémy Barbay

Departamento de Ciencias de la Computación, FCFM, Universidad de Chile

FIRST PhD course, IT University of Copenhagen, December 15 and 16, 2008

Abstract

Succinct data structures replace static instances of pointer based data structures, improving performance in both time and space in the word RAM model (a restriction of the RAM model where the size of each machine-word is bounded). Introduced by Jacobson in 1989, the concept yields both theoretical and practical interesting results.

I will give an overview of some key concepts, structured in five lectures of 1h15, each lecture covering one concept with one example of technical result on it, and ending with some light homework to take home.

No other background is required besides a good understanding of regular courses in (theoretical) computer science.

Preliminary schedule

Monday December 15 (room 4A 20)

Tuesday December 16 (room 4A 20)

Bio

Jérémy received a BSc in Mathematics in 1997 in Rouen, a Master in 1998 and a PhD in 2002, both in CS in Orsay. He was a posdoctoral fellow at the university of British Columbia from 2002 to 2004 and an assistant professor at the university of Waterloo from 2004 to 2008. He is now an assistant professor at the university of Chile.

Jérémy's research spans several domains, and can be divided into two main topics and a few alternate ones. The two main interests concern the adaptive analysis of the complexity of algorithms, and the design of succinct data structures. His other interests concern application of those results to information retrieval, mathematical models for the theory of evolution, electronic tools for teaching and e-teaching, and publication protocols for digital documents.

Participants

Rasmus Pagh (pagh@itu.dk), organizer.

Anders Schack-Nielsen, ITU

Andrea Campagna, ITU

Bjørn Petersen, DIKU

Jeppe Winther Larsen, ITU

Laurent Flindt Muller, DIKU

Mads Kehlet Jepsen, DIKU

Milan Ruzic, ITU

Philip Bille, ITU

Rasmus Resen Amossen, ITU

Thore Husfeldt, ITU

 
barbay.txt · Last modified: 2008/12/14 23:39 by pagh
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki