Algorithmic Foundations
In the research area of Algorithmic Foundations, we investigate fundamental problems of computer science that are often subproblems of larger structures. Our topics of research mostly stem from the context of text indexing and information retrieval, particularly classic pattern matching, where the task is to find a pattern in a much longer sequence (e.g., within a collection of documents, human genomes, ...), as well as text compression, where repeating patterns are used to compute a smaller representation.
Our special interest lies in the ability to process or index massive datasets (big data), which requires the use of succinct data structures. The goal of these data structures is staying close to the theoretically optimal memory requirements while still being able to answer queries efficiently. In this regard, we also consider advanced computational models such as external memory and, in particular, parallel computation on systems with shared memory (multicore) as well as distributed systems (clusters).
As part of the chair for Algorithm Engineering, we implement many of the data structures we design with the goal of being competitive with existing solutions in terms of running times - for construction as well as answering of queries - and memory requirements.
Algorithm Engineering can be understood as a cycle: after analysis of a newly designed data structure, it is implemented and investigated in practice via experiments. Aside from measurements of running times, memory requirements, cache efficiency etc., these experiments also aim at a comparison against potentially existing solutions. Typically, experiments reveal bottlenecks, disadvantageous border cases or other traits that can be improved. This may lead to an adjusted design - and the cycle begins anew.
To achieve the highest possible efficiency in all regards, we prefer the programming language C++ that allows implementations close to the hardware, including the ability to use special hardware features such as vectoring, novel CPU instructions etc.
