Campus Event Calendar
Event Entry
What and Who
Towards Universal Succinct Representations of Trees
Arash Farzan
University of Waterloo
Talk
AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 6 April 2009
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
A succinct representation of a combinatorial object is a highly space-efficient representation on the RAM with logarithmic word size that supports dynamic queries in constant time. In this talk, we mainly focus on succinct representation of trees which have found an increasing number of applications in indexing massive collections of textual and semi-structured data.
In the first part of the talk, we present a new approach in succinct representation of trees which unifies and enhances the power of pre-existing succinct representations of trees for various families of trees (such as ordered and k-ary trees).
In the second part of the talk, we discuss some related topics in succinct representations. We first sketch a dynamic version of our succinct representation of trees, where the encoded tree is changing by insertion and deletion of nodes. We conclude by exploring the topic of space lower bounds for succinct encodings.
This is joint work with J.Ian Munro, Rajeev Raman, and S.Srinivasa Rao.
Contact
Spyros Angelopoulos
--email hidden
passcode not visible
logged in users only
Spyros Angelopoulos, 04/03/2009 13:56
Spyros Angelopoulos, 04/03/2009 13:56 -- Created document.
Spyros Angelopoulos, 04/03/2009 13:56 -- Created document.