Jump to Navigation | Search | Content area | Page footer
( http://www.dagstuhl.de/10091 )

28.02.10 - 05.03.10, Seminar 10091

Data Structures

Organizers

Lars Arge (Aarhus University, DK)
Erik D. Demaine (MIT - Cambridge, US)
Raimund Seidel (Universität des Saarlandes, DE)



For support, please contact

Claudia Thiele for administrative aspects

Angelika Mueller for scientific aspects

Documents

Participants and shared Documents
Seminar Wiki

(Use seminar number and access code to log in)

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.

Related Seminars

Classification

  • Data structures
  • Data bases/information retrieval
  • Networks

Keywords

  • Data structures
  • Algorithms
  • Large data sets

Publications

Books from the participants of the current Seminar 

Book exhibition in the library, 1st floor

(during the seminar week)

Each Dagstuhl Seminar has the possibility to publish a volume of  "Dagstuhl Seminar Proceedings" online. Details will be discussed during the seminar.

Background information on

Dagstuhl Seminar Proceedings

Follow-Up Publications

Please inform us, when a further publication results from your seminar. These Follow-Up publications are listed separately and are presented on a special shelf on the ground floor of the library.