Please use this identifier to cite or link to this item:
|Title:||Optimised Predecessor Data Structures for Internal Memory.|
|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.|
|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.