Open Collections

Data Structures of the Future: Concurrent, Optimistic, and Relaxed

Banff International Research Station for Mathematical Innovation and Discovery

A central computing trend over the last decade has been the need to process increasingly larger amounts of data as efficiently as possible. This development is challenging both software and hardware design, and is altering the way data structures and algorithms are constructed, implemented, and deployed. In this talk, I will present some examples of such new data structure design ideas and implementations. In particular, I will discuss some inherent limitations of parallelizing classic data structures, and then focus on approaches to circumvent these limitations. The first approach is to relax the software semantics, to allow for approximation, randomization, or both. The second is to modify the underlying hardware architecture to unlock more parallelism. Time permitting, I will also cover results showing that both approaches can improve real-world performance, and touch upon some of the major open questions in the area.

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: Microsoft Research

2017-06-21

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/62050

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/