Abstract:
Compression is a ubiquitous tool for reducing storage requirements.Without further efforts, though, access to the compressed data requires decompressing it first.

Succinct and compressed data structures try to combine (asymptotically) optimal space usage with efficient access operations directly on thecompressed representation.

I will exemplify some techniques from this area on the range-minimum problem: Given an array A1..n of numbers,the task is to construct a data structure (in a preprocessing step)that can efficiently answer range-minimum queries:
rmq(i,j) = k in {i,...,j} so that Ak = min{Ai,...,Aj}.

rmq data structures have applications in text indexing,e.g., for simulating suffix-tree operations when storing onlysuffix array and lcp array.

I will present a novel compressed rmq data structure thatwas inspired by entropy computations for random BSTs. In passing, I will identify techniques that often help to reduce therunning time of access operations.

Presented by:
Sebastian Wild is postdoctoral fellow in the group of Ian Munroat University of Waterloo, Canada.He holds a PhD from University of Kaiserslautern, Germany,where he also completed his studies of computer science.His dissertation on the analysis of quicksort was awardedthe GI Dissertationspreis 2016 for the best PhD thesis in computer science in Germany, Austria and Switzerland.

Sebastian's research interests are the design and analysis of algorithms and data structures, in particular improving the fundamentalbuilding blocks of computer science like sorting and searchingbeyond worst-case and big-Oh bounds.