Principles of Programming Seminar
In Person - ASA Conference Room, Gates Hillman 6115
Ph.D. Student, Department of Computer Science, Aarhus University, Denmark
I/O-Efficient Algorithms and Data Structures
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.
Steffan Sølvsten is a Ph.D. 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.
Faculty Host: Marijin Heule