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.

Creative Commons BY 4.0

Gerth Stølting Brodal, John Iacono, László Kozma, and Vijaya Ramachandran

• Kunal Agrawal (Washington University - St. Louis, US) [dblp]
• Elena Arseneva (University of Lugano, CH) [dblp]
• Michael A. Bender (Stony Brook University, US) [dblp]
• Ioana Oriana Bercea (IT University of Copenhagen, DK) [dblp]
• Guy E. Blelloch (Carnegie Mellon University - Pittsburgh, US) [dblp]
• Gerth Stølting Brodal (Aarhus University, DK) [dblp]
• Alexander Conway (VMware Research - Palo Alto, US) [dblp]
• Justin Dallant (UL - Brussels, BE)
• Guy Even (Tel Aviv University, IL) [dblp]
• Rolf Fagerberg (University of Southern Denmark - Odense, DK) [dblp]
• Martin Farach-Colton (Rutgers University - Piscataway, US) [dblp]
• Inge Li Gørtz (Technical University of Denmark - Lyngby, DK) [dblp]
• John Iacono (UL - Brussels, BE) [dblp]
• Riko Jacob (IT University of Copenhagen, DK) [dblp]
• Rob Johnson (VMware - Palo Alto, US) [dblp]
• Valerie King (University of Victoria, CA) [dblp]
• Tsvi Kopelowitz (Bar-Ilan University - Ramat Gan, IL) [dblp]
• László Kozma (FU Berlin, DE) [dblp]
• Rasmus Kyng (ETH Zürich, CH) [dblp]
• Moshe Lewenstein (Bar-Ilan University - Ramat Gan, IL) [dblp]
• Quanquan C. Liu (Northwestern University - Evanston, US) [dblp]
• Ulrich Carsten Meyer (Goethe-Universität - Frankfurt am Main, DE) [dblp]
• Ian Munro (University of Waterloo, CA) [dblp]
• Markus E. Nebel (Universität Bielefeld, DE) [dblp]
• Eunjin Oh (POSTECH - Pohang, KR) [dblp]
• Rotem Oshman (Tel Aviv University, IL) [dblp]
• Seth Pettie (University of Michigan - Ann Arbor, US) [dblp]
• Cynthia A. Phillips (Sandia National Labs - Albuquerque, US) [dblp]
• Vijaya Ramachandran (University of Texas - Austin, US) [dblp]
• Rajeev Raman (University of Leicester, GB) [dblp]
• Eva Rotenberg (Technical University of Denmark - Lyngby, DK) [dblp]
• Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
• Francesco Silvestri (University of Padova, IT) [dblp]
• Shikha Singh (Williams College - Williamstown, US) [dblp]
• Nodari Sitchinava (University of Hawaii at Manoa - Honolulu, US) [dblp]
• Yihan Sun (University of California - Riverside, US) [dblp]
• Robert Endre Tarjan (Princeton University, US) [dblp]
• Nicole Wein (Rutgers University - Piscataway, US) [dblp]
• Sebastian Wild (University of Liverpool, GB) [dblp]
• Helen Xu (Lawrence Berkeley National Laboratory, US) [dblp]