Dagstuhl Seminar 98091
Data Structures
( Mar 02 – Mar 06, 1998 )
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/98091
Organizers
- I. Munro (Waterloo)
- P. Widmayer (ETH Zürich)
- S. Näher (Halle)
Contact
Background
The design and analysis of algorithms is one of the fundamental areas in computer science. This also involves the development of suitable methods for structuring the data to be manipulated by these algorithms. In this way, 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 both in research and teaching.
The development of the research in this area has been influenced by new application fields such as CAD, Geographic Information Systems, Molecular Biology and Genetics. Not only new methods and paradigms, such as randomisation or competitive analysis of algorithms, have been developed, but there is also some shift of interest away from theory, e.g., the classical analysis of asymptotic behaviour of algorithms, to more practical issues, such as implementation problems and the usefulness of algorithms in practical applications. One can observe that more and more researchers in computer science also want to make their results available in form of programs or software packages. This trend is also reflected in important international conferences.
Results
The Fourth Dagstuhl Seminar on Data Structures was attended by 41 people from 11 countries. The workshop brought together researchers from all over the world working on different areas of the field of efficient data structures and algorithms. Quite a few interest groups used the workshop to discuss and develop ongoing and new cooperations. Many interesting results and solutions for theoretical and practical problems were presented.
The explicit consideration of external memory is becoming a major concern. It is crucial for the practical value of algorithms and data structures, and it creates interesting theoretical problems. Accordingly, there have been several contributions of external memory algorithms and data structures for problems in Computational Geometry and Geographic Information Systems.
On the theoretical side, there have been interesting contributions concerning search & graph structures. A particular result on hashing and several results on special-purpose data & search structures and added features (such as distributed, fault-tolerant, concurrent...) extended recent insights and limits in the area. Another remarkable result showed a (nearly) exact bound for planar point location.
The geometric data structure section saw new algorithms concerning mobile robots and unknown terrain. An algorithm that extends by far the limits of known problem sizes has been presented for rectilinear Steiner trees.
An open problem session reviewed Knuth's 60 famous open problems. It turned out that the majority of the problems is still unsettled today.
Perspectives
The workshop helped to identify several tracks of research in data structures that play and will continue to play an important role in the area. The field of algorithms and data structures continues its expansion towards previously undiscovered fields.
As computers influence more and more aspects of our lives, data structures are needed for an ever growing domain of applications, with questions of steadily increasing complexity.
The general task of developing and analysing simple and practical algorithms and data structures remains with us.
Thanks
The abstracts of the 35 talks are contained in the published Dagstuhl-Seminar-Report 202, which was compiled by Nora Sleumer. Thanks go to the European Community, which supported the participation of 5 young researchers and 2 key note speakers in the framework of its TMR programme. The organisers would like to thank all participants and especially the team of Schloss Dagstuhl for helping to make the workshop a success. The warm atmosphere of the castle supported discussions and the informal exchange of recent results even beyond the personal perspective. This is exactly what "Schloss Dagstuhl" stands for in the community.
- I. Munro (Waterloo)
- P. Widmayer (ETH Zürich)
- S. Näher (Halle)
Related Seminars
- Dagstuhl Seminar 9145: Data Structures (1991-11-04 - 1991-11-08) (Details)
- Dagstuhl Seminar 9409: Data Structures (1994-02-28 - 1994-03-04) (Details)
- Dagstuhl Seminar 9609: Data Structures (1996-02-26 - 1996-03-01) (Details)
- Dagstuhl Seminar 00091: Data Structures (2000-02-27 - 2000-03-03) (Details)
- Dagstuhl Seminar 02091: Data Structures (2002-02-24 - 2002-03-01) (Details)
- Dagstuhl Seminar 04091: Data Structures (2004-02-22 - 2004-02-27) (Details)
- Dagstuhl Seminar 06091: Data Structures (2006-02-26 - 2006-03-03) (Details)
- Dagstuhl Seminar 08081: Data Structures (2008-02-17 - 2008-02-22) (Details)
- Dagstuhl Seminar 10091: Data Structures (2010-02-28 - 2010-03-05) (Details)
- Dagstuhl Seminar 14091: Data Structures and Advanced Models of Computation on Big Data (2014-02-23 - 2014-02-28) (Details)
- Dagstuhl Seminar 16101: Data Structures and Advanced Models of Computation on Big Data (2016-03-06 - 2016-03-11) (Details)
- Dagstuhl Seminar 19051: Data Structures for the Cloud and External Memory Data (2019-01-27 - 2019-02-01) (Details)
- Dagstuhl Seminar 21071: Scalable Data Structures (2021-02-14 - 2021-02-19) (Details)
- Dagstuhl Seminar 23211: Scalable Data Structures (2023-05-21 - 2023-05-26) (Details)
- Dagstuhl Seminar 25191: Adaptive and Scalable Data Structures (2025-05-04 - 2025-05-09) (Details)
