Data Structures

Summary

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.