Succinct data structures: From theory to practice

Simon Gog (University of Melbourne)

CSIRO ICT IR and friends

DATE: 2013-11-11
TIME: 16:00:00 - 17:00:00
LOCATION: CSIRO seminar room
CONTACT: JavaScript must be enabled to display this email address.

ABSTRACT:
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. One recent example of the adoption of the techniques in industry is the social graph of Facebook.

The library code is available at: https://github.com/simongog/sdsl-lite.

http://es.csiro.au/
BIO:
Simon Gog is a postdoctoral researcher in the Department of Computing and Information Systems at The University of Melbourne. He completed his PhD in 2011 at Ulm University, Germany, and has research interests in string processing, information retrieval, and algorithm engineering. His main focus is on implementing efficient compact or succinct structures, and on carrying out experimental investigations in a way that leads to reliable and reproducible results.