Dagstuhl Seminar 23211
Scalable Data Structures
( May 21 – May 26, 2023 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/23211
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)
Contact
- Marsha Kleinbauer (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
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]
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 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)
Classification
- Data Structures and Algorithms
- Information Retrieval
Keywords
- Data structures
- algorithms
- computational models
- big data
- parallel computation
