https://www.dagstuhl.de/23211

May 21 – 26 , 2023, Dagstuhl Seminar 23211

Scalable Data Structures

Organizers

Gerth Střlting Brodal (Aarhus University, DK)
John Iacono (UL – Brussels, BE)
László Kozma (FU Berlin, DE)
Vijaya Ramachandran (University of Texas – Austin, US)

For support, please contact

Jutka Gasiorowski for administrative matters

Marsha Kleinbauer for scientific matters

Motivation

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.

Motivation text license
  Creative Commons BY 4.0
  Gerth Střlting Brodal, John Iacono, László Kozma, and Vijaya Ramachandran

Dagstuhl Seminar Series

Classification

  • Data Structures And Algorithms
  • Information Retrieval

Keywords

  • Data structures
  • Algorithms
  • Computational models
  • Big data
  • Parallel computation

Documentation

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.

Publications

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