Data Structures

Motivation

The seminar will cover research on data structures in general, and some special, current topics. General topics include data structures geared towards memory hierarchies, data structures in the context of the large computer word model and its inherent small scale bit parallelism, distributed data structures, competitive and randomized analysis, efficient structures with minimal space requirements, and others. In addition there will be emphasis on three special topics:

Data structures and communication complexity

Recently a communication complexity view on data structures has been used to prove a number of surprising, breakthrough lower bounds for a number of data structuring problems in powerful computational models (cell probe model, word RAM). How far do these ideas carry?

The dynamic optimality conjecture

The question is whether there is a single binary search tree update strategy that is competitive (in the technical sense) with every other update strategy. More than twenty years ago Sleator and Tarjan conjectured that splay trees consitute such a competitive strategy. After a long time of lack of progress in this question (in spite of many serious attempts) a number of breakthroughts were achieved recently (some O(log log n)-competitive strategies; a purely combinatorial formulation of the dynamic optimality conjecture). These breakthroughs still fall short of fully solving the problem. Further insight is needed and the proposed workshop should be a good platform for arriving at such insight.

Data structures for modern, commodity parallel hardware architectures

We are seeing the emergence of highly parallel architectures in commodity processors. Modern CPUs feature several cores. Similarly general purpose GPUs have evolved into freely programmable processors with many cores. The memory and synchronization of these multi-core processors does not resemble any of the existing theoretical models such as PRAM, or networked processors. Since these new highly parallel processors are about to be ubiquitous it is important to understand the possibilites and theoretical limitations of these processors and study data structuring in this context.