Dagstuhl Seminar 13232
Indexes and Computation over Compressed Structured Data
( Jun 02 – Jun 07, 2013 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/13232
Organizers
- Sebastian Maneth (University of Oxford, GB)
- Gonzalo Navarro (University of Chile - Santiago de Chile, CL)
Contact
- Andreas Dolzmann (for scientific matters)
Impacts
- Less Space : Indexing for Queries with Wildcards : article in LNCS 8283, pp. 89-99 - Lewenstein, Moshe; Munro, J. Ian; Raman, Venkatesh; Thankachan, Sharma V. - Berlin : Springer, 2013. - pp. 89-99 - (Lecture notes in computer science : ARCOSS : 8283 ; pp. 89-99).
- Ranked Document Selection : article in LNCS 8503 SWAT 2014 : pp. 344-356 - Munro, J. Ian; Navarro, Gonzalo; Shah, Rahul; Thankachan, Sharma V. - Berlin : Springer, 2014 - (Lecture notes in computer science : 8503 ; article).
- Succinct Data Structures for Representing Equivalence Classes : article in LNCS 8283, pp. 502-512 - Lewenstein, Moshe; Munro, J. Ian; Raman, Venkatesh - Berlin : Springer, 2013. - pp. 502-512 - (Lecture notes in computer science : ARCOSS : 8283 ; pp. 502-512).
This seminar aims to bring together researchers from various research directions of compression and indexing of structured data. The field is gaining importance as digitally stored data volumes are increasing at unprecedented speeds. Of particular interest are compression schemes that allow data to be queried without prior decompression, and combinations of such schemes with indexes that give fast access to particular operations.
Our meeting will be a follow-up to the very successful June, 2008 Dagstuhl Seminar 08261, "Structure-Based Compression of Complex Massive Data", which brought together researchers from a range of different areas including data structures, databases, and automata, among others. The resultant ideas were later published in top venues and generated important system implementations (e.g. the "SXSI"system). The present seminar continues to address a variety of fields. Its focus has shifted towards data structures and indexes and slightly away from databases. It now also touches upon information retrieval (through ranking, tf/idf) and graph processing. The seminar seeks to inspire the sharing of theoretical results and the practical requirements related to compression. Topics of the seminar include, but are not limited to:
- Tractability versus Intractability for Algorithmic Problems on Compressed Data
- Compression Algorithms for Trees and Graphs
- Indexes for Compressed Data
- Algorithms for Compressed Data
- Better Search Results: Ranking and TF/IDF
- Applications of Structure Compression to other Areas
We expect the seminar to have the following outcomes:
- Discovery of interconnections between different research directions and CS areas: databases, operational research, WWW, etc.
- Interchange of ideas between theory and practice
- Finding of new application areas for compression of structured data
- Development of research topics that are of common interest
- Identification of key problems and requirements for the future of compression techniques for structured data
- Initiation of new collaborations
The above will be discussed within the context of three types of sessions: overview, small, and summary. In the first type of session, overviews of state-of the art and open research issues on the contributing research areas will be presented to all participants. In the small sessions, participants will discuss more focused specific topics. In the summary sessions, results of small group discussions will be presented to all participants. We are convinced that the seminar will provide a unique chance to discover interconnections between different research directions in compression and indexing, to interchange ideas between theory and application oriented research, to distinguish between solved and open questions in the field, and to initiate new collaborations.
The Dagstuhl Seminar "Indexes and Computation over Compressed Structured Data" took place from June 2nd to 7th, 2013. The aim was to bring together researchers from various research directions of compression and indexing of structured data. Compression, and the ability to compute directly over compressed structures, is a topic that is gaining importance as digitally stored data volumes are increasing at unprecedented speeds. Of particular interest is the combination of compression schemes with indexes that give fast access to particular operations. The seminar was meant to inspire the exchange of theoretical results and practical requirements related compression and indexing. These points were addressed in particular
- Tractability versus Intractability for Algorithmic Problems on Compressed Data
- Compression Algorithms for Strings, Trees, and Graphs
- Indexes for Compressed Data
- Algorithms for Compressed Data
- Better Search Results: Ranking and TF/IDF
- Applications of Structure Compression to other Areas
The seminar fully satisfied our expectations. The 34$participants from 1$ countries (Canada, Chile, Denmark, Finland, Germany, Great Britain, Italy, Israel, Japan, Spain, and US) had been invited by the organizers to give survey talks about their recent research related to the topic of the seminar. The talks covered topics related to compression (e.g. grammar-based string compression) databases (e.g., XML, and top-k query answering), data structures (e.g. wavelet tries), string matching, and ranged to broad application areas such as biology. Most talks were followed by lively discussions. Smaller groups formed naturally which continued these discussions later.
We thank Schloss Dagstuhl for the professional and inspiring atmosphere. Such an intense research seminar is possible because Dagstuhl so perfectly meets all researchers' needs. For instance, elaborate research discussions in the evening were followed by local wine tasting or by heated sauna sessions.
Creative Commons BY 3.0 Unported license
Sebastian Maneth and Gonzalo Navarro
- Djamal Belazzougui (University of Helsinki, FI) [dblp]
- Philip Bille (Technical University of Denmark - Lyngby, DK) [dblp]
- Stefan Böttcher (Universität Paderborn, DE) [dblp]
- Francisco Claude (University of Waterloo, CA) [dblp]
- Henning Fernau (Universität Trier, DE) [dblp]
- Johannes Fischer (KIT - Karlsruher Institut für Technologie, DE) [dblp]
- Travis Gagie (University of Helsinki, FI) [dblp]
- Pawel Gawrychowski (MPI für Informatik - Saarbrücken, DE) [dblp]
- Roberto Grossi (University of Pisa, IT) [dblp]
- Shunsuke Inenaga (Kyushu University - Fukuoka, JP) [dblp]
- Artur Jez (MPI für Informatik - Saarbrücken, DE) [dblp]
- Juha Kärkkäinen (University of Helsinki, FI) [dblp]
- Susana Ladra González (University of A Coruña, ES) [dblp]
- Alejandro Lopez-Ortiz (University of Waterloo, CA) [dblp]
- Veli Mäkinen (University of Helsinki, FI) [dblp]
- Sebastian Maneth (University of Oxford, GB) [dblp]
- Ian Munro (University of Waterloo, CA) [dblp]
- Gonzalo Navarro (University of Chile - Santiago de Chile, CL) [dblp]
- Yakov Nekrich (University of Kansas - Lawrence, US) [dblp]
- Patrick K. Nicholson (University of Waterloo, CA) [dblp]
- Enno Ohlebusch (Universität Ulm, DE) [dblp]
- Giuseppe Ottaviano (University of Pisa, IT) [dblp]
- Simon J. Puglisi (University of Helsinki, FI) [dblp]
- Rajeev Raman (University of Leicester, GB) [dblp]
- Manfred Schmidt-Schauss (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Diego Seco (University of Conception, CL) [dblp]
- Rahul Shah (Louisiana State University - Baton Rouge, US) [dblp]
- Yasuo Tabei (Hokkaido University, JP) [dblp]
- Sharma V. Thankachan (Louisiana State University - Baton Rouge, US) [dblp]
- Alexander Tiskin (University of Warwick - Coventry, GB) [dblp]
- Koji Tsuda (CBRC - Tokyo, JP) [dblp]
- Niko Välimäki (University of Helsinki, FI) [dblp]
- Rossano Venturini (University of Pisa, IT) [dblp]
- Oren Weimann (University of Haifa, IL) [dblp]
Related Seminars
Classification
- data bases / information retrieval
- data structures / algorithms / complexity
Keywords
- compression
- indexing
- algorithms
