PoP Seminar Talk

I/O-Efficient Algorithms and Data Structures

Steffan Sølvsten, Graduate Student, Aarhus University
Friday, 08 September, 2023; 3:00 pm
GHC 6115
Host: Marijn Huele

Abstract

There are multiple approaches to deal with computations that have to run on massive data sets, e.g., randomised algorithms or machine learning. There is also a third approach: make the classic deterministic algorithms able to consume an input and/or produce an output that vastly exceeds the machine’s internal memory. To do so, one needs to optimise the algorithm’s access to data. That is, it needs to be I/O-efficient.

This talk is a short guided tour of the prior 36 years of research into I/O-efficient computation, starting with the I/O-model by Aggarwal and Vitter, then looking at the foundational I/O-efficient data structures, to then finally combining these data structures into algorithms that can handle petabytes of data without breaking a sweat.

Bio

Steffan Sølvsten is a PhD student at Aarhus University, Denmark, where he attempts to bridge the gap between algorithms and formal methods. Aarhus University is world renowned for its contributions to designing I/O-efficient algorithms; Steffan’s research applies these techniques to Decision Diagrams - both in theory and in practice.