Towards efficient algorithms on compressed graph databases

Abstract: The speed of algorithms on massive graphs depends on the size of the given data. Grammar-based compression is a technique to compress the size of a graph while still allowing to read or to modify the graph 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 un-compress compressed data.

The talk gives an overview of the key ideas behind grammar-based compression for large graphs and shows how to apply graph compression to graph databases. Furthermore, it introduces re-compression as a fast technique to keep compressed graphs small when they are frequently modified.

Bio:
Stefan Böttcher is a professor for computer science at Paderborn University in Germany.

His background research areas are query processing, parallel transactions, and security in database systems.

His current main research topics are compressed graph databases, and genome index construction for bio-informatics applications. He has published more than 100 papers. Furthermore, he has been cooperating with more than 20 companies in various industry branches. He is active in computer science education in companies and is working on explanation systems for e-learning.