Optimised Predecessor Data Structures for Internal Memory

Abstract. We demonstrate the importance of reducing misses in the translation-lookaside buer (TLB) for obtaining good performance on modern computer architectures. We focus on data structures for the dy-namic predecessor problem: to maintain a set S of keys from a totally ordered universe under insertions, deletions and predecessor queries. We give two general techniques for simultaneously reducing cache and TLB misses: simulating 3-level hierarchical memory algorithms and cache-oblivious algorithms. We give preliminary experimental results which demonstrate that data structures based on these ideas outperform data structures which are based on minimising cache misses alone, namely B-tree variants.