Date: 15 Mar 2007 From: jyrki@diku.dk Subject: Guest lecture: Srinivasa Rao Title: Succinct representations of trees Speaker: S. Srinivasa Rao, IT University of Copenhagen Time: Wednesday, 21 March 2007, 15.15–16.00 Place: Lecture theatre N034 at DIKU Abstract: Trees are one of the most fundamental structures in computing. They are used in almost every aspect of modeling and representation for explicit computations. Standard representations of trees using pointers are quite wasteful of space, and could account for the dominant space cost in applications such as storing a suffix tree. For example, a standard representation of a binary tree on n nodes uses 2n pointers or 2n log n bits. This is a factor of log n more than the minimum number of bits necessary, as there are less than 4^n distinct binary trees on n nodes. Also, this only supports finding the left/right child of a node efficiently. To support other useful queries like finding the parent or size of a subtree, we need to augment the structure with roughly an additional n log n bits for each query. In this talk, starting with a brief introduction to succinct or highly space efficient data structures, I will present some tree representations that take only 2n + o(n) bits and support various useful queries, including those that are supported by a standard representation, efficiently. I will also discuss some applications where these can be used. Srinivasa's home page: http://www.itu.dk/people/ssrao/ PE-lab's home page: http://www.diku.dk/~jyrki/PE-lab/