Simon Gog is a research fellow in the Department of Computing and Information Systems at The University of Melbourne. He did his PhD at Ulm University, Germany, supervised by Enno Ohlebusch.
Succinct Data Structure use space close to the compressed representation of the underlaying objects but provide operations in
the same time complexity as their uncompressed counterparts. Since the early 90s, more and more succinct versions of data structures have been proposed -- ranging from bitvectors to complex information retrieval (IR) systems. Despite their attractive theoretical properties, there are only rare examples of practical use in systems. One reason for this is that an efficient implementation of complex structures, like a compressed text index, requires not only a profound knowledge of data compression and structures but also of modern hardware. In this seminar, I will give a introduction to Succinct Data Structures and present the C++ template library SDSL, which represents the state of the art in the field. This library facilitates easy composition of compression and indexing tools, which can be used to operate on large data sets in areas as Bioinformatics, IR, and Natural Language Processing.