Practical data structures

Martin Mareš

Abstract

(based on joint work with Michal Pokorný)

Algorithm designers often pay little attention to behavior of actual computers - they prefer simple theoretical models instead. At the same time, hardware designers strive for making their machines more efficient, but inevitably also more distant from the simple models. Recently, a couple of more realistic models have appeared (e.g., cache-oblivious algorithms). We will present several approaches to design of data structures in these models, together with insight into their behavior on real hardware.