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/