Dagstuhl Seminar 23071
From Big Data Theory to Big Data Practice
( Feb 12 – Feb 17, 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/23071
Organizers
- Martin Farach-Colton (Rutgers University - Piscataway, US)
- Fabian Daniel Kuhn (Universität Freiburg, DE)
- Ronitt Rubinfeld (MIT - Cambridge, US)
- Przemyslaw Uznanski (University of Wroclaw, PL)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
As data has grown faster than RAM, the theory of algorithms has expanded to provide approaches for tackling such problems. These fall into three broad categories:
- Streaming and semi-streaming algorithms
- Sublinear or local algorithms
- External memory algorithms
Each of these areas has a vibrant literature, and many of the results from the theory literature have made their way into practice. Other results are not suitable for implementation and deployment.
This Dagstuhl Seminar's aim was to address several questions by bringing together algorithmicists from these subcommunities, as well as algorithms engineers. Specifically, the aim was to address the following questions:
- What themes emerge from considering practical algorithms from the theory literature?
- Can we use these insights to create new models or to capture interesting new optimization criteria?
By bringing together researchers in these disparate areas and by including researchers in algorithms engineering, we hope to have brought to light these deep connections. The goals were to:
- Extract shared lessons to help guide theoretical research towards practical solutions;
- Create a feedback loop where commonalities of practical solutions can help guide future theoretical research;
- Help cross-pollinate these research areas.
Organization of the Seminar
The seminar brought together 38 researchers from theoretical computer science and systems research, both from academia and from industry. The participants consisted of both senior and junior researchers, including a number of postdocs and advanced PhD students.
During the four (The seminar had to be cut short by one day due to unforeseen logistic issues.) days of the seminar, 20 talks of different lengths took place. Speakers were given no time constraints, but all the talks took between 30 to 60 minutes. We value the freedom given to the speakers, and the audience enjoyed the relaxed schedule as well. Each day afternoons were spent on fruitfull discussions and open-ended open problems sessions.
Outcome
The seminar was seen as a success by organizers and participants. It brought together relevant communities, shared state-of-the-art research, and discussed challenges. The talks were of high quality and stimulating, encouraging participants to actively engage in working groups during the afternoon and evenings. It was particularly appreciated that a significant number of younger researchers (postdocs and PhD students) participated and integrated well. The organizers would like to express their gratitude to the Scientific Directorate and the administration of the Dagstuhl Center for their strong support during the seminar.
Creative Commons BY 4.0
Martin Farach-Colton, Fabian Daniel Kuhn, Ronitt Rubinfeld, and Przemyslaw Uznanski
Some recent advances in the theory of algorithms for big data – sublinear/local algorithms, streaming algorithms and external memory algorithms – have translated into impressive improvements in practice, whereas others have remained stubbornly resistant to useful implementations. This Dagstuhl Seminar aims to glean lessons for those aspects of these algorithms that have led to practical implementation to see if the lessons learned can both improve the implementations of other theoretical ideas and to help guide the next generation of theoretical advances.
As data has grown faster than RAM, the theory of algorithms has expanded to provide approaches for tackling such problems. These fall into three broad categories:
- Streaming and semi-streaming algorithms
- Sublinear or local algorithms
- External memory algorithms
Each of these areas has a vibrant literature, and many of the results from the theory literature have made their way into practice. Other results are not suitable for implementation and deployment. The seminar aims to address several questions by bringing together algorithmicists from these subcommunities, as well as algorithms engineers. Specifically, we aim to address the following questions:
- What themes emerge from considering practical algorithms from the theory literature?
- Can we use these insights to create new models or to capture interesting new optimization criteria?
By bringing together researchers in these disparate areas and by including researchers in algorithms engineering, we hope to bring to light these deep connections. The goals are to:
- Extract shared lessons to help guide theoretical research towards practical solutions;
- Create a feedback loop where commonalities of practical solutions can help guide future theoretical research;
- Help cross-pollinate these research areas.
Martin Farach-Colton, Fabian Daniel Kuhn, Ronitt Rubinfeld, and Przemyslaw Uznanski
- Kunal Agrawal (Washington University - St. Louis, US) [dblp]
- Alkida Balliu (Gran Sasso Science Institute - L'Aquila, IT) [dblp]
- Michael A. Bender (Stony Brook University, US) [dblp]
- Philip Bille (Technical University of Denmark - Lyngby, DK) [dblp]
- Sebastian Brandt (CISPA - Saarbrücken, DE) [dblp]
- Vincent Cohen-Addad (Google - Paris, FR) [dblp]
- Alexander Conway (VMware Research - Palo Alto, US) [dblp]
- Martin Dietzfelbinger (TU Ilmenau, DE) [dblp]
- Anne Driemel (Universität Bonn, DE) [dblp]
- Talya Eden (Bar-Ilan University - Ramat Gan, IL) [dblp]
- Martin Farach-Colton (Rutgers University - Piscataway, US) [dblp]
- Inge Li Gørtz (Technical University of Denmark - Lyngby, DK) [dblp]
- Riko Jacob (IT University of Copenhagen, DK) [dblp]
- Rob Johnson (VMware - Palo Alto, US) [dblp]
- Hanna Komlós (Rutgers University - New Brunswick, US)
- Adrian Kosowski (Pathway - Paris, FR)
- Fabian Daniel Kuhn (Universität Freiburg, DE) [dblp]
- William Kuszmaul (MIT - Cambridge, US) [dblp]
- Aleksander Lukasiewicz (University of Wroclaw, PL)
- Petra Mutzel (Universität Bonn, DE) [dblp]
- Yasamin Nazari (Universität Salzburg, AT) [dblp]
- Krzysztof Nowicki (Pathway - Paris, FR) [dblp]
- Dennis Olivetti (Gran Sasso Science Institute - L'Aquila, IT) [dblp]
- Krzysztof Onak (Boston University, US) [dblp]
- Rotem Oshman (Tel Aviv University, IL) [dblp]
- Prashant Pandey (University of Utah - Salt Lake City, US) [dblp]
- Ely Porat (Bar-Ilan University - Ramat Gan, IL) [dblp]
- Simon J. Puglisi (University of Helsinki, FI) [dblp]
- Sofya Raskhodnikova (Boston University, US)
- Eva Rotenberg (Technical University of Denmark - Lyngby, DK) [dblp]
- Ronitt Rubinfeld (MIT - Cambridge, US) [dblp]
- Christian Scheideler (Universität Paderborn, DE) [dblp]
- Comandur Seshadhri (University of California - Santa Cruz, US) [dblp]
- Christian Sohler (Universität Köln, DE) [dblp]
- Tatiana Starikovskaya (ENS - Paris, FR) [dblp]
- Jukka Suomela (Aalto University, FI) [dblp]
- David Tench (Rutgers University - Piscataway, US)
- Przemyslaw Uznanski (University of Wroclaw, PL) [dblp]
Classification
- Data Structures and Algorithms
- Distributed / Parallel / and Cluster Computing
Keywords
- Sublinear algorithms
- local algorithms
- external memory
