The Myriad Virtues of Succinct Data Structures

28^th February 2012, 16:00 G12
Prof. Rajeev Raman
Department of Computer Science
University of Leicester
UK

Abstract

Modern applications involving processing textual, semi-structured and spatial 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 two recent results, one on random-access to grammar-compressed strings and trees (joint with Bille, Landau, Satti, Sadakane and Weimann, SODA 2011) and range maximum queries (joint with Farzan and Munro).