Title: Random Access to Grammar-Compressed Strings and Trees

Speaker: Rajeev Raman, Univ. Leicester

Time/Date: Monday, May 30, 11-12
Location: Room 3501

Abstract:

Modern applications involving processing textual and semi-structured
data need to do fairly complex computations on data held in the
main memory of a computer, which is a limited resource in many contexts.
While data compression can reduce the size of data, it presents 
significant obstacles to operating on the compressed data, and new data
structuring techniques need to be developed to overcome these obstacles.
After an introduction to the issues, we will focus on one particular
recent result.

Let S be a string of length N compressed into a context-free grammar S of
size n. We present a representation of S achieving O(log N) random access
time, and O(n) construction time and space on the RAM.  We are able to
generalize our results to navigation and other operations on grammar-
compressed trees.  To achieve these bounds, we introduce several new
techniques and data structures of independent interest, including a
predecessor data structure, two "biased"  weighted ancestor data 
structures, and a compact representation of heavy-paths in grammars.

[Although this will be summarizing some other papers, the main result
above is joint with Bille, Landau, Satti, Sadakane and Weimann and some
parts of this paper were presented at the ACM-SIAM SODA 2011.]