Abstract
I will present several recent results on compressed data structures. All
have in common that algorithm engineering helps theory meet practice. In
particular, we will see practical solutions whose space consumption is
very close to theoretical lower bounds. Concretely, I will cover bit
vectors with support for rank and select, perfect hashing, static
function retrieval, and replacements for Bloom filters.
Bio
Peter Sanders received his PhD in computer science from Universität
Karlsruhe in 1996. After a short postdoc period at Chalmers University
in Gothenburgh, Sweden, he joined the Max Planck Institute for
Informatics in Saarbrücken. He returned to Karlsruhe as a full professor
in 2004. He leads the Algorithm Engineering Group at the Informatics
Department of KIT in the Institute for Theoretical Computer Science.
Peter Sanders won a number of prices among them the DFG Leibniz Award
2012 and a 2020 ERC advanced grant for the project "Engineering Scalable
Algorithms for the Basic Toolbox -- ScAlBox". He has more than 300
publications, mostly on algorithms for large data sets. This includes
parallel algorithms (sorting, SAT solving, data structures, multi-core
algorithm libraries, load balancing, communication scheduling, e.g.,
using network coding,...), memory hierarchies (caches, disks, storage
servers,...), graph algorithms (route planning, graph partitioning...),
randomized algorithms, compressed data structures, full text indices, etc.