Data structures enable the efficient storage and retrieval of data in a variety of settings. Data structures are central to almost all of computing and have been an object of study since the beginning of the discipline of computer science. For a given abstract data type and a certain model of computation, speed and small space are the usual aims of data structures research. Due to the unprecedented scale at which data structures are deployed in applications, even small performance gains can have a significant effect. Thus, the study of data structures remains a very active area of research with unresolved old problems, new objects of interest, new techniques for analysis, and an interplay between theoretical data structure design, developments in computer hardware, and the needs of modern applications.
Data structures are not designed in isolation from the computing devices that they run on. The ultimate goal is to design data structures that are fast in practice. As hardware advances, models of computation must also evolve. The original and most simplistic models included the random access machine (RAM) and comparison models. Later models attempted to more accurately capture various hardware effects; these include the external memory/DAM model, the cache-oblivious model of multi-level memory systems and the streaming model. A compelling goal of data structure research is to develop algorithms that are optimal for several computational models at the same time, and as a counterpoint, to study inherent trade-offs between the cost measures of the different models, e.g., query time vs. space usage, read time vs. write time, computational time vs. block transfers to/from external memory, or optimality in the external memory model vs. optimality in the cache-oblivious model.
Parallel computation is crucial to the scalability of data structures and has attained particular importance as single processor hardware is no longer prevalent, even on mobile devices. Modern parallelism takes many forms, from several cores on a modern CPU to several machines on a network, to specialized hardware. Each of these settings requires us to revisit classical models of parallelism such as the PRAM, fork-join, and bulk synchronous parallel models, in order to evaluate how well they apply and then to develop effective methods. GPUs present their own challenges, as they are often the most powerful computing unit in a modern machine, yet have a particular architecture that is a vestige of their origins in graphics processing and defies simple modeling.
Dagstuhl Seminars on data structures have been held roughly biennially since 1991. These seminars have played a very important role in moving a community that was focused on theoretical analysis to implementation, experimentation, and deployment. This Dagstuhl Seminar will, in addition to the “classical” data structuring topics, place special emphasis on spawning new research within data structures for multithreaded, bulk-synchronous, GPU, and emerging computing paradigms such as tensor cores.
- 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 98091: Data Structures (1998-03-02 - 1998-03-06) (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)
- Data Structures and Algorithms
- Information Retrieval
- Data structures
- computational models
- big data
- parallel computation