Succinct Representations of Trees

Speaker:	Dr. Srinivasa Rao
		IT University of Copenhagen

Title:		"Succinct Representations of Trees"

Date:		Monday, 13 March 2006

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F
		(Leung Yat Sing Lecture Theatre, ear lift nos. 25/26)
		HKUST

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.


*************************
Biography:

Srinivasa Rao is currently working as an Assistant Professor in the
Combinatorial Logic and Algorithms group at the IT University of
Copenhagen. He obtained his PhD from the Institute of Mathematical
Sciences, India. He spent six months as a Research Associate at the
University of Leicester, UK, and three years as a Postdoctoral Fellow at
the University of Waterloo, Canada. Most of his research work is focused
on data structures, namely space efficient data structures. His other
research interests include external memory algorithms, database theory,
bioinformatics, approximation algorithms and fixed parameter tractability.