Dagstuhl Seminar 08081
Data Structures
( Feb 17 – Feb 22, 2008 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/08081
Organizers
- Lars Arge (Aarhus University, DK)
- Robert Sedgewick (Princeton University, US)
- Raimund Seidel (Universität des Saarlandes, DE)
Contact
- Annette Beyer (for administrative matters)
Impacts
- An Application of Self-organizing Data Structures to Compression : article - Dorrigiv, Reza; Lopez-Ortiz, Alejandro; Munro, J. Ian - Berlin : Springer, 2009 - (Lecture notes in computer science : 5526 ; S. 137-148). ISBN: 978-3-642-02010-0. DOI: 10.1007/978-3-642-02011-7.
- Dynamic Succinct Ordered Trees : article S. 439-450 - Farzan, Arash; Munro, J. Ian - Berlin : Springer, 2009. - (Lecture notes in computer science : 5555 ; S. 439-450). ISBN: 978-3-642-02926-4. DOI: 10.1007/978-3-642-02927-1.
- Lower Bounds for Succinct Data Structures : article S. 3 - Munro, J. Ian - Berlin : Springer, 2009 - (Lecture notes in computer science : 5029 ; S. 3). ISBN: 978-3-540-69066-5. DOI: 10.1007/978-3-540-69068-9.
The purpose of this workshop was to discuss recent developments in various aspects of data structure research and also to familiarize the community with some of problems that arise in the context of using so-called flash memory as a storage medium. 49 researchers attended the workshop producing a congenial and productive atmosphere.
A number of contributions reported on new advances on old problems in data structure research: E.g. John Iacono summarized recent advances regarding the dynamic optimality conjecture of splay trees, Bob Tarjan showed new results on dynamically maintaining an acyclic graph, Bob Sedgewick presented a particularly simple version of red-black trees, and Mihai Patrascu offered a new, plausible approach for proving super-polylogarithmic lower bounds to dynamic data structure problems.
The design of data structures and algorithms that can deal well with the memory hierarchy used in today's computers was another core topic of the workshop. E.g. Nobert Zeh discussed this problem in the context of red-blue line segment intersection, Rico Jacob considered the multiplication of dense vectors by a sparse matrix, and Michael Bender presented so-called streaming B-trees that can implement dictionaries well in this memory hierarchy context.
Reducing the actual space requirement of data structures to a minimum was the topic of several contributions. For instance Martin Dietzfelbinger and also Arash Farzan considered this problem from the theoretical point of view, and Peter Sanders and also Holger Bast from a very practical point of view.
A highlight of the workshop were the presentations by San Lyul Min and by Ethan Miller on so-called flash memory, which is physical memory that has found its way into many storage devices but has technological properties that lead to the following peculiarities: (i) Before a bit is written it has to be cleared, however this can only be achieved by clearing an entire block of bits. (ii) Every block of bits can only be cleared a (large) constant number of times before the storage capabilities of this block become too unreliable.
There were many more interesting contributions than listed here and, of course, countless discussions and collaborations. The Dagstuhl atmosphere provided just the right environment for all this.
- Mohammad Ali Abam (Aarhus University, DK) [dblp]
- Pankaj Kumar Agarwal (Duke University - Durham, US) [dblp]
- Lars Arge (Aarhus University, DK) [dblp]
- H. Bast (MPI für Informatik - Saarbrücken, DE)
- Michael A. Bender (SUNY - Stony Brook, US) [dblp]
- Henrik Blunck (Aarhus University, DK)
- Prosenjit Bose (Carleton University - Ottawa, CA)
- Karl Bringmann (Saarland University, DE) [dblp]
- Andrej Brodnik (University of Primorska, SI) [dblp]
- Adam L. Buchsbaum (Lion Cave Capital - Edison, US)
- Marjan Celikik (MPI für Informatik - Saarbrücken, DE)
- Martin Dietzfelbinger (TU Ilmenau, DE) [dblp]
- Faith Ellen (University of Toronto, CA) [dblp]
- Jeff Erickson (University of Illinois - Urbana-Champaign, US) [dblp]
- Rolf Fagerberg (University of Southern Denmark - Odense, DK) [dblp]
- Arash Farzan (University of Waterloo, CA)
- Loukas Georgiadis (HP Labs - Palo Alto, US) [dblp]
- Anders Gidenstam (MPI für Informatik - Saarbrücken, DE)
- Torben Hagerup (Universität Augsburg, DE) [dblp]
- Sariel Har-Peled (University of Illinois - Urbana-Champaign, US) [dblp]
- Herman J. Haverkort (TU Eindhoven, NL) [dblp]
- John Iacono (Polytechnic Institute of NYU - Brooklyn, US) [dblp]
- Riko Jacob (TU München, DE) [dblp]
- Valerie King (University of Victoria, CA) [dblp]
- Moshe Lewenstein (Bar-Ilan University - Ramat Gan, IL) [dblp]
- Alejandro Lopez-Ortiz (University of Waterloo, CA) [dblp]
- Conrado Martinez (UPC - Barcelona, ES) [dblp]
- Domagoj Matijevic (University of Osijek, HR)
- Kurt Mehlhorn (MPI für Informatik - Saarbrücken, DE) [dblp]
- Ulrich Carsten Meyer (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Ethan Miller (University of California - Santa Cruz, US)
- Sang Lyul Min (Seoul Nat. University, KR) [dblp]
- Gabriel Moruz (University of Frankfurt, DE) [dblp]
- Ian Munro (University of Waterloo, CA) [dblp]
- Rasmus Pagh (IT University of Copenhagen, DK) [dblp]
- Mihai Patrascu (AT&T Labs Research - Florham Park, US)
- Seth Pettie (Univ. of Michigan - Ann Arbor, US) [dblp]
- Rajeev Raman (University of Leicester, GB) [dblp]
- Peter Sanders (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Srinivasa Rao Satti (Aarhus University, DK) [dblp]
- Robert Sedgewick (Princeton University, US) [dblp]
- Raimund Seidel (Universität des Saarlandes, DE) [dblp]
- Daniel Sleator (Carnegie Mellon University, US)
- Robert Endre Tarjan (Princeton University, US) [dblp]
- Laura I. Toma (Bowdoin College - Brunswick, US) [dblp]
- Jan Vahrenhold (TU Dortmund, DE) [dblp]
- Suresh Venkatasubramanian (University of Utah - Salt Lake City, US) [dblp]
- Alfredo Viola (INCO - Montevideo, UY) [dblp]
- Norbert Zeh (Dalhousie University, CA) [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 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 25191: Adaptive and Scalable Data Structures (2025-05-04 - 2025-05-09) (Details)
Classification
- data bases / information retrieval
- data structures / algorithms / complexity
- networks
Keywords
- data structures
- algorithms
- large data sets
- external memory methods
- streaming
- web-scale
- flash memory
