Optimised predecessor data structures for internal memory

Naila Rahman, Richard Cole, Rajeev Raman

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithm Engineering - 5th International Workshop, WAE 2001, Proceedings
Number of pages12
StatePublished - 2001
Event5th International Workshop on Algorithm Engineering, WAE 2001 - Arhus, Denmark
Duration: Aug 28 2010Aug 31 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2141 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th International Workshop on Algorithm Engineering, WAE 2001

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Optimised predecessor data structures for internal memory'. Together they form a unique fingerprint.

Cite this