Dynamic data structures: the interplay of invariants and algorithm design

PhD defence, Monday 18 November 2013. Casper Kejlberg-Rasmussen.

2013.11.18 | Nanna Maria Elgaard Pedersen

Casper Kejlberg-Rasmussen

Casper Kejlberg-Rasmussen

The amount of communication and data we wish to keep has grown exponentially throughout the last thirty years. This development is caused by the extensive use of computers and the Internet in all areas of society. The Large Hadron Collider project alone produces 25 petabytes of data a year. These extreme amounts of data are too large to fit within the internal memory of a computer, and have to be stored externally on disks and tapes. Accessing data on disks and tapes is magnitudes slower than doing so on internal memory such as RAM and CPU caches. Accessing data most efficiently on external media is achieved by loading large chunks of data consecutively stored on the media. Within the area of I/O-effective algorithms, these characteristics of external media are used in the design of algorithms and data structures.

The extreme size of data alone provides problems, but that is not all. Changes frequently occur because of new observations and changes in existing data. These extra challenges make data structure design even more difficult where I/O-efficiency is still required. Many fundamental problems still have no satisfying I/O-efficient solutions.

In the course of his research, Casper Kejlberg-Rasmussen designed new I/O-efficient and dynamic data structures for skyline queries and distribution-sensitive dictionaries. Skyline queries often appear within database systems for all kinds of data. A dictionary is a fundamental data structure for storing keys and their associated values. Dictionaries are applied within all branches of software development. Distribution-sensitive dictionaries guarantee response times that depend on the distribution of queries to the dictionary.

The PhD degree was completed at the Department of Computer Science, Science and Technology, Aarhus University.

Time: Monday 18 November 2013 at 14.15
Place: Building 5342, room 333 (ADA), Department of Computer Science, Aarhus University
Title of dissertation: Dynamic Data Structures: The Interplay of Invariants and Algorithm Design
Contact information: Casper Kejlberg-Rasmussen, ckr@cs.au.dk
Members of the assessment committee:
Professor Roberto Grossi, Department of Informatics, University of Pisa, Italy
Professor Rasmus Pagh, IT University of Copenhagen
Associate Professor Anders Møller (chair), Department of Computer Science, Aarhus University
Main supervisor:
Associate Professor Gerth Stølting Brodal, Department of Computer Science, Aarhus University
Language: The dissertation will be defended in English

The defence is public.
The dissertation is available for reading at the Graduate School of Science and Technology/GSST, Ny Munkegade 120, building 1521, room 112, 8000 Aarhus C.

PhD defence
Comments on content: 
Revised 22.06.2017