https://www.dagstuhl.de/23211

21. – 26. Mai 2023, Dagstuhl-Seminar 23211

Scalable Data Structures

Organisatoren

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)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Jutka Gasiorowski zu administrativen Fragen

Marsha Kleinbauer zu wissenschaftlichen Fragen

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

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.