Dagstuhl Seminar 25191
Adaptive and Scalable Data Structures
( May 04 – May 09, 2025 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25191
Organizers
- Michael A. Bender (Stony Brook University, US)
- John Iacono (ULB - Brussels, BE)
- László Kozma (FU Berlin, DE)
- Eva Rotenberg (Technical University of Denmark - Lyngby, DK)
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
About the seminar
Data structures are fundamental building blocks of computing systems and are deployed in applications of increasing size and sophistication. The design and analysis of scalable data structures has been a central goal of computer science from the beginnings of the field. Yet, the study of data structures remains as active as ever, as it reflects changes in the underlying computational infrastructure, as well as the evolving needs of applications.
Adaptivity is a multi-faceted goal that can refer to: data structures seamlessly taking advantage of resources offered by the underlying hardware, or restrictions thereof; the usage of application-specific insights or side-information to improve data structure efficiency; the extent to which the data generating process can adversarially adapt to the data structure.
Some of these aspects pose long-standing open questions that continue to inspire research (e.g., the dynamic optimality conjecture asks whether binary search trees can optimally adapt to their usage pattern). More recent directions of adaptivity to side-information, e.g., from machine learning advice, pose fresh research questions, and can also relate to past work on data structures that are locality-adaptive, robust to errors, or that make use of imprecise or unreliable comparisons. A refined notion related to adversarial adaptivity is that of history-independence: the question of whether data structures can avoid leaking information about their past sequence of operations. Besides the clear motivation from the point of view of security and privacy, this concept has recently played a key role in designing state-of-the-art data structures for the prototypical list labeling problem. Participants in the seminar have further explored to what extent history independence can be reconciled with optimal efficiency in fundamental data structures such as priority queues.
This seminar was the 16th in a series of loosely related Dagstuhl Seminars on data structures. It brought together a diverse group of researchers with complementary expertise and varying levels of seniority, to illuminate different aspects of data structure scalability and adaptivity. We also aimed to include researchers who are experts in adjacent, applied areas (data structures in computational geometry, data structures for strings, etc.), to inspire and inform each other and to identify relevant research directions.
The organizers of the seminar put a strong emphasis on discussion and collaboration. Participants were asked to give short (10-15 minutes) or medium (20-25 minutes) talks. Most participants spoke, and the format allowed everyone who wished to speak to do so. We explicitly encouraged forward-thinking talks that include open problems, interesting new directions or challenges, focusing on informal, open-ended discussion, rather than polished presentations of past work. In the program we made a deliberate effort to leave space for loosely structured discussion and collaboration, reserving most of the afternoons for this purpose, and having brief status-report sessions where we all met to discuss what people had been discussing.
Topics
The presentations and discussions covered a broad range of topics in classical data structures and diverse applications, as well as new directions inspired by various aspects of scalability and adaptivity.
Models of computation were an important theme of the seminar. Afshani (Section 4.10 of the full report) discussed possible separations concerning I/O operations and total work, Bille (Section 4.1) discussed data structures in the ultra-wide word RAM model, and Meyer (Section 4.2) talked about unstructured parallel I/O on SSDs in the context of graph algorithms.
Parallelism and distributed computing were also the focus of further talks: King (Section 4.4) presented work on a problem in distributed setting with many Byzantine participants, and Chechik (Section 5.8) discussed the maximum independent set problem in the congested clique model.
Several talks focused on questions (old and new) on graph algorithms: Wein (Section 4.8) talked about a new concept of a “DAG cover” extending classical notions of tree covers, Liu (Section 4.9) discussed a batch version of the dynamic connectivity problem, van der Hoog (Section 5.2) raised a question about greedy chain decomposition on DAGs, Bilò (Section 4.15) revisited the problem of single-source shortest p-disjoint paths, Gudmundsson (Section 4.16) talked about approximate distance oracles for a special class of sparse graphs, and Fineman (Section 4.17) talked about open questions about incremental topological sorting.
Relating to online problems, Agrawal (Section 5.6) discussed results and open questions concerning a scheduling problem with DAG constraints, and Munro (Section 4.11) talked about a (paired) variant of the paging problem.
On compression and compact data structures, Navarro talked about dynamic bitvectors (Section 4.5) and on a graph problem related to grammar-based compression (Section 5.9), and Gawrychowski (Section 5.4) discussed open problems related to Lempel-Ziv compression. The analysis of data structures and related notions of adaptivity were a key focus of the seminar. Conway (Section 4.3) gave an overview of results and open questions on history-independent priority queues, while Iacono (Section 5.1) discussed the working set property of priority queues in conjunction with efficient decrease-key. Brodal (Section 4.6) highlighted a simple and efficient data structure for storing integers, and Tarjan (Section 5.3) drew attention to the different analyses of path compression, raising the question of an alternative proof; Kuszmaul (Section 4.14) talked about recent results and open questions on quadratic probing hash tables. Kozma (Section 5.10) pointed out a remaining open question in the analysis of classical selection algorithms, and Farach-Colton (Section 5.5) raised a question related to the Karp-Rabin fingerprinting algorithm.
In his talk, Sedgewick (Section 4.13) advocated for an “algorithms science”, using cardinality estimation as a case study. Zamir (Section 4.7) presented recent work on using cryptographic techniques to design asymptotically faster algorithms. Bercea (Section 4.18) discussed a possible new model for Bloom filters with predictions. Storandt (Section 5.7) presented data structure questions arising in the context of geometric intersection problems. Goodrich (Section 4.12) presented computational geometry problems in a setting with probabilistic errors, and raised the question of designing data structures that are robust to probabilistic deletions.
Collaboration was structured around informal working groups, with focus on some of the concrete open problems identified during the seminar. These notably included questions on simultaneous work and I/O optimality (see Section 4.10), fully dynamic graph connectivity (see Section 4.9), history independent heaps (see Section 4.3), heaps with the working set property (see Section 5.1) and greedy chain decompositions of DAGs (see Section 5.2). Several promising directions were explored, and results were obtained already during the seminar. It is expected that the collaborations started at the seminar will lead to publications.
Final Thoughts
The organizers would like to thank the Dagstuhl team for their continuous support and also thank all participants for their contributions to the seminar. The current (16th) seminar was part of a long-running series that has co-evolved with the field, both tracking and inspiring its trends and developments throughout the years.
The seminar fills a unique niche in the computer science research landscape. Although data structural topics are well represented at major venues of theoretical computer science, this series provides essentially the only opportunity for core data structures researchers from around the world to meet and exchange ideas in an informal, collaborative setting, having data structures as the primary focus. (Some other fields, such as computational geometry have a broader tradition of specialized workshops focusing on problem-solving.)
The appreciation by the community for the seminar and the opportunity it offers to personally meet and interact is reflected by the very strong response to invitations and the highly positive subsequent feedback. Respondents particularly praised the relaxed, informal atmosphere and the focus on short talks and loosely structured collaboration around open questions, validating the organizers' efforts in this direction.
Earlier seminars in the series had few female participants. An important focus of the last three seminars was to significantly increase female attendance. In the current seminar, 43% of the invited participants were female, resulting in a 35\% female attendance.
Another important goal of the seminar is to encourage the interaction between senior and early career researchers, the latter comprising around a third of the invited participants and eventual attendees. We also made a deliberate effort to include researchers who have not attended the previous seminar(s), these making up a slight majority of both the invitee- and participant lists; we find this to be particularly important for a long-running seminar.
All the aspects mentioned were strongly appreciated by the participants in the post-seminar survey. The survey respondents also praised the coverage of a diverse range of research topics, and the continued efforts by the organizers to refine and improve the seminar format.
Creative Commons BY 4.0
Michael A. Bender, John Iacono, László Kozma, and Eva Rotenberg
Data structures are the science of organizing and accessing data, and their study is a core part of computer science. They underpin our computing infrastructure with efficiency being of critical importance. As the computing landscape changes with more demanding tasks arising, data structure research remains vibrant, with two aspects coming particularly in focus: scalability and adaptivity.
Scalability means that data structures remain efficient as data sets increase, become more dynamic, and become more distributed. Adaptivity implies taking advantage of modern hardware, such as multicore computation or memory hierarchies, as well specific structure and biases in the operations performed. One seeks to create structures that maximally take advantage of such architectural and distributional details without any foreknowledge of them. General limits of adaptivity have long posed deep theoretical questions, which continue to inspire research.
This Dagstuhl Seminar is part of a successful series begun in 1991. The series has contributed to shaping trends in data structures research. We propose to bring together leading researchers in classical data structures with those with expertise under the theme of scalability and adaptivity. By exposing the participants to diverse viewpoints, we aim to connect models and approaches, inspire new directions and collaborations, make progress on difficult problems, and continue advancing the state-of-the-art in data structures research.
Michael A. Bender, John Iacono, László Kozma, and Eva Rotenberg
Please log in to DOOR to see more details.
- Peyman Afshani (Aarhus University, DK) [dblp]
- Kunal Agrawal (Washington University - St. Louis, US) [dblp]
- Hideo Bannai (Institute of Science Tokyo, JP) [dblp]
- Michael A. Bender (Stony Brook University, US) [dblp]
- Ioana Oriana Bercea (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Philip Bille (Technical University of Denmark - Lyngby, DK) [dblp]
- Davide Bilò (University of L'Aquila, IT) [dblp]
- Gerth Stølting Brodal (Aarhus University, DK) [dblp]
- Shiri Chechik (Tel Aviv University, IL) [dblp]
- Alexander Conway (Cornell Tech - New York, US) [dblp]
- Justin Dallant (UL - Brussels, BE) [dblp]
- Aditi Dudeja (Paris Lodron Universität Salzburg, AT) [dblp]
- Faith Ellen (University of Toronto, CA) [dblp]
- Martin Farach-Colton (NYU - New York, US) [dblp]
- Jeremy Fineman (Georgetown University - Washington, DC, US) [dblp]
- Pawel Gawrychowski (University of Wroclaw, PL) [dblp]
- Michael Goodrich (University of California - Irvine, US) [dblp]
- Inge Li Gørtz (Technical University of Denmark - Lyngby, DK) [dblp]
- Joachim Gudmundsson (The University of Sydney, AU) [dblp]
- John Iacono (ULB - Brussels, BE) [dblp]
- Rob Johnson (Broadcom - San Jose, US) [dblp]
- Valerie King (University of Victoria, CA) [dblp]
- Tomasz Kociumaka (MPI für Informatik - Saarbrücken, DE) [dblp]
- Hanna Komlós (NYU - New York, US) [dblp]
- László Kozma (FU Berlin, DE) [dblp]
- William Kuszmaul (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Jingxun Liang (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Quanquan C. Liu (Yale University - New Haven, US) [dblp]
- Ulrich Carsten Meyer (Goethe University - Frankfurt am Main, DE) [dblp]
- Ian Munro (University of Waterloo, CA) [dblp]
- Gonzalo Navarro (University of Chile - Santiago de Chile, CL) [dblp]
- Eva Rotenberg (Technical University of Denmark - Lyngby, DK) [dblp]
- Robert Sedgewick (Princeton University, US) [dblp]
- Marek Sokolowski (MPI für Informatik - Saarbrücken, DE) [dblp]
- Teresa Steiner (Technical University of Denmark - Lyngby, DK) [dblp]
- Sabine Storandt (Universität Konstanz, DE) [dblp]
- Robert Endre Tarjan (Princeton University, US) [dblp]
- Ivor van der Hoog (Technical University of Denmark - Lyngby, DK) [dblp]
- Stefan Walzer (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Nicole Wein (University of Michigan - Ann Arbor, US) [dblp]
- Huacheng Yu (Princeton University, US) [dblp]
- Or Zamir (Tel Aviv University, IL) [dblp]
- Renfei Zhou (Carnegie Mellon University - Pittsburgh, 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)
- Dagstuhl Seminar 23211: Scalable Data Structures (2023-05-21 - 2023-05-26) (Details)
- Dagstuhl Seminar 27411: Simplicity and Efficiency of Data Structures (2027-10-10 - 2027-10-15) (Details)
Classification
- Data Structures and Algorithms
Keywords
- Data structures
- Algorithms
- Big data
- Computational models
