February 17 – 22 , 2008, Dagstuhl Seminar 08081
For support, please contact
Art exhibition opens on Tuesday Feb. 19
All participants are invited to attend after dinner on 7:30 pm.
More information here.
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.
Dagstuhl Seminar Series
- 16101: "Data Structures and Advanced Models of Computation on Big Data" (2016)
- 14091: "Data Structures and Advanced Models of Computation on Big Data" (2014)
- 10091: "Data Structures" (2010)
- 06091: "Data Structures " (2006)
- 04091: "Data Structures" (2004)
- 02091: "Data Structures" (2002)
- 00091: "Data Structures" (2000)
- 98091: "Data Structures" (1998)
- 9609: "Data Structures" (1996)
- 9409: "Data Structures" (1994)
- 9145: "Data Structures" (1991)
- Data Bases / Information Retrieval
- Data Structures / Algorithms / Complexity
- Data structures
- Large data sets
- External memory methods
- Flash memory