February 26 – March 3 , 2006, Dagstuhl Seminar 06091

Data Structures


Lars Arge (Aarhus University, DK)
Robert Sedgewick (Princeton University, US)
Dorothea Wagner (KIT – Karlsruher Institut für Technologie, DE)

For support, please contact

Dagstuhl Service Team


Dagstuhl Seminar Proceedings DROPS
List of Participants


The design and analysis of algorithms is a fundamental area in computer science. This also involves the development of suitable methods for structuring the data to be manipulated by these algorithms. Hence, algorithms and data structures form a unit, and the right choice of algorithms and data structures is a crucial step in the solution of many problems. For this reason, the design, analysis and implementation of data structures form a classical field of computer science that continues to spawn exciting new research problems.

The Dagstuhl Seminar on Data Structures in 2006 reported on ongoing research on classical data structuring problems as well as application areas such as text retreival and computational geometry. Persistent themes include randomized, cache-oblivious, and succinct data structures. Dagstuhl meetings have played an important role in developing these themes over the past decade.

As in previous meetings, there was some shift of interest away from purely theoretical issues (asymptotic analysis) towards scientific studies that are directly relevant to the use of data structures in practical applications. This shift is motivated by the desire of increasing numbers of researchers in the field to make their results available in form of programs or software packages.

Interest in the topic remains high: another attendance record was set, and several invitees who could not attend expressed their sincere regrets and their strong desire to be invited to future meetings.

A last-minute call from the organizers asked participants to think about the following questions:
- What research problems are you working on lately?
- What critical roadblocks are you facing in addressing them?
- What is the most exciting outcome you could envision if successful?
- Why should anyone be interested in your results?
- What applications do you think are most in need of new research in data structures and algorithms?
- What problems do you think other people need to be working on?

Several of the presentations were provocative responses to these questions. Beyond the scientific talks, there was a particularly fruitful (and sometimes contentious!) session that centered on whether it might be fruitful to step back and gain consensus on significant open problems in the field whose solution would have important longterm impact. As the field has matured over the past 50 (!) years, careful examination of these sorts of issues is an important part of the research landscape.

We thank the team of Schloss Dagstuhl for their hospitality and support making this successful workshop possible.

Dagstuhl Seminar Series


  • Data Bases / Information Retrieval
  • Data Structures / Algorithms / Complexity
  • Web
  • Networks


  • Data structures
  • Algorithms
  • Large data sets
  • External memory algorithms
  • Streaming model


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.