Optimised predecessor data structures for internal memory

Naila Rahman, Richard Cole, Rajeev Raman

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

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.

Original languageEnglish (US)
Title of host publicationAlgorithm Engineering - 5th International Workshop, WAE 2001, Proceedings
Pages67-78
Number of pages12
DOIs
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

Other

Other5th International Workshop on Algorithm Engineering, WAE 2001
CountryDenmark
CityArhus
Period8/28/108/31/10

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this