Algorithms on grammar-compressed strings, trees, and graphs
COM1 Level 3
MR1, COM1-03-19
Abstract:
The speed of algorithms on massive structured data like strings, trees, and graphs depends on the size of the given data. Grammar-based compression is a technique to compress the size of given data while still allowing to read or to modify the data with a little time overhead. When data access methods to compressed data are chosen carefully, the speed-up gained by data size reduction significantly predominates the time overhead needed to partially uncompress compressed data. The talk gives an overview of the key ideas behind grammar-based compression techniques for strings, trees and graphs. Furthermore, it shows some examples for faster algorithms on compressed data.
Biodata:
Stefan Bottcher is a professor for computer science at Paderborn University in Germany. His background research areas are query processing, transactions, and security in database systems. His current main research topics are graph databases, string processing and bioinformatics. He has published more than 100 papers. Furthermore, he has been cooperating with more than 20 companies in various industry branches. He is furthermore active in computer science education in companies and is working on explanation systems for e-learning.