Please use this identifier to cite or link to this item:
Title: Optimised Predecessor Data Structures for Internal Memory.
Authors: Rahman, Naila
Cole, Richard
Raman, Rajeev
First Published: 2001
Citation: Algorithm Engineering: 5th International Workshop, WAE 2001 Aarhus, Denmark, August 28-31, 2001, Proceedings. Lecture Notes in Computer Science, 2001, 2141, pp. 67-78
Abstract: We demonstrate the importance of reducing misses in the translation-lookaside buffer (TLB) for obtaining good performance on modern computer architectures. We focus on data structures for the dynamic 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.
DOI Link: 10.1007/3-540-44688-5_6
ISSN: 0302-9743
Type: Conference paper
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
There are no files associated with this item.

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.