Special Seminar: Srinivasa Rao Satti "Dynamic Compressed String Representations Supporting Random Access"

Dynamic Compressed String Representations Supporting Random Access

Srinivasa Rao Satti

Abstract:

In the first part of the talk, I will present a scheme for storing a dynamic string S in compressed form, while permitting following operations directly on the compressed representation of S: (a) access a substring of S; (b) replace, insert or delete a symbol in S; (c) count how many occurrences of a given symbol appear in any given prefix of S (called rank operation); and (d) locate the position of the i-th occurrence of a symbol inside S (called select operation). An important application of this result is in Compressed Random Access Memory (CRAM), where one can represent the memory of a computer in compressed form while being able to support random access efficiently without decompressing the whole string.These results extend or improve the bounds of previous work by Ferragina and Venturini [SODA, 2007], Jansson et al. [ICALP, 2012], and Nekrich and Navarro [SODA, 2013]. In the later part of the talk, I will present an overview and future directions of my research.

Bio:  

Srinivasa Rao Satti received his PhD in Theoretical Computer Science from the Institute of Mathematical Sciences, Chennai, India in 2002 under the supervision of Prof. Venkatesh Raman. He is currently working as an Associate Professor in the School of Computer Science and Engineering at Seoul National University, South Korea. He has worked as a researcher at University of Leicester, UK, University of Waterloo, Canada, IT University of Copenhagen, Denmark, and Aarhus University, Denmark before joining Seoul National University in 2009. His primary research area is succinct data structures. His main contributions to this field include optimal compressed representation of bitvectors, succinct tree representation as well as indexes and encodings for various extensions of range minimum data structures. His other research interests include database indexing, external memory algorithms and space-efficient graph algorithms.